22
$\begingroup$

This question is inspired by article Alexander Shen "Gauss multiplication trick?" (Russian, "Mathematical Enlightenment", 2019).

Dasgupta, Papadimitriou, Vazirani, Algorithms (2008) Ch. 2:

The mathematician Carl Friedrich Gauss (1777–1855) once noticed that although the product of two complex numbers $$(a + bi)(c + di) = ac − bd + (bc + ad)i$$ seems to involve four real-number multiplications, it can in fact be done with just three: $ac$, $bd$, and $(a + b)(c + d)$, since $$ bc + ad = (a + b)(c + d) − ac − bd.$$ ⟨...⟩ this modest improvement becomes very significant when applied recursively.

Moore, Mertens, The Nature of Computation (2011):

The first $O(n^{\log_2 3}$) algorithm for multiplying $n$-digit integers was found in 1962 by Karatsuba and Ofman [447]. However, the fact that we can reduce the number of multiplications from four to three goes back to Gauss! He noticed that in order to calculate the product of two complex numbers, $$(a + bi)(c + di) = (ac − bd) + (ad + bc)i$$ we only need three real multiplications, such as $ac$, $bd$, and $(a + c)(b + d)$, since we can get the real and imaginary parts by adding and substracting these products. The idea of [447] is then to replace $i$ with $10^{n/2}$, and to apply this trick recursively.

Another books explaining "Gauss trick" give references to the Donald E. Knuth, The Art of Computer Programming, Vol. 2 and 3. But there are no words "Gauss trick" in Knuth's books.

Q: Does this trick really belong to Gauss or this situation is a reminiscence of FFT which was known to Gauss and rediscovered by Cooley and Tukey?

$\endgroup$
  • 3
    $\begingroup$ I'm not sure what you're really asking. Yes, it seems Gauss discovered this "trick" for complex numbers. No, he didn't apply this idea to multiplying large integers. Remember that in Gauss's time a "computer" used pencil (or quill pen) and paper. $\endgroup$ – Robert Israel Dec 27 '18 at 4:26
  • 5
    $\begingroup$ @RobertIsrael I'm interested in more precise arguments than "it seems". Can you give any reference? $\endgroup$ – Alexey Ustinov Dec 27 '18 at 4:41
  • 2
    $\begingroup$ There is some discussion at cs.stackexchange.com/questions/1901/… $\endgroup$ – Gerry Myerson Dec 27 '18 at 4:44
  • 2
    $\begingroup$ @GerryMyerson In that question reference to "Gauss (complex numbers)" gives wikipedia article "Multiplication algorithm" where Gauss is not mentioned. So it is not clear again why this trick belongs to Gauss. $\endgroup$ – Alexey Ustinov Dec 27 '18 at 4:53
  • 1
    $\begingroup$ Might this be attributed to Gauss for the method in his Theoria Residuorum Biquadraticorum, Commentatio Secunda, Sect. 43-44 (for which there seems to be a German translation available online)? $\endgroup$ – student Dec 27 '18 at 17:24
24
$\begingroup$

I made an effort to trace the source of what Wikipedia describes as: "The basic step of Karatsuba's algorithm is a formula that allows one to compute the product of two large numbers $x$ and $y$ using three multiplications of smaller numbers, each with about half as many digits as $x$ or $y$, plus some additions and digit shifts. This basic step is, in fact, a generalization of Gauss's complex multiplication algorithm, where the imaginary unit $i$ is replaced by a power of the base."

In the linked page Wikipedia gives as a source Knuth's The Art of Computer Programming volume 2: Seminumerical algorithms. The multiplication of two complex numbers in three operations is discussed on page 647, without reference to Gauss. (I checked the entire volume and found no such reference.) Karatsuba discusses the history of his algoritm in The complexity of computations (1995), also without mentioning Gauss.

Since the efficient multiplication algorithm is related to the Fast Fourier Transform (FFT), it may be implicit in Gauss's (1805, published 1866) Theoria Interpolationis --- but I could not find it there in any obviously recognizable form.

Proofs that three multiplications are indeed minimal appeared in 1971, by S. Winograd and by I. Munro, again without reference to Gauss.

Daniel Bernstein's Multidigit multiplication for mathematicians (2001) carefully presents original sources for each algorithm and refers to Karatsuba's trick (page 5) instead of Gauss's trick. Bernstein does attribute a different multiplication "trick" to Gauss, the multiplication of high-degree polynomials which is at the basis of the FFT.
See page 7 of the 2001 paper, and page 5 of Fast multiplication and its applications, 2004

In Fast Algorithms for Signal Processing, Richard Blahut comments that "Algorithms for complex multiplication using three real multiplications became generally known in the late 1950s, but the origin of these algorithms is a little hazy."

I finally note that the attribution to Gauss seems to be of recent date. The earliest reference I found in Google is a 2005 lecture note. My conclusion at present is that this attribution is not based on the historical record.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ What about Goldstine's "History of numerical analysis" p249 (see ams.org/mathscinet-getitem?mr=484905 ) ? $\endgroup$ – BS. Jan 3 '19 at 10:32
  • $\begingroup$ @BS -- you might perhaps expand this comment? I do not have the book and Google will not show page 249... $\endgroup$ – Carlo Beenakker Jan 3 '19 at 11:19
  • $\begingroup$ @CarloBeenakker Will it work? libgen.io/book/index.php?md5=984B5D5058B6DC670750220E1340418C $\endgroup$ – Alexey Ustinov Jan 9 '19 at 12:45
  • 1
    $\begingroup$ @CarloBeenakker There is a comment on this page: ''Gauss III 77, pp. 303ff. This fascinating work of Gauss was neglected and was rediscovered by Cooley and Tukey in an important paper in 1965. Cf. Cooley, CTA, pp. 297-301." As I understand this comments is connected only with FFT. $\endgroup$ – Alexey Ustinov Jan 9 '19 at 13:05
  • $\begingroup$ Indeed, that is what Bernstein refers to as the “FFT trick”, to distinguish it from what he calls the “Karatsuba trick”. They are in the same spirit, but distinct. $\endgroup$ – Carlo Beenakker Jan 9 '19 at 16:08

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.