The recently proposed o(n log n) integer multiplication algorithm [pdf]

▲ The recently proposed o(n log n) integer multiplication algorithm [pdf](web.maths.unsw.edu.au)

26 points by craigcitro an hour ago | 14 comments

▲ jdb1729 18 minutes ago | parent | next [-]

> 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 32 minutes ago | parent | prev | next [-]

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 10 minutes ago | parent | next [-]

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 27 minutes ago | parent | prev | next [-]

For those of us uninformed, what’s the difference between O and o?

▲ bobmarleybiceps 5 minutes ago | parent | next [-]

Knuth originally defining them https://dl.acm.org/doi/10.1145/1008328.1008329

▲ theokrueger 23 minutes ago | parent | prev | next [-]

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 9 minutes ago | parent [-]

that's not the convention I know... (from CLRS algorithms book).

Big O is sort of like <=. little o is sort of like <.

https://dl.acm.org/doi/10.1145/1008328.1008329

	▲	npinsker a minute ago \| parent [-]
		Yeah, GP is a bit off. 'O(n)' is: "there exists a K such that, for sufficiently large n, K * n is always larger". 'o(n)' is: "for every K, for sufficiently large n, K * n is always larger".

▲ ruined 15 minutes ago | parent | prev | next [-]

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

▲ boothby 22 minutes ago | parent | prev | next [-]

If f is O(g) and o(h) then

  Lim f/g -> C a constant

And

  Lim f/h -> 0

	▲	appplication 19 minutes ago \| parent [-]
		Lmao! If someone is asking the difference between big and little o notation this is absolutely not the right way to clarify it. If you were joking then maybe you got me

▲ Ygg2 20 minutes ago | parent | prev [-]

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 23 minutes ago | parent | prev [-]

ty, fixed. (ahh, copy paste.)

▲ ajkjk 5 minutes ago | parent | prev [-]

Really enjoy the writing style here.