3 ms·
for about a decade, integer multiplication was at n4^log*(n) where log* is the iterated logarithm. Also the curently best factorization algorithm (GNFS) is at
by adgjlsfhk1 1y ago
for about a decade, integer multiplication was at n4^log*(n) where log* is the iterated logarithm.
Also the curently best factorization algorithm (GNFS) is at exp(k*log(n)^1/3log(log(n))^2/3).
Intro algorithms classes just tend to stay away from the really cursed runtimes since the normal ones are enough to traumatize the undergrads.
- Sniffnoy 1y agoHey the asterisks in your reply got read as formatting so it's ended up messed-up.
- adgjlsfhk1 1y agooops. fixed.
- hinkley 1y agoAre BigInteger multiplications in logn² now or do they still have weird terms in them?
- adgjlsfhk1 1y agodown to nlogn