Some time ago I've read this news article, Mathematicians Discover the Perfect Way to Multiply, reporting a discovery published in 2019, where Harvey and Hoeven[1] found a algorithm able to execute multiplication in $N \log N$ steps. Compare with the $N^2$ we are used to while doing multiplication by hand.

That amused me, because I had no idea in Mathematics there was still open problems in basic arithmetic, something I took for granted, long ago settled knowledge, since childhood.

Now I wonder, did this discovery help, or could help, materials modeling? Did a code developed somewhere for this purpose made use of it. A downside of the new algorithm is a set up phase where you need to put the numbers in a suitable form, so this initial effort is paid only for large numbers. My impression is that in matter modeling our algorithms are more about multiplying lots of small numbers fast, instead of some big numbers, so I guess the answer is probably no. But I'm not sure.

If not, can someone explain in detail the impact of any of the multiplication algorithms scaling better than $N^2$, for some practical application?

[1] David Harvey, Joris van der Hoeven. Integer multiplication in time O(n log n). 2019. ⟨hal-02070778⟩

  • 10
    $\begingroup$ +1. It's for integer multiplication, not floating-point multiplication, so applications to Matter Modeling are limited, and there hasn't been much time since 2019, so it hasn't made its way into people's codes. But it's an interesting result indeed. $\endgroup$ – Nike Dattani Jun 20 '20 at 2:42
  • 9
    $\begingroup$ You can eliminate floating-point math by scaling every value to an integer first. However, even extremely precise calculations won't need so many digits to represent the resulting integers that the asymptotically faster algorithms would be faster than the practical O(n^2) algorithms.(See jpl.nasa.gov/edu/news/2016/3/16/…, for example.) $\endgroup$ – chepner Jun 20 '20 at 15:36
  • 7
    $\begingroup$ @NikeDattani, floating-point multiplication is just integer multiplication with a scaling factor. $\endgroup$ – Mark Jun 20 '20 at 23:16
  • 1
    $\begingroup$ @Mark - unfortunately it is not! Multiplication in the rational field, ℚ, is as you describe. But - floating-point multiplication has to deal with limited precision ... (just quibbling ...) $\endgroup$ – davidbak Jun 25 '20 at 16:28
  • 1
    $\begingroup$ I can't tell how useful the question is but I'm glad I stumbled on it. It was nice to have learned about the discovery of a multiplication algorithm in time O(n log n). I previously read the Wikipedia article en.wikipedia.org/wiki/F%C3%BCrer%27s_algorithm, a lower bound of O(n log n) has only been conjectured. $\endgroup$ – Timothy Dec 19 '20 at 19:41

What are the state-of-the-art algorithms for long-integer multiplication?

First let me address the point you raised about the schoolbook algorithm having $\mathcal{O}(n^2)$ scaling, by saying that this was not the state-of-the-art algorithm used in most matter modeling software. Below I give a brief overview:

(1960) Karatsuba multiplication. $\mathcal{O}(n^{1.58})$: Faster than naive multiplication after $n$ gets ~$10^{96}$.
(1963-2005) Toom-Cook-Knuth. $\mathcal{O}(n\cdot 2^{\sqrt{2\log n}}\log n)$: Generalization of Karatsuba.
(1971) Schönhage-Strassen. $\mathcal{O}(n\log n\log\log n)$: Outperforms TCK after ~$10^{10000}$.
(2007) Fürer. $\mathcal{O}(n\log n\cdot 2^{\mathcal{O}(\log^*n)})$: Outperforms SS after ~$10^{10^{18}}$.
(2015) Harvey et al. $\mathcal{O}(n\log n\cdot 2^{3\log^*n})$: Similar to Fürer's algorithm.
(2015) Harvey et al. $\mathcal{O}(n\log n\cdot 2^{2\log^*n})$: Relies on conjectures not yet proven.
(2016) Covanov-Thomé. $\mathcal{O}(n\log n\cdot 2^{2\log^*n})$: Relies on (different) conjectures not yet proven.
(2018) Harvey & van der Hoeven. $\mathcal{O}(n\log n\cdot 2^{2\log^*n})$: Finally proven without conjectures.
(2019) Harvey & van der Hoeven. $\mathcal{O}(n\log n)$: The algorithm mentioned in the paper you cited.

Which of these algorithms have practical consequences?

Schönhage-Strassen: GNU multi-precision library uses it for #s with 33,000 to 150,000 digits.
Toom-Cook: is used for intermediate-sized numbers, basically until Schönhage-Strassen is used.
Karatsuba: is a specific case of Toom-Cook: not likely used for numbers smaller than $10^{96}$.

So what are the consequences of the 2019 algorithm?

Likely nothing for the calculations we typically do. Schönhage and Strassen predicted very long ago that $\mathcal{O}(n\log n)$ would be the most efficient possible algorithm from a computational complexity point of view, and in 2019 the algorithm that achieves this predicted "lower bound" was found by Harvey and van der Hoeven. It is probably not implemented in any library, just as the 2018, 2016, 2015, and 2007 algorithms are also not implemented anywhere as far as I know. They are all beautiful mathematics papers which give theoretical scalings, but likely have no practical consequences.

Do you ever multiply together integers with 96 digits? Typically in double-precision floating point arithmetic we multiply numbers with no more than 18 digits, and in quadruple-precision arithmetic (which is indeed used in matter modeling for things like numerical derivatives in variational energy calculations, but quite rarely) numbers have up to 36 digits, but it is unlikely that anyone in matter modeling is frequently multiplying numbers with 96 digits, so even the Karatsuba algorithm is in practice worse than the schoolbook $n^2$ algorithm, due to Karatsuba involving extra shifts and additions as overhead. The Toom-Cook algorithms (such as Karatsuba) are useful in number theory, and in fact we use them every day when we do e-banking or when we use GitHub involving RSA keys, since RSA numbers are hundreds or thousands of digits long. The Schönhage-Strassen is used mainly in number theory for things like calculating record numbers of digits in $\pi$, and for practical applications such as multiplying polynomials with huge coefficients.

Conclusion: The 2019 algorithm for integer multiplication does not affect real-world applications.

  • 15
    $\begingroup$ Nice summary. A good reminder that $\mathcal{O}$ notation can hide large constant coefficients, making theoretical algorithms impractical for most common use cases. $\endgroup$ – davidbak Jun 20 '20 at 20:08
  • 4
    $\begingroup$ @PeterCordes The correct numbers are: $n=2^{320} \approx 10^{96}$ for Karatsuba overtaking schoolbook algorithm, 1728-7808 64-bit words (about 30,000-150,000 digits) for the GNU implementation of Schönhage-Strassen, and $n=2^{2^{64}} \approx 10^{10^{18}}$ for Fürer's algorithm overtaking Schönhage-Strassen. $\endgroup$ – Nike Dattani Jun 21 '20 at 4:58
  • 5
    $\begingroup$ In other words, it's a galactic algorithm. $\endgroup$ – J.G. Jun 21 '20 at 22:18
  • 3
    $\begingroup$ @J.G. Same with you, if you're able to perhaps write an answer about galactic algorithms such as the Coppersmith–Winograd algorithm for matrix multiplication (which is actually quite related to the question!). $\endgroup$ – Nike Dattani Jun 22 '20 at 1:17
  • 3
    $\begingroup$ @NikeDattani Sure. I've posted a hopefully useful answer. $\endgroup$ – J.G. Jun 22 '20 at 7:16

This $O(n\ln n)$ integer multiplication algorithm is a galactic algorithm, meaning that it won't be used despite being "of lower complexity" because it only becomes more efficient than existing algorithms for problems vastly larger than any relevant to us in practice. The problem is big-$O$ notation only tells us how the algorithm behaves for sufficiently large $n$, whereas values of $n$ that will come up in practice will see a much worse behaviour. Section 5 of their paper explains:

In this section we present the main integer multiplication algorithm. We actually give a family of algorithms, parameterised by a dimension parameter $d\geqslant2$. Let $n_0 := 2^{d^{12}}\geqslant 2^{4096}$, and suppose that we wish to multiply integers with $n$ bits. For $n < n_0$, we may use any convenient base-case multiplication algorithm, such as the classical $O(n^2)$ algorithm. For $n\geqslant n_0$ 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\geqslant1729$.

In other words, it's only worth using the new algorithm to multiply numbers with at least $\geqslant2^{1729^{12}}$ bits. (For integer multiplication, the problem size $n$ is how many bits the larger integer has, not the integer itself; but even this number would have to be so large for the algorithm to be worthwhile I'll find it useful to discuss its number of digits, in base $10$.) This number of bits has more than $2\times 10^{38}$ digits in base $10$. A computer using every subatomic particle in the observable universe to store one bit of data can only store a number of bits of data whose number of digits is well under $100$. So there's no chance anyone would ever have a machine capable of such multiplication regardless of algorithm. The paper notes that smaller problems should just be done with existing algorithms.

Why does $1729$ come up here? Because a $1729$-dimensional Fourier transform is used. I'm sure within a few years there will be a tweaked version that brings that number down, allowing smaller problems to be multiplied in $O(n\log n)$ time. But even if we only require $d=2$ so $n_0=2^{2^{12}}$, that's still a number with $1234$ digits in base $10$, far more than the aforementioned $100$. For what it's worth, the paper sketches a route to using $d=8$, in which case $n_0$ would have over $2\times10^{10}$ digits.

As my link to Wikipedia notes, other kinds of multiplication have also encountered galactic algorithms, such as gradual improvements to the Coppersmith–Winograd algorithm for matrix multiplication.

  • 4
    $\begingroup$ Ramanujan was right, 1729 is a very interesting number. $\endgroup$ – James K Jun 22 '20 at 16:57
  • $\begingroup$ So even the minimum number of (base 10) digits where this algorithm starts to win (maybe: depends on the constants) can barely be represented in an IEEE float (and even then not exactly) - you need a double? (Range for IEEE single precision float: ±1.18×10<sup>−38</sup> to ±3.4×10<sup>38</sup>) $\endgroup$ – davidbak Jun 22 '20 at 17:51
  • $\begingroup$ @JamesK - I have not corresponded with the authors but 1729 is pulled out of thin air (subject to a constraint) - a quote from the paper: "In Section 5, we will simply take d := 1729 (any constant larger than K would do)." (page 7) So in fact I wouldn't be surprised if they chose 1729 over other possibilities precisely because Ramanujan thought it was interesting! $\endgroup$ – davidbak Jun 22 '20 at 18:18
  • 2
    $\begingroup$ @davidbak Yes and no. With some optimizations any $d>8$ would do, but the simplest version requires $d>1728$. But since $d$ is required to be a dimension, it has to be an integer. See also Sec. 5.4, and the discussion of Eq. (1.3). $\endgroup$ – J.G. Jun 22 '20 at 18:24
  • $\begingroup$ I think you got it wrong in terms of estimating what a computer can calculate. $2^{x}$ numbers requires $x$ bits. An average home computer can store numbers over $x^{1024^{4}}$, it is equal to 1 GB $\endgroup$ – Ilya Gazman Jun 24 '20 at 15:57

To take a slight detour, we can also look at the progress of matrix multiplication algorithms. As mentioned in a few comments here, standard matrix multiplication is $O(n^{3})$ and any exact method for a general matrix is going to require $O(n^{2})$ operations just to process all the elements of initial matrices. Over the last 50 years, different methods have been developed to reduce the exponent, often denoted $\omega$. These could in principle be very useful for matter modeling, as a number of electronic structure and molecular dynamics methods rely on matrix multiplication and matrix operations which have been shown to scale the same (determinant, inversion, Gaussian elimination) or in a way expressible in terms of $\omega$ (eigenvalues). 

The simplest such approach, and thus the most likely to be applied in practice, is the 1971 Strassen Algorithm, which has $O(n^{\log_2(7)})=O(n^{2.804...})$ scaling. It achieves this by recursively breaking the initial matrices into 4 blocks and storing intermediate quantities such that you can perform 7, rather than the typical 8, block multiplications. 

Fairly recent studies suggest that the crossover point where it becomes more efficient than standard matrix multiplication is somewhere between $n=512$ and $n=1024$ (the method works best with widths that are powers of two due the repeated splits into 4 blocks), which are not unreasonable sizes to encounter in a large molecular electronic structure calculation. In practice, the better scaling in general is traded for greater speed for specific cases by setting a threshold size below which the recursion is stopped and replaced with standard matrix multiplication. I don't know off hand of any program that actually uses this method, but it seems like it would be simple addition and could produce tangible speedups for larger systems.

The last significant improvement was the 1990 Coopersmith-Winograd Algorithm, which scales as $O(n^{2.376...})$. The algorithm is much more complicated than the original Strassen algorithm; the proof of the scaling relates the rank of a particular trilinear form of tensor products to $\omega$. This complexity manifests in a very large prefactor, making the method much slower than the Strassen method or standard matrix multiplication. The impractically large matrices needed to reach the crossover threshold for these later approaches has led them to be referred to as galactic algorithms.

These later approaches currently have no use in matter modeling (or really any practical application), but could have significance in the long run. While the current thread of research has focused on proving a lower bound for $\omega$, this work could provide the impetus for producing more practical algorithms by proving that better scaling than the standard algorithm is possible.

  • 2
    $\begingroup$ @NikeDattani I have always thought this was an interesting topic and wanted the opportunity to explore it more. $\endgroup$ – Tyberius Jun 23 '20 at 18:44

Can someone explain in detail the impact of any of the multiplication algorithms scaling better than N2, for some practical application?

An actual application is right in front of our eyes: digital signature using RSA. If I click on the lock icon for the present page in my browser, then on the arrow on the right of Connection secure, then More Information, then View Certificate, I see that the connection uses this RSA-2048 public key: public key This means that at each new connection, the browser performs modular arithmetic with 2048-bit integers, that is 616-decimal digit integers.

In order to authenticate the server (or, in a previous operation, to check its certificate, which must be done at least once on the first connection), it is computed A65537 mod M for the 2048-bit M in the picture, and A of the same size. Since 65537 = 216+1, that requires 17 modular multiplications. Each can be (and often is) performed by multiplying two 2048-bit integers into a 4096-bit integer, followed by modular reduction by way of an other multiplication of 2048-bit integers.

That arithmetic is performed using limbs (the equivalent of decimal digits) that typically are 32-bit (sometime 64-bit, or 16-bit on low-end mobile devices). It is thus performed multiplication of integers of width N = 64 limbs. With the schoolbook algorithm, each multiplication requires N2 multiplications of two limbs and additions of the result, each requiring in the order of 50 CPU clock cycles. At 1 GHz, we are talking 17×2×64×64×50×10-9 s that is ≈7 ms, which is not negligible because establishing an https connection (or checking a certificate) is so common.

In order to reduce delay and power consumption, it pays to use at least the simplest of the below-O(N2) multiplication algorithms: Karatsuba multiplication, which is O(N≈1.6). There is a threshold before that pays (especially on modern CPUs with fast multipliers), which can be down to about 10 limbs (reference). For 64×64 limbs, Karatsuba would typically reduce computing time by a factor of nearly (4/3)2 ≈ 1.7, which is better than nothing. That's part of why implementations based on GMP are faster. For low-end devices with 16-bit limbs, or when doing 4096-bit RSA, that's a factor (4/3)3 ≈ 2.3, and quite worth using.

On the server side, there are more computations (about 50 times more work) and that can sometime represent a sizable fraction of the total workload, but the incentive to use Karatsuba for the bulk of the work is actually lower: the numbers manipulated are half as wide, and sometime the limbs are bigger.

There are other applications of Karatsuba and its generalization Toom-Cook in cryptography, not limited to RSA; e.g. batch verification of ECC signatures, see Daniel J. Bernstein's Batch binary Edwards. In the specialized subfield of cryptanalysis, there even are uses of Schönhage-Strassen, e.g. cryptanalysis of ISO 9796-2 signatures. It's in GMP for a reason.

The recent Harvey-Hoeven algorithm is a satisfying achievement, but is not going to be used in practical applications. I even doubt that it can ever be implemented: it seems to work for numbers in the order of 172912 bits, which is about 1022 times the RAM in a current supercomputer.

  • $\begingroup$ +10. fgrieu has arrived! $\endgroup$ – Nike Dattani Jun 27 '20 at 21:33
  • 3
    $\begingroup$ Wow this is such a great answer! It's awesome to see how these algorithms are important, even if currently inapplicable to matter modeling. It adds a lot to the discussion by means of a detailed example. $\endgroup$ – Cody Aldaz Jun 27 '20 at 22:01
  • 3
    $\begingroup$ This might be a typo. "when doing 4096-bit RSA, that's a factor of (4/3)^2≈2.3". But (4/3)^2≈1.7 as mentioned earlier in your answer. $\endgroup$ – Rashid Rafeek Jun 28 '20 at 5:24
  • 2
    $\begingroup$ @Rashid Rafeek : typo indeed, fixed, thanks for the report. $\endgroup$ – fgrieu Jun 28 '20 at 5:30
  • 1
    $\begingroup$ Yes, definitely. I mostly objected to the suggestion that memory access could explain a large cost. CPUs these days either have caches, or they're clocked so low that memory access is cheap-ish. I think Karatsuba wins because it reduces the amount of ALU work needed, and that's the dominant factor for most BigInteger functions. $\endgroup$ – Peter Cordes Jun 29 '20 at 2:25

Even the simplest better-than-schoolbook (O(n^2)) algorithms like Karatsuba are only useful in practice for large n. But what is n? It's not single bits, and it's not decimal digits. (Posting this tangent as requested in comments.)

Software implementations of an extended-precision multiply algorithm work in integer chunks as wide as the hardware provides. On a 64-bit CPU, that's usually 64x64 => 128-bit integer multiplication, e.g. the x86-64 mul instruction. (@fgrieu's answer has more detail on this, including the term "limb" for such a chunk.)

That fixed-width CPU instruction runs in fixed time (regardless of the value on most CPUs; division is the only instruction that's slow enough to justify variable latency in a modern pipelined CPU, and in the most recent x86-64 CPUs even it's constant). e.g. on modern Intel and AMD CPUs, mul r64 or mulx have a throughput of 1 per cycle and a latency of 3 to 4 cycles (for the low and high halves of the output, respectively: https://www.uops.info/html-instr/MUL_R64.html).

Hardware doesn't "know" it's doing one big multiply, it's just doing each fixed-width part separately. Hardware can easily be parallel (adding partial products) if you can throw enough transistors at the problem. HW multipliers in CPUs use the Dadda tree design. This is simpler than doing 63 additions of shifted versions of the other 64-bit input (or 0 where this input has a 0 bit) using normal adders: carry propagation can be deferred. Hardware tricks like that are AFAIK unrelated to any of the sub-N^2 algorithmic tricks.

Such a multiply instruction, and add-with-carry, are the building blocks for schoolbook multiplication's O(n^2) time complexity. e.g. 128-bit multiplication (producing a 128-bit result) takes 3 multiplies on x86-64: https://godbolt.org/z/qBAbfQ. To also produce the high half, all of those multiplies would have to be "full" 64x64=>128 instead of only 64x64 => 64 for the low x high and high x low cross products, and we'd need to do the high x high product, for a total of 4 mul instructions.

e.g. this SO answer shows 32x32 => 64-bit multiply using 16-bit x86 so each input is 2 limbs, and the output is 2+2 = 4 limbs, requiring 2*2 = 4 multiplies of 16x16 => 32 bits each. Exactly the same pattern would apply for 64x64 => 128 on a 32-bit machine, or 128x128 => 256 on a 64-bit machine.

Since that building block is opaque to software, and/or shuffling individual bits around would be much more expensive than it's worth, n is only 64 for 4096-bit integer multiply.

To allow better instruction-level parallelism (letting superscalar CPUs do the same work in less time) and reducing overhead of mov instructions, Intel introduced (in Broadwell) the ADX extension that allows two parallel dependency chains of add-with-carry. This whitepaper shows the advantages it gives for small problems (like 512-bit x 512-bit multiplication (8 x 8 limbs)).

For floating-point, an FP multiplier involves an integer multiplier for the 53x53-bit => 53-bit correctly rounded mantissa (the most significant 53 bits of the full integer product) plus hardware to add the exponents, and check for / handle overflow / underflow and NaN. See Why does Intel's Haswell chip allow floating point multiplication to be twice as fast as addition? for some info about how FP ALUs are designed, and the barely-related question of why Intel made the design choices they did in Haswell and Skylake.

To get extra FP precision, one technique is so-called "double-double": wide mantissa using two doubles, but only the exponent from one of them. Using that only takes a handful of double-precision math operations, like 6 to 20 depending on which operation and whether FMA (fused multiply-add without intermediate rounding) is available. The relevant width is n=2 doubles, not n=36 decimal digits. (And IEEE FP is a binary format, not decimal, although there are decimal FP formats that exist, with some CPUs even having hardware support for them, such as PowerPC.)

Note that a SIMD multiplier just replicates that for each SIMD element. double-double can SIMD efficiently if you store separate vectors of lo / hi halves so you don't need to shuffle to line up the corresponding halves of a single number. e.g. this Q&A.

Other extended-precision number representations

You could store numbers as an array of bytes, each byte holding a single decimal digit. But that's pretty terrible. Historically, it was not uncommon to use a simplistic format like that, especially for a score counter in a game that gets printed on screen in decimal format constantly. Or BCD (2 decimal digits per 8-bit byte, each in a separate 4-bit nibble).

But this is pretty bad, especially for multiplying numbers stored in this format, because then n becomes large and complexity scales with N^2 (for the simple schoolbook algorithm).

@davidbak commented:

w.r.t. "nobody uses decimal digits as an extended-precision format" - is that true? I know there used to be implementations of multi precision integer arithmetic that used the largest power of 10 that would fit in a word as the base - e.g., 10^9 for 32-bit machines. Made conversions to<->from a human-readable base 10 notation much easier and cost only a "reasonable" overhead for some definition of reasonable that might depend on your use case. Is that not done anymore? (Although strictly speaking those aren't decimal digits, just power-of-ten digits...)

Indeed, larger powers of 10 could be sane when you need frequent conversion to/from a decimal string, or multiply/divide by powers of 10. But then a 36-digit number is 4 chunks of 9, not 36 chunks of 1. e.g. one use-case was printing the first 1000 decimal digits of Fib(10^9) (x86-64 asm code-golf) where it's handy to have right shift by 1 limb be division by a power of 10, and for conversion to decimal to only need to consider the current limb, converting that to 9 decimal digits without having to do extended-precision division where the remainder depends on all higher bits.

See also this code-review answer about an implementation based on single decimal digits. I included some details about what CPython does, and some other links. It's not rare for beginners to come up with that as an idea, but non-toy libraries use at least 10^9 as the base for "limbs", unless we're talking about BCD.

Or more commonly binary extended precision using all 32 bits per 32-bit integer, or sometimes only 2^30 to leave room for high-level language handling of carry in/out (like in CPython) without access to an asm carry flag.

Another advantage of leaving some spare bits per limb is to allow deferred carry normalization, making SIMD for addition efficiently possible. See @Mysticial's answer on Can long integer routines benefit from SSE?. Especially for extended-precision addition, leaving some slack in each limb is actually interesting if you design around that format with awareness of when to normalize as an extra step. (@Mysticial is the author of y-cruncher and also works on Prime95; he implemented its use of FP-FMA to take advantage of the FP mantissa multipliers for bit-exact integer work.)

That answer also points out that "really large bignum" multiplications can be done as an FFT.

Normally (with standard techniques) it's very hard to take advantage of SIMD for extended-precision; within one operation, there's a serial dependency between each element: you don't know if there's carry-in to this element until you process the previous element (for addition).

For multiplication, it's usually even worse: SIMD doesn't usually have very wide multipliers, and with the result being twice as wide as the inputs it's a problem where to put them.

The amount of work done by one building block should be measured as the "product bits" you compute per cycle, e.g. 64x64 => 128-bit full multiply does 64x64 = 4096 units of work. But a 4x 32x32=>64-bit SIMD multiply (like AVX2 vpmuludq) does 32^2 = 1024 units of work per element, with 4 elements, for a total of 4096 units of multiply work. And it leaves more adding of partial products not done. So even in theory, ignoring other factors, AVX2 vpmuludq on a 256-bit vector is break-even with scalar.

AVX512 has 64x64 => 64-bit multiply (but still no way to get the upper-half of the full result so it's no more helpful for BigInteger than 32x32 => 64, I think). AVX512IFMA more directly exposes what the FP mantissa multipliers can do, providing separate low and high half 52x52 => 104-bit multiply.

(Other SIMD integer multiply instructions like vpmulld that do 32x32 => 32-bit usually decode to two separate uops for the vector-ALU ports, so they can use the same per-element multipliers as FP mantissas. But those multipliers are only 52x52 or 24x24-bit. Making them wider would cost significantly more for these wide SIMD ALUs, and only help the fairly rarely used SIMD-integer multiply instructions.)


Practical importance: compactifying explanations

It is widely believed that $\mathcal{O}(n \log n)$ is the best possible result, and therefore we no longer have to say $\mathcal{O}(n\log n\cdot 2^{2\log^*n})$ every single time in every single paper in related fields, we can just say $\mathcal{O}(n \log n)$ every time now. Here is a related quote from Reddit:

"The result is of extreme practical importance. Not for actually multiplying integers (as usual with these algorithms it's probably not faster than existing algorithms for integers that can be stored in the observable universe), but for writing papers. It has always been a hassle to write down the complexity of integer multiplication or algorithms based on integer multiplication by introducing soft-O notation, little-o exponents, epsilons greater than 0, or iterated logarithms. From now on I can just write O(n log n) in my papers and be done with it!"

While this might not be the answer you're looking for, about practical impact on computations, it does in fact answer the question of "What is the practical value of this algorithm?"

  • 3
    $\begingroup$ Rather than downvoting a brand new user, I ask you to consider editing the post to say it's practical importance is in compactifying explanations, rather than just a copy-paste answer. Otherwise I'll do it when I've finished my morning activities. $\endgroup$ – Nike Dattani Jun 25 '20 at 13:32
  • 4
    $\begingroup$ I upvoted because I nearly always approve of a sense of humor, even on the notoriously humor-impacted stack exchange sites. (In moderation, of course.) $\endgroup$ – davidbak Jun 25 '20 at 14:27
  • 3
    $\begingroup$ @davidbak Thank you, I appreciate it! When I woke up someone had downvoted, until I evened it out. I also appreciate humor, but in this case the user has also technically answered the questioned correctly, in a way that I had not expected at all. The question is "what is a practical use?" and the user has very correctly given a practical use. This might be funny but it's also correct. $\endgroup$ – Nike Dattani Jun 25 '20 at 15:35
  • $\begingroup$ In at least some contexts, they'd write $M(n)$ instead. $\endgroup$ – J.G. Jun 28 '20 at 14:11
  • $\begingroup$ True but then they have to explain what M(n) is, so the user Валерий Заподовников does have a point. $\endgroup$ – Nike Dattani Jun 29 '20 at 2:43

It is possible to multiply large numbers in time O(log n).

  • 2
    $\begingroup$ Welcome to the site! Could you elaborate further, possibly by pointing to a source for this claim? $\endgroup$ – Tyberius Nov 29 '20 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.