10 ms·
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,
by avmich 2mo ago
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?
- necovek 2mo agoYou 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 2mo agoYes, but the point is to look for different representations, not necessarily use this specific one.
- necovek 2mo agoYes, but the point is that getting to a different representation from a natural one (eg. binary one with computers or a decimal one for human use) is going to have some "external" overhead which is likely to negate the savings. Yes, sometimes a neat trick like the one in the article of replacing one multiplication with substraction appears, but that is not as universal.
- zeroonetwothree 2mo agoTrue but addition becomes a lot less efficient in this representation :)
- WCSTombs 2mo agoTo 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 2mo agoResidue 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 2mo agoI think the problem comes when you do a multiplication and you need more primes for uniqueness.
- tzs 2mo agoI 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 2mo agoThis 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.