Optymalny algorytm mnożenia długich liczb, np. n=1000 cyfr ma podobno złożoność nlogn - w wersji FFT.
Czy to było udowodnione kiedykolwiek?
Mam wątpliwości, bo generalnie schemat mnożenia polega na podziale liczb na grupy cyfr, np. po dwie cyfry, 3, 4 itd.
Złożoność jest tu następująca: n do potęgi log(2k-1)/logk; gdzie k = liczba cyfr w grupie.
Można sobie sprawdzić szczególne przypadki:
2: n^(log3/log2) = n^1.585 - metoda par Karatsuby
https://en.wikipedia.org/wiki/Karatsuba_algorithm
3: n^(log5/log3) = n^1.465 - Toome3
https://en.wikipedia.org/wiki/Toom%E2%80%93Cook_multiplication
4: n^(log7/log4) = n^1.40 - ?
...
8: n^(log15/log8) = n^ 1.3 - ?
itd.
jak widać możemy sobie tu zaserwować dowolnie mały wykładnik - znaczy dowolnie blisko 1, co jest na pewno szybsze od nlogn.
1000: ln(2*1000-1)/lln1000 = 1.1