5 ms·

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

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
- esafak 2y ago
  And if I may take this yet a step further, this is the point of mathematical transformations: to find a domain in which desirable operations are easier such that the round trip to and from the domain are offset. In the past, transformations, like logarithms, Fourier transforms, wavelets, had to be proposed. Enabled by advances in computers, machine learning automated all that away by composing differentiable building blocks into universal estimators. The parameters of these building blocks are estimated through gradient descent in conjunction with a user-chosen loss function, which guides the optimization of the transform. Good representations can be manipulated through basic algebra (like added, averaged, and compared for similarity, depending on the task) in a way that corresponds to semantic operations when their raw, untransformed representations can not.
  - HPsquared 2y ago
    I'm still amazed at word embeddings. They allow to find related words, and even do addition and subtraction. The way you can supposedly take "king", subtract "man" and add "woman" and you get "queen", and this kind of thing is the mathematical basis of LLMs.
    - otabdeveloper4 2y ago
      That's an urban legend and not how embbeddings work.
      - CamperBob2 2y ago
        It's my understanding of how embeddings work, as well. The dot products (cosine similarity) of man . woman end up being very similar to king . queen. This similarity could be considered subtraction if you stretch the metaphor enough. If this is not a valid way to think about embedding vectors, would you care to elaborate?
        otabdeveloper4 2y ago
        Embedding vectors are when you take a high-dimensionality vector of word ID's and reduce deminsionality to something more manageable. (Think something like principal component analysis or singular value decomposition.) The "similarity" here means word ID's that commonly occur together in vectors. There is no logical reasoning or attempts at semantic analysis here. > The dot products (cosine similarity) of man . woman end up being very similar to king . queen This is because 'king' and 'man' occur together in a distribution similar to that of 'queen' and 'woman'. The idea that the embedding of 'king' is somehow a sum of 'autarch' and 'man' and that subtracting 'man' from 'king' and adding 'woman' somehow gives you 'queen' is an urban legend. Embeddings don't carry semantic meanings, they aren't dictionaries or encyclopedias. They are only statistical features about word co-occurrences.
mlyle 2y ago
Yes, and overflowing the mantissa moves the exponent in the right direction by the right amount; just now the least significant bits are not quite in the right place anymore. But that's by definition a small error.
advisedwang 2y ago
As the very first article says: > 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?
- zahlman 2y ago
  You can multiply two numbers by multiplying their mantissas and adding their exponents. Since the numbers are stored in base 2, the mantissa values range from 1 to 2 (subnormals notwithstanding) - but they're effectively stored as a 0..1 value. The effective range produced by adding vs. multiplying them have considerable overlap, and on average the difference won't be much. Because of how the mantissa and exponent fields are arranged (a deliberate choice by the standard, AFAIK), the mantissa effectively adds additional bits to the approximation of the logarithm given by the exponent. Edit: this other comment chain https://news.ycombinator.com/item?id=43034230 https://news.ycombinator.com/item?id=43034230 perhaps puts it better.
emmelaich 2y ago
Anyone who did high school before calculators (late 70s) would have carried around a book of logarithmic tables so they could do the multiplication necessary for many problems.

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

esafak 2y ago
And if I may take this yet a step further, this is the point of mathematical transformations: to find a domain in which desirable operations are easier such that the round trip to and from the domain are offset. In the past, transformations, like logarithms, Fourier transforms, wavelets, had to be proposed. Enabled by advances in computers, machine learning automated all that away by composing differentiable building blocks into universal estimators. The parameters of these building blocks are estimated through gradient descent in conjunction with a user-chosen loss function, which guides the optimization of the transform. Good representations can be manipulated through basic algebra (like added, averaged, and compared for similarity, depending on the task) in a way that corresponds to semantic operations when their raw, untransformed representations can not.
- HPsquared 2y ago
  I'm still amazed at word embeddings. They allow to find related words, and even do addition and subtraction. The way you can supposedly take "king", subtract "man" and add "woman" and you get "queen", and this kind of thing is the mathematical basis of LLMs.
  - otabdeveloper4 2y ago
    That's an urban legend and not how embbeddings work.
    - CamperBob2 2y ago
      It's my understanding of how embeddings work, as well. The dot products (cosine similarity) of man . woman end up being very similar to king . queen. This similarity could be considered subtraction if you stretch the metaphor enough. If this is not a valid way to think about embedding vectors, would you care to elaborate?
      - otabdeveloper4 2y ago
        Embedding vectors are when you take a high-dimensionality vector of word ID's and reduce deminsionality to something more manageable. (Think something like principal component analysis or singular value decomposition.) The "similarity" here means word ID's that commonly occur together in vectors. There is no logical reasoning or attempts at semantic analysis here. > The dot products (cosine similarity) of man . woman end up being very similar to king . queen This is because 'king' and 'man' occur together in a distribution similar to that of 'queen' and 'woman'. The idea that the embedding of 'king' is somehow a sum of 'autarch' and 'man' and that subtracting 'man' from 'king' and adding 'woman' somehow gives you 'queen' is an urban legend. Embeddings don't carry semantic meanings, they aren't dictionaries or encyclopedias. They are only statistical features about word co-occurrences.

mlyle 2y ago

Yes, and overflowing the mantissa moves the exponent in the right direction by the right amount; just now the least significant bits are not quite in the right place anymore. But that's by definition a small error.

advisedwang 2y ago

As the very first article says: > 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?

zahlman 2y ago
You can multiply two numbers by multiplying their mantissas and adding their exponents. Since the numbers are stored in base 2, the mantissa values range from 1 to 2 (subnormals notwithstanding) - but they're effectively stored as a 0..1 value. The effective range produced by adding vs. multiplying them have considerable overlap, and on average the difference won't be much. Because of how the mantissa and exponent fields are arranged (a deliberate choice by the standard, AFAIK), the mantissa effectively adds additional bits to the approximation of the logarithm given by the exponent. Edit: this other comment chain https://news.ycombinator.com/item?id=43034230 https://news.ycombinator.com/item?id=43034230 perhaps puts it better.

emmelaich 2y ago

Anyone who did high school before calculators (late 70s) would have carried around a book of logarithmic tables so they could do the multiplication necessary for many problems.