Hacker News Reader

Comment by Dylan16807 | Hacker News Reader

It's worth noting that you can generally divide much faster if you know the divisor ahead of time, because you can turn it into a multiplication problem. But doing this takes some effort, as compared to turning subtraction into addition which is trivial.

View on HN

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.

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.

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.

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

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?

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.

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/

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).

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

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!

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 :-)

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.

Dr. Douglas Jones wrote a pretty great article on the subject, https://homepage.cs.uiowa.edu/~jones/bcd/divide.html. Depending on the divisor it can be a bit messy, since reciprocal multiplication sometimes needs extra precision. For example, on an 8-bit machine, x/6 == (x*42>>8), which is nice because 42 fits in 8 bits. But x/105 == (x*313>>15) needs 9 bits to hold 313. On some systems (thinking 8-bit AVR), it'd probably be faster to branch on the 3 cases rather than perform a full 16-bit multiplication.

To dive into this a bit more without using too much math jargon, under modulo every integer division is a trivial integer multiplication but the number you multiply by has to figured out before hand.

The above is also not true of factors of the modulo itself but then that's just a right shift so that part is easy.

eg. Under mod 35 if i want to divide by 3 i can just multiply by 12 since 12x3 = 1 under mod 35.

eg2. Under mod 35 if i want to divide by 11 i can just multiply by 16 since 16x11 = 1 under mod 35.

I can do this for any number that doesn't share factors with 35 since there's always a multiple to that number that will give 1. I could also create base 2 examples similarly. It's called the multiplicative inverse.

To clarify, there are two separate notions of division-as-multiplication discussed here.

Modular division is straightforward to convert to a multiplication; however this is mainly for specialized applications, like cryptography and number theory. It's uncommon to want divide-by-2 to make the value larger.

Ordinary flooring division can also be converted to a multiplication problem when the dividend is bounded. This uses the "magic number" approach where you multiply by a rounded scaled reciprocal, and then do some work to correct the error from rounding.

Can you explain what do you mean with:

>It's worth noting that you can generally divide much faster if you know the divisor ahead of time

Division is just multiplication with 1/x so i don't understand

For flooring integer division with a bounded dividend and known constant, the idea is to multiply by a scaled reciprocal. For example with 32 bit division by 3, you might precompute 2^32 / 3, multiply by that, and then flooring-divide by 2*32 (right shift).

It gets tricky because 2^32/3 is not an integer, so you must round it. This introduces error; the idea is to show that the error is wiped out by the flooring divide. I did the monster math here:

https://ridiculousfish.com/blog/posts/labor-of-division-epis...

Exactly. If you know you’re going to later be dividing by 23.7, you can precompute 1/23.7 and store that as a constant. Then you can later multiply by it.

Yes but 1/x is just another division, so it only helps to speed up the final division of you're able to calculate 1/x beforehand.

For integer division, you may find that rounding is not identical after multiplying by the reciprocal.

Doesn't the risk of lack of precision apply to both floating point and fixed-point? I'd think the reciprocal would need to be exactly represented in the type, or to have more bits than the original type to produce a correct result in the last bit (or two bits?).

Also, with integers, a signed right shift is rounding down (towards negative infinity), whereas the division operator/instruction in many languages/hardware is rounding towards 0.

To adjust the rounding, you'd add the sign-bit to the first fractional bit before shifting the last step. Let's say that 'x' is a signed long, and a signed long has 64 bits, then:

result = ((x >> amount-1) + ((unsigned long)x >> 63)) >> 1;

> Doesn't the risk of lack of precision apply to both floating point and fixed-point? I'd think the reciprocal would need to be exactly represented in the type, or to have more bits than the original type to produce a correct result in the last bit (or two bits?).

Yes, but this was historically okay on an x87 FPU which had more precise representation than the common external formats.

He is talking about the fact that compilers can turn division by a constant into multiplications and bit shifts which are much faster.

Here's an example: https://godbolt.org/z/8vG637fb5

It compiles x/6 to some mad multiplication, bitshift and add.

How do you calculate 1/x without using division?

Not being snarky, at the simplest level by knowing x ahead of time you can change your code from y = n/2 into y = n * 0.5. Not wildly important by itself, but in a loop - maybe… I suspect compilers optimize for that already.

I still don't get it. How do you know that 1/x = 0.abc... without performing the division? I mean in general case, not in something matching binary tricks. Such as 1/3 for example. Unless you mean you somehow know the value of 1/x ahead of time. But where does it come from?

If you know the divisor x ahead of time you can pre-compute 1/x at compile time, so that your actual compiled code never does the division--only your compiler does. Your actual compiled code just does the multiplication by a pre-computed constant (and the compiled code doesn't have to know that that constant was pre-computed as the reciprocal of x).

Ah, thanks for clarifying.

Often, you can amortize a division or reciprocal by calculating it once and then reusing it. Frequently the divisor is dynamic, but reused locally.

For example, if you want to normalize a 3D vector you could do:

    mag = sqrt(x*x + y*y + z*z)
    x /= mag
    y /= mag
    z /= mag

That's three divisions with the same divisor. But you could instead do:

    invMag = 1.0 / sqrt(x*x + y*y + z*z)
    x *= invMag
    y *= invMag
    z *= invMag

There's still a single division (or reciprocal) done here. But you've eliminated at least the other two. (And it's even better if you have an rsqrt function.)

so basically just precompute all the answers you will need and then just look up the values later?

There’s no lookup needed if the value is constant

I.e.

https://libdivide.com/

Reply on news.ycombinator.com