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.
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.
Brian Kesslersays:
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.
Very interesting, thank you for the article ! I wonder if any of the bignum library every thought about this…
I’d be interested in knowing the answer to this question… 🙂 I have looked at the usual suspects and found nothing.
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.
Interesting. I was aware of your code, but I don’t think I ever noticed that it is what you were doing.
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.
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
Thank you for the references.
It’s also studied for integer arithmetic:
Faster truncated integer multiplication – David Harvey -https://arxiv.org/abs/1703.00640