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?
Best Answer
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.