The recently proposed o(n log n) integer multiplication algorithm [pdf] (web.maths.unsw.edu.au)
32 points by craigcitro an hour ago
yaoke259 2 minutes ago
Awesome write up and intro by a fellow Sydney-sider, kept me hooked! As someone who's not a maths wizard, the technical details flew by my head but the prose allowing me to empathise deeply with those in the field was very enlightening. I never realised how big of a deal the maths dump was and how much it has shaken up the field. I guess we are all just trying to figure out this whole "intelligence on tap" thing together.
jdb1729 28 minutes ago
> The new result does not directly imply new complexity bounds for polynomial multiplication over a fixed finite field, say multiplication in F2[x]. The state of the art for this problem is an algorithm that multiplies polynomials of degree n in time O(n log n 4^log*(n)) [HvdH19].
@platypii and I obtained a Lean proof of the same improvement for DFT over prime-order finite fields (yielding polynomial multiplication via the convolution theorem): https://github.com/platypii/integer-mult-bounds-lean/blob/ma...
flebron 42 minutes ago
Note in this case the title says "O(n log n)", but the important part is this is "o(n log n)", not just "O(n log n)'. The former is a strict subset of the latter. We already knew how to multiply two n-bit integers in O(n log n) time, via the FFT.
ComplexSystems 20 minutes ago
Roughly speaking, O(n log n) means "grows no faster than k(n log n) for some k", whereas o(n log n) means grows strictly more slowly* than k(n log n) for all* choices of k.
onionisafruit 37 minutes ago
For those of us uninformed, what’s the difference between O and o?
bobmarleybiceps 15 minutes ago
Knuth originally defining them https://dl.acm.org/doi/10.1145/1008328.1008329
ruined 25 minutes ago
f(n) = O(g(n)) means as n increases, f(n)/g(n) must not grow beyond a constant
f(n) = o(g(n)) means as n increases, f(n)/g(n) must shrink
jhanschoo 3 minutes ago
theokrueger 33 minutes ago
Big O basically drops constants
O(2n+1) = O(2n) = O(n)
o(2n+1) > o(2n) > o(n)
Both define upper boundary, but big O can read like "the function is generally proportional to ___" and little o can read like "the function is never more than _____"
bobmarleybiceps 19 minutes ago
boothby 33 minutes ago
If f is O(g) and o(h) then
Lim f/g -> C a constant
Lim f/h -> 0adgjlsfhk1 2 minutes ago
appplication 29 minutes ago
Ygg2 30 minutes ago
Both are upper bounds. But small o is strictly smaller than upper bound. Big O is not greater than upper bound.
https://stackoverflow.com/questions/1364444/difference-betwe...
craigcitro 33 minutes ago
ty, fixed. (ahh, copy paste.)
ajkjk 15 minutes ago
Really enjoy the writing style here.