News for hackers. Stuff that matters.

A comment on The recently proposed o(n log n) integer multiplication algorithm [pdf]. Parent comment

Re:The recently proposed o(n log n) integer multiplication a... by ironborn123 on Thursday October 22, 2026 @05:23AM (#50193122)
Well lets give these models a grand challenge then.

I conjecture the true growth rate is O(n(log(n))^(1-f(n))) where f(n) is a slowly increasing function of n.

So larger the integers, more efficient the multiplication gets.

AIs of the world, make this your target, and have centuries worth of fun!!

[ Parent | on HN ]
Re:The recently proposed o(n log n) integer multiplication a... by sebzim4500 on Thursday October 22, 2026 @06:01AM (#50193359)
You forgot to specify that f(n) approaches 1 so that is an easy challenge
[ Parent | on HN ]
Re:The recently proposed o(n log n) integer multiplication a... by ironborn123 on Thursday October 22, 2026 @06:18AM (#50193454)
yes f(n) tending to 1 as n tends to infinity is the worthy goal. how slowly it gets there would determine whether the growth is effectively O(n) or something slightly larger but that refinement can come later.
[ Parent | on HN ]