Some new computer arithmetic - multiplication
- somewhat surprising to me is this appeared on my facebook! Less clear to me is if/when/how soon this will be implemented in software
a new method for computer multiplication of very large integers . This seems to be a proof of the
1971 conjecture of Schönhage and Strassen https://interestingengineering.com/science/mathematicians-discovered-a-new-much-faster-way-to-multiply-large-numbers?utm_source=Facebook&utm_medium=content&utm_campaign=organic&utm_content=Jan15&fbclid=IwAR2vbCbC0Gh1HdbroSFpXeFnItzIlceZxlLW1GPAePj7GBsa-v7h7nJVU8k&mibextid=Zxz2cZPress release
https://newsroom.unsw.edu.au/news/science-tech/maths-whiz-solves-48-year-old-multiplication-problemand the source publication
https://hal.science/hal-02070778/documentcitation
David Harvey, Joris van Der Hoeven. Integer multiplication in time O(n log n). Annals of Mathematics,
2021, �10.4007/annals.2021.193.2.4�. �hal-02070778v2�
and the authors abstract
Abstract. We present an algorithm that computes the product of two n-bit
integers in O(n log n) bit operations, thus confirming a conjecture of Sch¨onhage
and Strassen from 1971. Our complexity analysis takes place in the multitape
Turing machine model, with integers encoded in the usual binary representation. Central to the new algorithm is a novel "Gaussian resampling" technique
that enables us to reduce the integer multiplication problem to a collection of
multidimensional discrete Fourier transforms over the complex numbers, whose
dimensions are all powers of two. These transforms may then be evaluated
rapidly by means of Nussbaumer's fast polynomial transforms.
------------------------------
Chris Barker, Ph.D.
2023 Chair Statistical Consulting Section
Consultant and
Adjunct Associate Professor of Biostatistics
www.barkerstats.com---
"In composition you have all the time you want to decide what to say in 15 seconds, in improvisation you have 15 seconds."
-Steve Lacy
------------------------------