Integer multiplication is a cool rabbit hole, as we still don’t know how fast an optimal multiplication algorithm is. Optimality here concerns the number of single-bit operations, so adding two n-bit numbers costs O(n) operations.
Counting this way, multiplications seems to take at least quadratic time, since we have n shifts and n additions to perform in the worst case, no? The surprising answer is no, it can be done faster using Karatsuba’s algorithm. In fact, we know of quasilinear algorithms (Schönhage-Strassen) and suspect that it is asymptotically optimal, however nobody has proven it yet.
Your statement is not completely correct. Schönhage and Strassen (1971) only formulated the conjecture that the multiplication time was Θ(n log n), but their algorithm, published in the same year, had the higher complexity O(n log n log log n).
It took 48 years until 2019 for Harvey and van der Hoeven to present their multiplication algorithm that in fact has complexity O(n log n), which can be assumed to be asymptotically optimal if you think the Schönhage-Strassen-conjecture is correct.
However, Landau symbols hide a lot of things. Not only do we have multiplicative constants that make a big difference, there are multiple assumptions in the derivation of the algorithm that assume the involved integers to be larger than a certain number. Thus, even though we may have reached an optimal bound, there’s still a lot of room for improvement. Additionally, the advantages of the Harvey-van-der-Hoeven-algorithm over the Schönhage-Strassen-algorithm only pan out for numbers larger than even feasably representable in today’s computers, which is the reason why Schönhage-Strassen is still considered state-of-the-art.
Another deeper rabbit hole is the variation of so-called “complexity models”. The standard model is that of the multitape Turing machine, and one often sees Boolean circuits as well, but there are other models. When I lean back and gaze at the stars, I sometimes imagine other alien lifeforms that might have much more efficient algorithms for the pendant of integer multiplication given they have different computational architectures to work with.
To give a bit of a relation and food for thought regarding complexity conjectures, Kolmogorov conjectured in 1956 that the integer multiplication had a complexity of Θ(n²), which was quickly proven to be wrong by Karatsuba.
To me that’s also the part that makes me think it’s not worth implementing it for most systems, as this leads to diminishing returns pretty quickly. Karatsuba’s algorithm is fast enough and even that is not exactly for small numbers.
It’s a smooth transition to a galactic algorithm. Things really started to take off with Fürer’s algorithm in 2007 and Schönhage-Strassen is actually comfortably in the realm of positive yields in today’s computing, which is why I wouldn’t call it a galactic algorithm, indeed.
A fun thing about this is that while most of us write for CPUs with a multiply instruction, this is one hop away from ways you implement fancier operations used in cryptography like elliptic curve multiplication for ECC or modular exponentiation for RSA or DH. For modular exponentiation, you can square-and-multiply, that is repeatedly square a number instead of doubling and then multiply some of the results together instead of adding them. For elliptic curves, you can repeatedly double and add, but “addition” is defined differently. (Wikipedia mentions faster ways for both but those basic methods get the right result.) Unlike with plain multiplication/division, those operations don’t have a known fast, general way to compute the inverse, which is why they’re interesting for cryptography.
That does not mean go implement your own crypto, but it is cool that at least that one piece of what crypto libraries are doing is relatively accessible using our intuitions about regular old arithmetic. And if someone more informed about this wants to fill in details go for it–just trying to give a general impression of the similarities.
Integer multiplication is a cool rabbit hole, as we still don’t know how fast an optimal multiplication algorithm is. Optimality here concerns the number of single-bit operations, so adding two n-bit numbers costs O(n) operations.
Counting this way, multiplications seems to take at least quadratic time, since we have n shifts and n additions to perform in the worst case, no? The surprising answer is no, it can be done faster using Karatsuba’s algorithm. In fact, we know of quasilinear algorithms (Schönhage-Strassen) and suspect that it is asymptotically optimal, however nobody has proven it yet.
Your statement is not completely correct. Schönhage and Strassen (1971) only formulated the conjecture that the multiplication time was Θ(n log n), but their algorithm, published in the same year, had the higher complexity O(n log n log log n).
It took 48 years until 2019 for Harvey and van der Hoeven to present their multiplication algorithm that in fact has complexity O(n log n), which can be assumed to be asymptotically optimal if you think the Schönhage-Strassen-conjecture is correct.
However, Landau symbols hide a lot of things. Not only do we have multiplicative constants that make a big difference, there are multiple assumptions in the derivation of the algorithm that assume the involved integers to be larger than a certain number. Thus, even though we may have reached an optimal bound, there’s still a lot of room for improvement. Additionally, the advantages of the Harvey-van-der-Hoeven-algorithm over the Schönhage-Strassen-algorithm only pan out for numbers larger than even feasably representable in today’s computers, which is the reason why Schönhage-Strassen is still considered state-of-the-art.
Another deeper rabbit hole is the variation of so-called “complexity models”. The standard model is that of the multitape Turing machine, and one often sees Boolean circuits as well, but there are other models. When I lean back and gaze at the stars, I sometimes imagine other alien lifeforms that might have much more efficient algorithms for the pendant of integer multiplication given they have different computational architectures to work with.
To give a bit of a relation and food for thought regarding complexity conjectures, Kolmogorov conjectured in 1956 that the integer multiplication had a complexity of Θ(n²), which was quickly proven to be wrong by Karatsuba.
You buried the cool part about Schönhage–Strassen algorithm that it’s an example of Galactic algorithms. :)
To me that’s also the part that makes me think it’s not worth implementing it for most systems, as this leads to diminishing returns pretty quickly. Karatsuba’s algorithm is fast enough and even that is not exactly for small numbers.
Yeah for sure. I guess the point is that it’s cool and wholly impractical.
I think the sibling comment by FRIGN implies that the Harvey and van der Hoeven algorithm is the Galactic algorithm, not Schönhage–Strassen?
It’s a smooth transition to a galactic algorithm. Things really started to take off with Fürer’s algorithm in 2007 and Schönhage-Strassen is actually comfortably in the realm of positive yields in today’s computing, which is why I wouldn’t call it a galactic algorithm, indeed.
A fun thing about this is that while most of us write for CPUs with a multiply instruction, this is one hop away from ways you implement fancier operations used in cryptography like elliptic curve multiplication for ECC or modular exponentiation for RSA or DH. For modular exponentiation, you can square-and-multiply, that is repeatedly square a number instead of doubling and then multiply some of the results together instead of adding them. For elliptic curves, you can repeatedly double and add, but “addition” is defined differently. (Wikipedia mentions faster ways for both but those basic methods get the right result.) Unlike with plain multiplication/division, those operations don’t have a known fast, general way to compute the inverse, which is why they’re interesting for cryptography.
That does not mean go implement your own crypto, but it is cool that at least that one piece of what crypto libraries are doing is relatively accessible using our intuitions about regular old arithmetic. And if someone more informed about this wants to fill in details go for it–just trying to give a general impression of the similarities.