numbers. What they are unlikely to do,
many researchers agree, is come up
with any algorithm qualitatively faster
than n(logn). No one knows how to
prove this—as a rule, establishing there
are no algorithms faster than some
bound is much harder than coming up
with a new fast algorithm.
Nevertheless, “It would really surprise us if it is possible to do better than
n(logn),” van der Hoeven said. “We feel
that the story for integer multiplication
Faster Integer Multiplication. SIAM J.
Comput., Volume 39 Issue 3, 2009, pages
Harvey, D. and van der Hoeven, J.
Integer Multiplication in Time O(nlogn).
The Complexity of Computations.
Proceedings of the Steklov Institute
of Mathematics, Volume 211, 1995,
Schönhage, A. and Strassen, V.
Schnelle Multiplikation grosser Zahlen.
Computing, Volume 7, Issue 3-4,
September 1971, pages 281–292.
Erica Klarreich is a mathematics and science journalist
based in Berkeley, CA, USA.
© 2020 ACM 0001-0782/20/1 $15.00
day because they were superseded by
something else,” Harvey said.
Finally, in March 2019 the pair
figured out how to eliminate the
log(logn) term completely. Their new
algorithm uses a higher-dimensional
version of the fast Fourier transform,
combined with a method they devised
for increasing the number of sampling points to take advantage of additional speedups when the number
of sampling points is a power of two.
“It’s definitely the hardest paper I
ever worked on,” Harvey said.
The algorithm entails rounding
off the complex numbers involved in
the fast Fourier transform to achieve
a balance of speed and precision that
is “kind of amazing,” Cooper said.
“They’re performing exact integer
multiplication, but in the process
they’re passing into this other world
using complex numbers and poly-
nomials and doing an approximate
computation, then coming back and
getting an exact answer.”
The n(logn) bound means Harvey
and van der Hoeven’s algorithm is
faster than Schönhage and Strassen’s
algorithm, or Fürer’s algorithm, or any
other known multiplication algorithm,
provided n is sufficiently large. For
now, “sufficiently large” means almost
unfathomably large: Harvey and van
der Hoeven’s algorithm doesn’t even
kick in until the number of bits in the
two numbers being multiplied is great-
er than 2 raised to the 172912 power. (By
comparison, the number of particles in
the observable Universe is commonly
put at about 2270.)
Harvey and van der Hoeven made
no efforts to optimize their algorithm. This was partly because they
were focused on the theoretical advance, and partly because they were
tickled when their back-of-the-en-velope calculations led them to the
number 1729, which, in a famous
anecdote, the mathematician Srinivasa Ramanujan called a “very interesting” number (because it is the
smallest number that can be written
as a sum of two cubes in two different
ways). “When I saw this, I burst out
laughing,” Harvey recalled.
Other researchers will likely find
ways to tweak Harvey and van der Hoeven’s algorithm so it outperforms
other algorithms at smaller and smaller
entails rounding off
the complex numbers
in the fast Fourier
transform to achieve
a balance of speed
and precision that
is “kind of amazing,”
ACM recently inducted 62
Distinguished Members for
their outstanding contributions
to the field.
The 2019 inductees are
long-standing ACM members
selected by their peers for a
range of accomplishments
that have contributed to
technologies that underpin how
we live, work, and play.
“Each year, it is our
honor to select a new class
of Distinguished Members,”
explains ACM president Cherri
M. Pancake. “In everything we
do, our overarching goal is to
build a community wherein
computing professionals can
grow professionally and, in
turn, contribute to the field
and the broader society. We
are delighted to recognize
these individuals for their
contributions to computing,
and we hope that the careers of
the 2019 ACM Distinguished
Members will continue
to prosper through their
participation with ACM.”
The 2019 ACM Distinguished
Members have made
contributions in a wide range
of technical areas, including
artificial intelligence, human-
computer interaction, computer
engineering, computer science
graphics, and networking.
The ACM Distinguished
Member program recognizes
up to 10% of ACM worldwide
membership based on
professional experience and
significant achievement in the
computing field. Candidates
must have at least 15 years
of professional experience
in computing, five years of
ACM membership, and
have achieved a significant
level of accomplishment or
made a significant impact in
computing, computer science,
and/or information technology.
serve as mentors and role
models, guiding technical
career development and
contributing to the field
beyond the norm.
The list of new Distinguished
Members can be viewed at