4 ms·
Are there any non-FFT multiplication algorithms that are faster than O(n^2)? I wonder if you could try to find a systematic way of 'efficiently' representing i
by soVeryTired 8y ago
Are there any non-FFT multiplication algorithms that are faster than O(n^2)?
I wonder if you could try to find a systematic way of 'efficiently' representing integers that is amenable to multiplication. Consider squaring 9999, for example. The standard algorithm decomposes 9999 as (9000 + 900 + 90 + 9), then uses distributivity of multiplication, which is clearly n^2 in the number of digits. However, you can achieve the same result more efficiently via 9999 = (10000 - 1), which requires fewer multiplications to square. Can efficient representations of integers be found systematically?
- klipt 8y ago> Are there any non-FFT multiplication algorithms that are faster than O(n^2)? https://en.wikipedia.org/wiki/Karatsuba_algorithm https://en.wikipedia.org/wiki/Karatsuba_algorithm
- kadoban 8y agoYes, the first one found was Karatsuba multiplication. It's based on splitting the number in about half and doing smaller multiplications. It is quite interesting to learn, the algorithm is both easy to understand and surprising in result (though less surprising if you know FFT or this result).
- soVeryTired 8y agoNice, thanks (to you and the sibling comment, who got there at the same time)