Discussion: View Thread

  • 1.  Computer Arithmetic

    Posted 01-18-2023 00:41

     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


    Press release

    and the source publication

    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

    "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