Hacker News Reader

Comment by eigenket | Hacker News Reader

Its worth noting that this asymmetry between addition and multiplication happens because our usual representations of numbers (i.e. on a piece of paper or in a a computer) favour addition over multiplication. You can come up with different representations of rationals, for example you could store prime exponents as integers so the number 20 gets stored as (2,0,1,0...) because its 2^2 × 3^0 × 5^1, or 5/6 would be (-1, -1, 1,...). With a representation like this, or just by taking logs if you like, you can come up with a representation where multiplication and division are very cheap but addition and subtraction are more expensive.

View on HN

Nitpick, 50 is 2^1 × 5^2, not the other way around. But anyway, thanks a ton for this post, I felt my brain shift at a new way of thinking about numbers, seriously. I have to wonder what serious and useful implementations of this method might have been done somewhere.

Thanks :) I edited my comment so the arithmetic is (hopefully) right now

By the way, if you're wondering if anyone has done anything useful with the method of describing numbers as prime exponents I mentioned the answer is yes, depending on your definition of "useful".

The encoding in terms of prime exponents is known as the Godel encoding, and its a fairly important step in proving things like Godel's incompleteness theorems and the undecidability of the Halting problem.

Essentially it's a one-to-one map between natural numbers and finite sequences of natural numbers (since you can encode (a,b,c,d...) as 2^a × 3^b × 5^c × 7^d etc), which turns out to be mathematically a convenient thing to have.

Stated very broadly, I think of the mathematical “design space” as the set {operations, representations}.

Classic examples include:

- time domain / frequency domain

- lookup table / functional form

- traditional binary representation / gray codes

Before mechanical calculators, large tables of logarithms were computed by hand and used for exactly this purpose.

Makes me wonder... Is it known whether there is some intermediate representation that makes both fast?

Yeah you store the log of every number.

Could you explain a little more of post a reference?

    A × B = C

then

    log A + log B = log C

And if

    D^E = F

then

    E × log D = log F

Mostly a tongue in cheek comment but if you don't know log rules at all check out log tables [0]. And you'll see that if you use log values then multiplication and division become addition and subtraction and equally simply.

Relies on you either having stored the needed data or efficiently calculating logirithms and antilogirithims.

https://www.cuemath.com/algebra/log-table/

Ah, I get it now. All we need is a logarithm oracle and we're good to go :)

Indeed, with lookup tables, if you've seen one, you've seen them all

Unfortunately, if you've seen them all, you also need to store them all :-)

Actually, everything will work out fine if we just could pick the optimal algorithm for each situation. How? Use an oracle to pick the right algorithm!

That's essentially how IEE 754 floating-point works. You can think of it as a piece-wise linear approximation of the base-2 logarithm.

For non-negative values, the exponent (upper) bits give the integer part of the logarithm and the significand (lower) bits approximate the fractional part (i.e., the mantissa).

In other words, you can do:

    float approxLog2( float value )
    {
        assert( value > 0.0f );
        auto bits = std::bit_cast< int32_t >( value );
        auto exponent = ( bits >> 23 ) - 127;
        auto significand = bits & ( ( 1 << 23 ) - 1 );
        return exponent + significand / static_cast< float >( 1 << 23 );
    }

This will be exact at powers of two, and within 0.0860748291 of the true value in between (always being slightly too low).

I don't think that anything exists which is going to be better than the normal representations we use in anything except fantastically niche situations.

I was going to add a less eloquent comment along these lines, but you got here first!

Please share it if you can recall. As someone who just figured out what Base-2 and Base-10 meant, I’m eager for all sorts of Mathematica.

Reply on news.ycombinator.com