How on earth was it widely conjectured to be O(n log n) if nobody had an algorithm? What constitutes evidence for that?
-
-
-
I don't know the details, but Arnold Schönhage and Volker Strassen got the time down to O(n log(n) log(log(n))) with fast Fourier transform, and they conjectured that O(n log(n)) was possible. I guess if you almost do something you hope you can do it!
- 2 more replies
New conversation -
-
-
hate to break it to you guys, but it only works with numbers containing at least 2^4096 digits..
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
-
-
Fun thread for those trying to digest this.https://www.reddit.com/r/programming/comments/b5avlv/integer_multiplication_in_time_on_log_n_pdf/ …
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
-
-
It took me forever to figure out what this meant (never having heard of BigO before), but here: Multiplication of giant numbers can theoretically be done faster than multiplying each individual digit/bit by all of the digits/bits in the other number.https://www.reddit.com/r/programming/comments/b5avlv/integer_multiplication_in_time_on_log_n_pdf/ …
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
-
-
Finding an O(n log n) algo is easy, but finding one with reasonable memory constraints is difficult
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
-
-
Yikes, who'd have imagined that an operation as elementary as integer multiplication (even of large numbers) would lend itself to such rich complexity?! Good luck to whoever first tries to implement either one of the two algorithms presented in actual code!
-
Imagine having the ram for it too!
- 1 more reply
New conversation -
-
-
Fingers crossed

-
Open archive HAL, is currently down...
- 1 more reply
New conversation -
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.