Daniel Lemire's blog

, 6 min read

Multiplying backward for profit

8 thoughts on “Multiplying backward for profit”

  1. Very interesting, thank you for the article ! I wonder if any of the bignum library every thought about this…

    1. I’d be interested in knowing the answer to this question… 🙂 I have looked at the usual suspects and found nothing.

  2. KWillets says:

    This is the same thing that I was doing last summer here when I was fiddling with your range generator. The multiplication stops when a carry into the bits of interest is no longer possible; I ended up writing it as a tail-recursive carry() function.

    I haven’t read your code fully, but it looks like your gate on the carry flag is the same; I golfed it down to (x + w < x) to cover the possibility of [-1,w-1] in the continued multiplication.

    At the time I wrote this I didn’t notice any algorithms that do the same, but I don’t know much about numerics.

    1. Interesting. I was aware of your code, but I don’t think I ever noticed that it is what you were doing.

      1. KWillets says:

        That’s…understandable.

        It started as a finite extension of your modulo-and-discard to see if I could put off the modulo more; then I realized that extending the multiplication indefinitely was simpler in some ways.

        Mysteriously, the range generation solutions all seemed to center on checking the [0,w) range, even your discard method. Backwards multiplication also requires looking for -1 which can carry from further right, but one addition and a CF check cover both cases.

  3. Brian Kessler says:

    This problem comes up in multi precision floating point multiplication where it is called the “short product”. MPFR uses a method similar to yours for small sizes (called “naive” in their docs) and a divide and conquer method due to Mulders for larger sizes. See the MPFR docs for the references.

    https://hal.inria.fr/inria-00070266/document

    “Naive” method

    https://www.researchgate.net/publication/2786248_Efficient_Multiprecision_Floating_Point_Multiplication_with_Optimal_Directional_Rounding

    Mulders algorithm

    http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.55.285&rep=rep1&type=pdf

    1. Thank you for the references.

    2. multiplicator says:

      It’s also studied for integer arithmetic:
      Faster truncated integer multiplication – David Harvey -https://arxiv.org/abs/1703.00640