4 ms·
Isn't multiplication of two integers with length n O(nlog(n)) with the Harvey-Hoevan algorithm? Is the limitation our 64-bit computers?
by MaximumYComb 6y ago
Isn't multiplication of two integers with length n O(nlog(n)) with the Harvey-Hoevan algorithm? Is the limitation our 64-bit computers?
- wbhart 6y agoHarvey-van der Hoeven. And yes it is. But this is an asymptotic cost meaning you have to have absolutely enormous integers before the cost will be lower than the old algorithm. In fact, the crossover is so large it is quite possibly out of the range of anything we'll practically ever compute. In particular, crypto typically works with integers zillions of times smaller, so you certainly don't want the Harvey-van der Hoeven algorithm for that.