When multiplying two numbers with each other, which are $n$-bit numbers, there are several algorithms like the one of Karatsuba ($O(n^{\log_2 3})$) and a new one doing it even better (Harvey - Van der Hoeven) with a complexity of $O(n \cdot \log n)$, which is much better, of course.

My question is now, if we a given a number $x$ and $m$ numbers $y_1, \ldots, y_m$, is there a faster algorithm than $O(m \cdot f(n))$, where $f(n)$ is the complexity of the fastest multiplication algorithm for just two numbers?

  • $\begingroup$ "and a new one"? which one? what is your unit of computation? what is $n$? $\endgroup$
    – kodlu
    Oct 31, 2023 at 11:55
  • 3
    $\begingroup$ I assume the "new one" refers to the Harvey–Van der Hoeven algorithm. $\endgroup$ Oct 31, 2023 at 11:59
  • $\begingroup$ I adapted the question accordingly. Many thanks for your input. $\endgroup$
    – tobias
    Oct 31, 2023 at 12:28
  • 1
    $\begingroup$ I don't know your exact algorithmic cost model, but this should be relevant. $\endgroup$ Oct 31, 2023 at 18:52
  • 2
    $\begingroup$ David Harvey. Joris van der Hoeven. "Integer multiplication in time $O(n\log n)$." Ann. of Math. (2) 193 (2) 563 - 617, March 2021. doi.org/10.4007/annals.2021.193.2.4 projecteuclid.org/journals/annals-of-mathematics/volume-193/… $\endgroup$ Oct 31, 2023 at 22:53


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.