6 ms·

Why Does Integer Addition Approximate Float Multiplication?

182 points by ibobev 2y ago

Animats 2y ago
Neat. Of course it works for the exponent, but that it's not that far off for the mantissa is unexpected. It helps that the mantissa is normalized.
- guyomes 2y ago
  For the mantissa, the insight is probably that : (1+e1)*(1+e2) = 1+e1+e2+(e1*e2) If e1 and e2 are small, then e1*e2 is negligible.
  - thequux 2y ago
    Huh, and in the case that e1 and e2 are large, the mantissa overflows into the exponent, multiplying the result by 2.
    - amelius 2y ago
      I guess we're lucky that the IEEE 754 committee put the exponent in front of the mantissa. Or maybe they were aware of this trick all along ...
      - tialaramex 2y ago
        This arrangement makes ordering easier anyway which is probably why they chose it. If we have some positive 32-bit integers A and B then if A < B, f32::from_bits(A) < f32::from_bits(B) Edited to add anecdote: I actually had a bug in realistic (my Rust crate to implement Hans Boehm's "Towards an API for the Real Numbers") which I only fixed recently, for converting my Real number into a floating point type where I might end up with too many mantissa bits, but then sometimes coincidentally the bottom bit of the exponent is zero, and so instead of increasing the exponent by one I actually overwrite it with a one and that's the same result. I finally caught that when it occurred to me to do "thorough testing". That is, take all possible 32-bit floats, turn them into a Real, then, turn that Real back into a 32-bit float, this should be a roundtrip, if it's not we've found a bug. There are "only" a few billion of these values to test, a machine can do that. I fixed the 64-bit routines for the same bugs, but I don't have enough years to run all the 64-bit tests the same way and discover any that aren't paralleled. [Of course there are presumably still bugs in the conversion algorithms which may either be symmetric, and thus the bug doesn't impact a round trip, or they don't affect the binary fractions used exclusively by floats, Real has proper rationals and various other things like the square root of integers, Pi, etc. which we can convert to a float and lose precision but we never get these from converting a float because floats are always binary fractions.]
        xigoi 2y ago
        > If we have some positive 32-bit integers A and B then if A < B, f32::from_bits(A) < f32::from_bits(B) That is, if both are valid floats that represent a finite non-zero number.
        deleted 2y ago
        [deleted]
        pauli5 2y ago
        Correct. Floats support both -0 and 0 they compare equal but their bit representations don't. Zero can be tricky. Not a numbers (NaNs) always compare as false. Their bit representations won't.
        ChadNauseam 2y ago
        > realistic (my Rust crate to implement Hans Boehm's "Towards an API for the Real Numbers") So cool, I didn't know anyone was working on this!
        tialaramex 2y ago
        If you're familiar with that work, realistic implements most of it (some trig functions I didn't get to yet) but it's deliberately not 1.0 because I'm still tinkering with core API things like, I changed how the errors work this week. If you're not familiar, a fact about the reals which cannot be emphasised enough is that almost all real numbers are non-computable. This serves to properly temper expectations, regardless of whether you know what the mathematical term "Almost all" means. We're going to be able to compute some useful reals, and then do arithmetic with them, and not get miserably bad rounding errors like for floating point for example. We just need to keep in mind that "towards" here is just gesturing in a direction, it's not a destination which can be reached.
        ChadNauseam 2y ago
        Haha I'm familiar, I actually also tried to implement the paper at some point. It's such a cool idea and a great example of the difficulty that goes in to making a really good UX, even for something as simple-sounding as a calculator app.
      - zeckalpha 2y ago
        What's obvious to Kahan is being relearned by the rest of us.
deleted 2y ago
[deleted]
nabla9 2y ago
It's math and not just for integers. That's also how slide rule works. a×b = 10^(log(a×b)) log(a×b) = log(a)+log(b) thus a×b = 10^(log(a)+log(b))
- Sharlin 2y ago
  Yes, but what is nontrivial here is how good the approximation is, despite the mantissa part being linear (much better than the upper bound of being within 2x of the real value).
  - shiandow 2y ago
    Nontrivial yes, but it's not that complicated to figure out that floats are a piecewise linear approximation of the base 2 logarithm. Edit: or base 2^k, depends a bit how you view it.
- advisedwang 2y ago
  The very first paragraph of the article says this and then goes on to say the trick gets the mantissa roughly right too: > You can multiply two numbers by adding their exponents. So just with the exponent-addition you will be within a factor of 2 of the right result. But this will actually be much better and get within 7.5% of the right answer. Why?
sethaurus 2y ago
This is the core trick in the Fast Inverse Square Root[0], as made famous by the Quake III source code. It uses a shift (equivalent to dividing) and a subtraction in integer-land to estimate x^(-0.5) in float-land. [0]: https://en.m.wikipedia.org/wiki/Fast_inverse_square_root https://en.m.wikipedia.org/wiki/Fast_inverse_square_root
- Timwi 2y ago
  I've always hated that it's called an “inverse”. It's not an inverse. The inverse of square root is square. If they had called it “reciprocal”, it would have been clear to me what it does, but “inverse” confused the hell out of me when I first saw it.
  - deleted 2y ago
    [deleted]
  - Someone 2y ago
    It’s confusing for non-mathematicians, but (and you may know that) it is not incorrect. https://en.wikipedia.org/wiki/Inverse_element https://en.wikipedia.org/wiki/Inverse_element: “In mathematics, the concept of an inverse element generalises the concepts of opposite (−x) and reciprocal (1/x) of numbers.”
    - bmacho 2y ago
      No, it's confusing for mathematicians because it is directly opposing math terminology. (Which is okay, but confusing.)
      - Grimblewald 2y ago
        It doesnt though, inverse strictly speaking means the multiplicative inverse. The idea was extended in inverse functions eventually which for sake of brevity we also call the inverse. Now f^{-1}(x) and f(x)^{-1} are clearly different beasts the first would describe the square (for square root) while the second describes what quake was doing. Wether you call something an inverse or its full name (multiplicative/functional - inverse) depends on if its unclear from context which was meant.
deleted 2y ago
[deleted]
HPsquared 2y ago
The most significant bits of a floating point representation are basically a logarithm of the number. Logarithms have this relation between multiplication and addition.
- deleted 2y ago
  [deleted]
- vanderZwan 2y ago
  To give a "yes and" side-track to your comment: saying "logarithms have this relation between multiplication and addition" is even underselling what logarithms are, because reducing multiplication to an additive operation was the whole motivation for John Napier[0] to discover/invent logarithms: > “…nothing is more tedious, fellow mathematicians, in the practice of the mathematical arts, than the great delays suffered in the tedium of lengthy multiplications and divisions, the finding of ratios, and in the extraction of square and cube roots… [with] the many slippery errors that can arise…I have found an amazing way of shortening the proceedings [in which]… all the numbers associated with the multiplications, and divisions of numbers, and with the long arduous tasks of extracting square and cube roots are themselves rejected from the work, and in their place other numbers are substituted, which perform the tasks of these rejected by means of addition, subtraction, and division by two or three only.”[1] Logarithms were honestly an enormous breakthrough in optimization, computers wouldn't be remotely as useful without them, even if most of us don't "see" the logarithms being used. In fact I'd argue that they are the second-biggest computational optimization in use today, with only positional notation being a bigger deal. Which, funny enough, works kind of similarly: imagine you only could count by tallying (so, unary). Adding two number M and N would take M+N operations, e.g. 1234 + 5678 would require counting all 6912 individual digits. Unary math scales O(n) in both data and computation. Systems like Roman numerals almost work, but as soon as we reach values larger than the largest symbol (M for 1000) it's O(n) again, just with a better constant factor. With positional notation numbers require only log(n) symbols to write down, and log(n) operations for addition, e.g. 1234 + 5678 requires one or two additions for each digit pair in a given position - one addition if there's no carry from the previous addition, two if there is. So addition at most 2 × ceil( max( log(M), log(N) ) ) operations, so log(n). Logarithms take that idea and "recursively" apply it to the notation, making the same optimization work for multiplication. Without it, the naive algorithm for the multiplication of two numbers requires iterating over each digit, e.g. 1234 × 5678 requires multiplying each of the four digits of the first number with each of the digit of the second number, and then adding all the resulting numbers. It scales O(di×dj), where di and dj are the digits of each number. If they're the same we can simplify that to O(d²). When the numbers are represented as two logarithms the operation is reduced to adding two numbers again, so O(log(d) + [whatever the log/inverse log conversion cost is]). Of course d is a different value here and the number of digits used affects the precision. I think the craziest thing of all this is that we're so used to positional notation that nobody ever seems to consider it a data compression technique. Even though almost no other data compression method would work without it as a building block (run-length encoding, Lempel-Ziv, Arithmetic coding? Useless without positional notation's O(log(n)) scaling factor). The only exceptions are data compression methods that are based on inventing their own numerical notation[2]. We do this every day ever since we first learned addition and subtraction as kids. Or as David Bess[3] puts it in his book "Mathematica": ask almost any adult what one billion minus one is and they know the answer instantaneously, so most adults would appear to have mental superpowers in the eyes of pretty much all mathematicians before positional notation was invented (well, everyone except Archimedes maybe[4]). Positional notation is magical, we're all math wizards, and it's so normalized that we don't even realize it. But to get back to your original point: yes, you are entirely correct. IEEE floats are a form of lossy compression of fractions, and the basis of that lossy compression is logarithmic notation (but with a fixed number of binary digits and some curious rules for encoding other values like NaN and infinity). [0] https://en.wikipedia.org/wiki/John_Napier https://en.wikipedia.org/wiki/John_Napier [1] https://en.wikipedia.org/wiki/Mirifici_Logarithmorum_Canonis_Descriptio https://en.wikipedia.org/wiki/Mirifici_Logarithmorum_Canonis... [2] https://en.wikipedia.org/wiki/Asymmetric_numeral_systems https://en.wikipedia.org/wiki/Asymmetric_numeral_systems [3] https://www.quantamagazine.org/mathematical-thinking-isnt-what-you-think-it-is-20241118/ https://www.quantamagazine.org/mathematical-thinking-isnt-wh... [4] https://en.wikipedia.org/wiki/The_Sand_Reckoner https://en.wikipedia.org/wiki/The_Sand_Reckoner
fatuna 2y ago
Would subtraction also approximate division?
- Jaxan 2y ago
  Yes
  - Timwi 2y ago
    Would negation also approximate the reciprocal?
    - vanderZwan 2y ago
      Yes. Logarithms are wonderful like that :)
rowanG077 2y ago
This can be very worth it in circuit design for custom accelerators. Floating point operation is often multicycle. If you can get close enough with addition it will save a ton of resources and probably also simplify the design.
SushiHippie 2y ago
Previous discussion of the paper: Addition is all you need for energy-efficient language models - https://news.ycombinator.com/item?id=41784591 https://news.ycombinator.com/item?id=41784591 - Oct 2024 - 126 comments
WhitneyLand 2y ago
I wonder if there was any inspiration from Quake III. Didn’t the inverse square root trick rely on bit-level floating point and subtraction of a bias?
akomtu 2y ago
float32 (1+m)×2^e as int32 = e<<23 | m (1+m1)×2^e1 × (1+m2)×2^e2 = (1+m1+m2+m1×m2)×2^(e1+e2) If m1×m2 is small, that's approximately float32(m1+m2, e1+e2).
deleted 2y ago
[deleted]
zeckalpha 2y ago
> The paper talks about using this to save power, but that’s probably not worth it for a few reasons It's probably not worth it to do this in software. But in hardware, it might be! A similar approach with a hardware prototype. https://research.nvidia.com/publication/2022-12_lns-madam-low-precision-training-logarithmic-number-system-using-multiplicative https://research.nvidia.com/publication/2022-12_lns-madam-lo...

182 points by ibobev 2y ago

Neat. Of course it works for the exponent, but that it's not that far off for the mantissa is unexpected. It helps that the mantissa is normalized.

guyomes 2y ago
For the mantissa, the insight is probably that : (1+e1)*(1+e2) = 1+e1+e2+(e1*e2) If e1 and e2 are small, then e1*e2 is negligible.
- thequux 2y ago
  Huh, and in the case that e1 and e2 are large, the mantissa overflows into the exponent, multiplying the result by 2.
  - amelius 2y ago
    I guess we're lucky that the IEEE 754 committee put the exponent in front of the mantissa. Or maybe they were aware of this trick all along ...
    - tialaramex 2y ago
      This arrangement makes ordering easier anyway which is probably why they chose it. If we have some positive 32-bit integers A and B then if A < B, f32::from_bits(A) < f32::from_bits(B) Edited to add anecdote: I actually had a bug in realistic (my Rust crate to implement Hans Boehm's "Towards an API for the Real Numbers") which I only fixed recently, for converting my Real number into a floating point type where I might end up with too many mantissa bits, but then sometimes coincidentally the bottom bit of the exponent is zero, and so instead of increasing the exponent by one I actually overwrite it with a one and that's the same result. I finally caught that when it occurred to me to do "thorough testing". That is, take all possible 32-bit floats, turn them into a Real, then, turn that Real back into a 32-bit float, this should be a roundtrip, if it's not we've found a bug. There are "only" a few billion of these values to test, a machine can do that. I fixed the 64-bit routines for the same bugs, but I don't have enough years to run all the 64-bit tests the same way and discover any that aren't paralleled. [Of course there are presumably still bugs in the conversion algorithms which may either be symmetric, and thus the bug doesn't impact a round trip, or they don't affect the binary fractions used exclusively by floats, Real has proper rationals and various other things like the square root of integers, Pi, etc. which we can convert to a float and lose precision but we never get these from converting a float because floats are always binary fractions.]
      - xigoi 2y ago
        > If we have some positive 32-bit integers A and B then if A < B, f32::from_bits(A) < f32::from_bits(B) That is, if both are valid floats that represent a finite non-zero number.
        deleted 2y ago
        [deleted]
        pauli5 2y ago
        Correct. Floats support both -0 and 0 they compare equal but their bit representations don't. Zero can be tricky. Not a numbers (NaNs) always compare as false. Their bit representations won't.
      - ChadNauseam 2y ago
        > realistic (my Rust crate to implement Hans Boehm's "Towards an API for the Real Numbers") So cool, I didn't know anyone was working on this!
        tialaramex 2y ago
        If you're familiar with that work, realistic implements most of it (some trig functions I didn't get to yet) but it's deliberately not 1.0 because I'm still tinkering with core API things like, I changed how the errors work this week. If you're not familiar, a fact about the reals which cannot be emphasised enough is that almost all real numbers are non-computable. This serves to properly temper expectations, regardless of whether you know what the mathematical term "Almost all" means. We're going to be able to compute some useful reals, and then do arithmetic with them, and not get miserably bad rounding errors like for floating point for example. We just need to keep in mind that "towards" here is just gesturing in a direction, it's not a destination which can be reached.
        ChadNauseam 2y ago
        Haha I'm familiar, I actually also tried to implement the paper at some point. It's such a cool idea and a great example of the difficulty that goes in to making a really good UX, even for something as simple-sounding as a calculator app.
    - zeckalpha 2y ago
      What's obvious to Kahan is being relearned by the rest of us.

deleted 2y ago

[deleted]

nabla9 2y ago

It's math and not just for integers. That's also how slide rule works. a×b = 10^(log(a×b)) log(a×b) = log(a)+log(b) thus a×b = 10^(log(a)+log(b))

Sharlin 2y ago
Yes, but what is nontrivial here is how good the approximation is, despite the mantissa part being linear (much better than the upper bound of being within 2x of the real value).
- shiandow 2y ago
  Nontrivial yes, but it's not that complicated to figure out that floats are a piecewise linear approximation of the base 2 logarithm. Edit: or base 2^k, depends a bit how you view it.
advisedwang 2y ago
The very first paragraph of the article says this and then goes on to say the trick gets the mantissa roughly right too: > You can multiply two numbers by adding their exponents. So just with the exponent-addition you will be within a factor of 2 of the right result. But this will actually be much better and get within 7.5% of the right answer. Why?

sethaurus 2y ago

This is the core trick in the Fast Inverse Square Root[0], as made famous by the Quake III source code. It uses a shift (equivalent to dividing) and a subtraction in integer-land to estimate x^(-0.5) in float-land. [0]: https://en.m.wikipedia.org/wiki/Fast_inverse_square_root https://en.m.wikipedia.org/wiki/Fast_inverse_square_root

Timwi 2y ago
I've always hated that it's called an “inverse”. It's not an inverse. The inverse of square root is square. If they had called it “reciprocal”, it would have been clear to me what it does, but “inverse” confused the hell out of me when I first saw it.
- deleted 2y ago
  [deleted]
- Someone 2y ago
  It’s confusing for non-mathematicians, but (and you may know that) it is not incorrect. https://en.wikipedia.org/wiki/Inverse_element https://en.wikipedia.org/wiki/Inverse_element: “In mathematics, the concept of an inverse element generalises the concepts of opposite (−x) and reciprocal (1/x) of numbers.”
  - bmacho 2y ago
    No, it's confusing for mathematicians because it is directly opposing math terminology. (Which is okay, but confusing.)
    - Grimblewald 2y ago
      It doesnt though, inverse strictly speaking means the multiplicative inverse. The idea was extended in inverse functions eventually which for sake of brevity we also call the inverse. Now f^{-1}(x) and f(x)^{-1} are clearly different beasts the first would describe the square (for square root) while the second describes what quake was doing. Wether you call something an inverse or its full name (multiplicative/functional - inverse) depends on if its unclear from context which was meant.

deleted 2y ago

[deleted]

HPsquared 2y ago

The most significant bits of a floating point representation are basically a logarithm of the number. Logarithms have this relation between multiplication and addition.

deleted 2y ago
[deleted]
vanderZwan 2y ago
To give a "yes and" side-track to your comment: saying "logarithms have this relation between multiplication and addition" is even underselling what logarithms are, because reducing multiplication to an additive operation was the whole motivation for John Napier[0] to discover/invent logarithms: > “…nothing is more tedious, fellow mathematicians, in the practice of the mathematical arts, than the great delays suffered in the tedium of lengthy multiplications and divisions, the finding of ratios, and in the extraction of square and cube roots… [with] the many slippery errors that can arise…I have found an amazing way of shortening the proceedings [in which]… all the numbers associated with the multiplications, and divisions of numbers, and with the long arduous tasks of extracting square and cube roots are themselves rejected from the work, and in their place other numbers are substituted, which perform the tasks of these rejected by means of addition, subtraction, and division by two or three only.”[1] Logarithms were honestly an enormous breakthrough in optimization, computers wouldn't be remotely as useful without them, even if most of us don't "see" the logarithms being used. In fact I'd argue that they are the second-biggest computational optimization in use today, with only positional notation being a bigger deal. Which, funny enough, works kind of similarly: imagine you only could count by tallying (so, unary). Adding two number M and N would take M+N operations, e.g. 1234 + 5678 would require counting all 6912 individual digits. Unary math scales O(n) in both data and computation. Systems like Roman numerals almost work, but as soon as we reach values larger than the largest symbol (M for 1000) it's O(n) again, just with a better constant factor. With positional notation numbers require only log(n) symbols to write down, and log(n) operations for addition, e.g. 1234 + 5678 requires one or two additions for each digit pair in a given position - one addition if there's no carry from the previous addition, two if there is. So addition at most 2 × ceil( max( log(M), log(N) ) ) operations, so log(n). Logarithms take that idea and "recursively" apply it to the notation, making the same optimization work for multiplication. Without it, the naive algorithm for the multiplication of two numbers requires iterating over each digit, e.g. 1234 × 5678 requires multiplying each of the four digits of the first number with each of the digit of the second number, and then adding all the resulting numbers. It scales O(di×dj), where di and dj are the digits of each number. If they're the same we can simplify that to O(d²). When the numbers are represented as two logarithms the operation is reduced to adding two numbers again, so O(log(d) + [whatever the log/inverse log conversion cost is]). Of course d is a different value here and the number of digits used affects the precision. I think the craziest thing of all this is that we're so used to positional notation that nobody ever seems to consider it a data compression technique. Even though almost no other data compression method would work without it as a building block (run-length encoding, Lempel-Ziv, Arithmetic coding? Useless without positional notation's O(log(n)) scaling factor). The only exceptions are data compression methods that are based on inventing their own numerical notation[2]. We do this every day ever since we first learned addition and subtraction as kids. Or as David Bess[3] puts it in his book "Mathematica": ask almost any adult what one billion minus one is and they know the answer instantaneously, so most adults would appear to have mental superpowers in the eyes of pretty much all mathematicians before positional notation was invented (well, everyone except Archimedes maybe[4]). Positional notation is magical, we're all math wizards, and it's so normalized that we don't even realize it. But to get back to your original point: yes, you are entirely correct. IEEE floats are a form of lossy compression of fractions, and the basis of that lossy compression is logarithmic notation (but with a fixed number of binary digits and some curious rules for encoding other values like NaN and infinity). [0] https://en.wikipedia.org/wiki/John_Napier https://en.wikipedia.org/wiki/John_Napier [1] https://en.wikipedia.org/wiki/Mirifici_Logarithmorum_Canonis_Descriptio https://en.wikipedia.org/wiki/Mirifici_Logarithmorum_Canonis... [2] https://en.wikipedia.org/wiki/Asymmetric_numeral_systems https://en.wikipedia.org/wiki/Asymmetric_numeral_systems [3] https://www.quantamagazine.org/mathematical-thinking-isnt-what-you-think-it-is-20241118/ https://www.quantamagazine.org/mathematical-thinking-isnt-wh... [4] https://en.wikipedia.org/wiki/The_Sand_Reckoner https://en.wikipedia.org/wiki/The_Sand_Reckoner

fatuna 2y ago

Would subtraction also approximate division?

Jaxan 2y ago
Yes
- Timwi 2y ago
  Would negation also approximate the reciprocal?
  - vanderZwan 2y ago
    Yes. Logarithms are wonderful like that :)

rowanG077 2y ago

This can be very worth it in circuit design for custom accelerators. Floating point operation is often multicycle. If you can get close enough with addition it will save a ton of resources and probably also simplify the design.

SushiHippie 2y ago

Previous discussion of the paper: Addition is all you need for energy-efficient language models - https://news.ycombinator.com/item?id=41784591 https://news.ycombinator.com/item?id=41784591 - Oct 2024 - 126 comments

WhitneyLand 2y ago

I wonder if there was any inspiration from Quake III. Didn’t the inverse square root trick rely on bit-level floating point and subtraction of a bias?

akomtu 2y ago

float32 (1+m)×2^e as int32 = e<<23 | m (1+m1)×2^e1 × (1+m2)×2^e2 = (1+m1+m2+m1×m2)×2^(e1+e2) If m1×m2 is small, that's approximately float32(m1+m2, e1+e2).

deleted 2y ago

[deleted]

zeckalpha 2y ago

> The paper talks about using this to save power, but that’s probably not worth it for a few reasons It's probably not worth it to do this in software. But in hardware, it might be! A similar approach with a hardware prototype. https://research.nvidia.com/publication/2022-12_lns-madam-low-precision-training-logarithmic-number-system-using-multiplicative https://research.nvidia.com/publication/2022-12_lns-madam-lo...