Hacker News

We can likely use different number representations for faster results. E.g. numbers in the form of coefficients to prime factors can be multipled at O(n) time, right?

zeroonetwothree 2 days ago [ - ]

True but addition becomes a lot less efficient in this representation :)

WCSTombs 2 days ago [ - ]

To make both addition and multiplication O(n), you can store numbers as their residues modulo a bunch of different primes and appeal to the Chinese Remainder Theorem. However, then size comparison becomes difficult.

less_less 2 days ago [ - ]

Residue number systems are really neat! They're sometimes used in crypto implementations, but there you're doing modular multiplication and in most cases the modular reduction then becomes costly, so it's not a free lunch. (Except in RSA and a few other cases. RSA-CRT gets you a "free" ~4x performance boost except it's more brittle to mistakes and side-channel / fault attacks.)

There's also NTT / Fourier multiplication as an option, for big integers or polynomials or modular arithmetic.

im3w1l a day ago [ - ]

I think the problem comes when you do a multiplication and you need more primes for uniqueness.

tzs a day ago [ - ]

I think you would probably just pick enough primes at the start to handle numbers up to the number of bits you need. If we stick with primes that fit in 32-bit unsigned integers, then using the largest k such primes covers numbers up this many bits or decimal digits:

     k     bits  digits
    10      319      96
    20      639     192
    30      959     288
    40     1279     385
    50     1599     481
    75     2399     722
   100     3199     963
   150     4799    1444
   250     7999    2408
   500    15999    4816
  1000    31999    9632

Here it is if we use the k largest primes that fit in 16-bit unsigned integers:

     k   bits  digits
    10    159      48
    20    319      96
    30    479     144
    40    639     192
    50    799     240
    75   1199     361
   100   1598     481
   150   2397     721
   250   3991    1201
   500   7967    2398
  1000  15868    4776

If we use primes that fit in 8-bit unsigned integers, here's what we can handle with the largest k such primes. This table only goes to 54 because after that we run out of primes.

   k  bits  digits
  10    78      23
  20   152      45
  30   220      66
  40   281      84
  50   327      98
  54   334     100

im3w1l 15 hours ago [ - ]

This might work really well in practice idk, but I think it's not allowed by big O to pick a maximum supported size. Otherwise you could just make a lookup table. Your algorithm must be ready for anything.

necovek 2 days ago [ - ]

You mean like those guaranteed-always-compresses-by-at-least-one-bit algorithm patents gzip page made fun of?

In your case, doing prime factoring is where the cost would be, wouldn't it?

avmich 2 days ago [ - ]

Yes, but the point is to look for different representations, not necessarily use this specific one.