8 ms·
Integer multiplication in time O(n log n) [pdf]
- amichail 8y agoThe second author of this paper created TeXmacs btw.
- williamstein 8y agoAnd the first contributed much to the large integer and polynomial multiplication code in SageMath...
- throwawaymath 8y agoThe abstract of this paper is refreshingly succinct: We present an algorithm that computes the product of two n-bit integers in O(n log n) bit operations. The result is excellent, and it closes (in the affirmative) the Schonhage-Strassen conjecture first postulated in 1971.
- hackcasual 8y agoIt establishes the upper bound, but I don't believe this paper establishes a lower bound, so the conjecture is still open (a super linear lower bound would violate the conjecture).
- deleted 8y ago[deleted]
- rincebrain 8y agoJust to be sure I understand, doesn't the conjecture postulate that O(n log n) is the lower bound, so _anything_ beneath n log n would violate it?
- lovecg 8y agoYes (technically the lower bound would be the small-o(n log n)). The conjecture is that it’s possible to do in O(n log n) time, which this paper proves, and that it’s not possible to do any faster (which is still an open problem).
- throwawaymath 8y agoYou make a good point, nice catch. Technically we don't know what the fastest possible algorithm is yet.
- burk96 8y agoI'm making my way through uni currently. I've taken a few CS classes that have touched briefly on O notation and I am currently in Calc 2. I understand bits and pieces of this but I am lost in most of the paper. What courses should I be taking to better my understanding of papers of this sort? Or alternatively, are there any online resources that could help me work my way through research papers like these?
- jacobolus 8y agoYou can learn all of these ideas on your own (by e.g. going through textbooks and doing a significant proportion of the exercises), but the guidance of a course / expert is pretty helpful. To understand computational complexity, take a course with a title like “theory of computation” or similar. https://en.wikipedia.org/wiki/Computational_complexity_theory https://en.wikipedia.org/wiki/Computational_complexity_theor... To understand linear maps, tensor products, etc., take a course (or 2–3 courses) in linear algebra. To understand various matrix decompositions, take a course in numerical linear algebra. https://en.wikipedia.org/wiki/Tensor_product https://en.wikipedia.org/wiki/Tensor_product https://en.wikipedia.org/wiki/Cholesky_decomposition https://en.wikipedia.org/wiki/Cholesky_decomposition To understand the FFT and convolutions, take a course in signal processing, maybe after a course in ordinary differential equations. https://en.wikipedia.org/wiki/Fast_Fourier_transform https://en.wikipedia.org/wiki/Fast_Fourier_transform https://en.wikipedia.org/wiki/Convolution https://en.wikipedia.org/wiki/Convolution To understand the theory of polynomial rings, take a course in abstract algebra. https://en.wikipedia.org/wiki/Polynomial_ring https://en.wikipedia.org/wiki/Polynomial_ring To understand numerical approximations and error propagation, take a course in numerical analysis. https://en.wikipedia.org/wiki/Numerical_analysis https://en.wikipedia.org/wiki/Numerical_analysis Courses in discrete math, algorithms, and complex analysis would also be helpful.
- fromthestart 8y ago>but the guidance of a course / expert is pretty helpful. From my peers I get the feeling that this is underappreciated in the tech world where many successful developers skipped college.
- jgoodknight 8y agoInteresting... what are the chances something like this gets implemented in Silicon and actually speeds up computation or is this purely of theoretical interest?
- deleted 8y ago[deleted]
- gaogao 8y agoIf the constants aren't too big, this might find use in signal processing.
- hackcasual 8y agoThe constants are massive. Like billions of digits.
- _0ffh 8y agoFor actual silicon, this does not seem like a relevant result. I think there are already time O(log n) multiplier circuits out there. Edit: A typical imul will probably be no more than O(n), just to add something less speculative.
- wbhart 8y agoThe big-oh notation is an asymptotic notation, so it is meaningless to describe an imul as being O(n). Given that an imul is doing 64x64 bit multiplications, it is almost a tautology to say it can be done in a constant times 64 ops/cycles.
- _0ffh 8y agoThat was not what I was trying to say, wrong as I may still be. I meant to talk about nxn bit multiplication. If you scale n then, given the same basic architecture, you will also scale the circuit delay. When the delay scales linearly with the number of bits, I'd call that architecture O(n) in time. To me that seems to make intuitive sense, even though I might have that wrong. The term imul I used merely as a short hand for integer multiplication. I was not alluding to any specific architecture or width, there are plenty of CPU architectures out there using that mnemonic.
- lifthrasiir 8y agoFor whoever wondering about the practicality of this algorithm, no, at least for now. Constants aside, the algorithm currently requires an enormous cutoff for the recursion (anything below that should be handled by traditional algorithms): > Let `n0 := 2^(d^12) >= 2^4096`, and suppose that we wish to multiply integers with n bits. For `n >= n0` we will describe a recursive algorithm that reduces the problem to a collection of multiplication problems of size roughly n^(1/d). We will show that this algorithm achieves `M(n) = O(n log n)`, provided that `d >= 1729`. (p. 33) 2^(1729^12) ~= 10^(2.15 * 10^38). The authors do note the possibility of much lower cutoff: > In this section we outline a number of such modifications that together reduce the constant to `K = 8 + epsilon`, so that the modified algorithm achieves `M(n) = O(n log n)` for any `d >= 9` (rather than `d >= 1729`). (p. 39) Here 2^(9^12) has about 85 billion decimal digits. Much smaller, but still too big to be practical.
- wbhart 8y agoThere are practical problems in pure mathematics that require multiplication of numbers with 85 billion digits. For example, polynomial multiplication can be reduced to integer multiplication, and certain problems, such as computing congruent numbers or class numbers of quadratic number fields can be reduced to that. Naturally the authors of the paper do not make any claims about the algorithm being practical though.
- lifthrasiir 8y agoYeah, the recent pi calculation amassed 31.4 trillion decimal digits (or about 10^15 binary digits) of the computation load, which would definitely include the integer multiplication of numbers with the comparable size among others. I'm not sure though, because the currently widespread algorithm (Schönhage-Strassen) is practically within two orders of magnitude from O(n log n) [1] and the previous record holder (Fürer's) had been proved extremely infeasible. Also note that 85 billion digits do not relate to the constant itself: it is the lower bound that the new algorithm can make difference, otherwise it reduces to the base case. I'm not really qualified to determine the expected constant of this algorithm though, so it might actually prove feasible. [1] Its time complexity is O(n log n * log log n). The double logarithm is already slowly growing; log log 2^(10^15) ~= 34 for the reference. At this stage the constant is much more important than the time complexity itself. y-cruncher, a record-setting pi computation software, actually has a set of proprietary algorithms [2] optimized for modern hardwares. [2] http://www.numberworld.org/y-cruncher/internals/multiplication.html http://www.numberworld.org/y-cruncher/internals/multiplicati...
- nraynaud 8y agoTangential question: how does single cycle multiplication works in arm cortex processors? Do they just run the ALU clock fast enough that the multiplication finishes in one visible core cycle or is there a binary trick?
- hatsunearu 8y agoAny binary operation (subject to the usual "well behaved" caveat) can be split up into any number of steps; this is called pipelining. In fact there's not really a reason why multiplication isn't a single cycle step, other than speed and energy efficiency. The maximum clock speed of an operation is limited by how fast a change in the input can be propagated into the correct change in output. You can get around this by splitting the operation into multiple mini-steps (pipelining) and clocking it to as fast as the slowest stage will go.
- _0ffh 8y agoThe paper applies to integer multiplication on a Turing machine. Actual digital circuits are not bound to that constraint.
- wbhart 8y agoIs there a known example of something a digital computer can do that a Turing machine cannot?
- your-nanny 8y agooverheat.
- Retra 8y agoTuring machines can simulate any other machine, but they can't do what any machine can do. You can simulate a toaster, but only a real machine can actually make toast.
- pmiller2 8y agoIn terms of computational power, real computers (ignoring physics) are linear bounded automata, which is a class of automata strictly weaker than Turing machines. Throwing physics into the mix means they’re unreliable computing devices.
- moab 8y agoThis very recent paper shows a matching (conditional) lower bound of \Omega(n\log n): https://arxiv.org/abs/1902.10935 https://arxiv.org/abs/1902.10935 (the hardness is from a conjecture in network coding).
- davidivadavid 8y agoVery interesting. I was just wondering what the lower bound could be (beyond O(n) which seems fairly obvious, even though as a hobbyist I'd be hard pressed to even prove that).
- hhmc 8y agoIt's coincidentally pleasing that the cutoff `d >= 1729` is the Hardy-Ramanujan number.
- soVeryTired 8y agoAre 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)
- tombert 8y agoWow, I learned something today; I had always thought of integer multiplication as a constant-time operation. This is why I love computer science, no matter how much I think I know, I can feel like an idiot a day later.
- pragmaticpandy 8y agoIf by integer you mean the four or so bytes that many languages use to represent a (bounded) int, then it is indeed constant. This is often the context in software engineering.
- tombert 8y agoI'm somewhat interested in compiler and computation theory, so this is why it was a surprise to me.
- davidivadavid 8y agoFor some reason, a lot of people seem to think that operations that have a low level implementation (e.g. basic instruction in some ISA) are O(1).
- SilasX 8y agoA little frustrated here: I was just trying to get background on how fast int-multiplication is and what the fastest algorithms are (and whether this is an advancement), but the Wikipedia article on this topic barely mentions Big-O. https://en.wikipedia.org/wiki/Multiplication_algorithm https://en.wikipedia.org/wiki/Multiplication_algorithm