Ideal divisors: when a division compiles down to just a multiplication

This was a nice post, thank you! I don't yet have an intuition for how to think about these 2-adic exponentials and logs (e.g. what does it mean to say that log_2(5) =6713115954038056572) but clearly the mathematics works out and even leads to faster code, so it's very cool and I hope to read it again and understand it better.

(As a sidenote on the motivation, I do wonder how common/useful it is to compute x^y mod (2^64) for random 64-bit integers x and y (so they'd be close to 2^63 on average)... from this perspective, the promised future post about computing the k-th root of a perfect k-th power integer sounds very interesting!)

Makes more sense in binary:

  0xFFF..F 111111111111111111111111
  0x7      000000000000000000000111
  0x249..9 001001001001001001001001

I think you're trying to explain what's special about the number -1227133513 or how it comes about / how one could arrive at it. This is something the author understands very well; in fact that's what the whole post is about (well, it's about more advanced matters, using this as a "hook"), and many nice methods to arrive at that number are discussed in the post and comments. (And BTW your computation corresponds to 1227133513 or -1/7, not to -1227133513 or 1/7.) The sentence you quoted is merely asking which of the many discussed methods gcc is actually using, and this cannot be answered by mathematics; it needs to be answered by pointing to the relevant source code.

(Note that the subtraction is between two pointers to "struct A", not two chars. In the snippet "char" is used simply because it's 1 byte; one could also use int8_t, assuming a byte is 8 bits long.)

It's a fact about how the C language does pointer arithmetic.

For instance, suppose you have an array of many 64-bit integers, and a pointer to one of the elements of the array:

    int64_t arr[100];
    int64_t *p;
    p = &arr[50];

Conversely, if you give the new pointer a name:

    int64_t *q;
    q = p + 1;

That is, when subtracting pointers (of the same type), the result implicitly divides by the size of the type. In the code example in the blog post, as the size of "struct A" is 7 bytes, subtracting two pointers to A will subtract the memory addresses and divide by 7.

If that wasn't clear, see this sentence on Wikipedia: https://en.wikipedia.org/w/index.php?title=Pointer_(computer... or the answers to this question: https://stackoverflow.com/questions/3238482/pointer-subtract... or play with it yourself here: https://godbolt.org/z/M6PEWYeYx

35 / 7 = 5

35-7 = 28, 1

28-7 = 21, 2

21-7 = 14, 3

14-7 = 07, 4

07-7 = 00, 5

thus we can see that in essence, division is repeated subtraction in some contexts, especially computationally.

An easy way to count the amount of X that fits into Y is to simply count the amount of times you can subtract X from Y before Y is a negative value

The key here is "at runtime".

When shown on a 7-segment display, the only numbers whose images don't contain a little square are 1, 2, 3, 4, 5, and 7. I call them "square-free numbers".

Oh, you're saying "square-free" has an established meaning in mathematics? https://en.wikipedia.org/wiki/Square-free_integer

Well, you see, "square" already had an established meaning in English before number theory existed. Curious, why’d you pick that specialization of this word, out of all that are available? :)

algebra plays a huge role in CS, e.g. cryptography

As an example of applicability, I used reciprocal multiplication and shifting, plus knowledge of how many bits of accuracy I didn't need, to get my old Kinect code for my former startup to run near 30fps instead of 2-3fps on hardware with no FPU and IIRC no divide instruction.

Yeah, a more detailed description of this general method seems missing from the article. Anyone care to provide it?

Less than one order of magnitude these days. On Tiger Lake, integer multiply is 3 cycles, while integer division is 12 for 32-bit integers and 15 for 64-bit.

Of course, the multiply is fully pipelined while the division is only partially, but even that leaves only a 10-fold difference.

Division is much faster these days than it used to be. It's still worth it to have compiler optimizations for it, but it's not important to avoid it anymore.

In this specific example, they do produce exactly the same result:

`a / b` is completely equivalent to `a * (1 / b)` when both b and 1/b are perfectly representable in floating point without rounding, which is the case for 2 and 0.5

That makes sense. I typically have to worry about larger relative tolerances anyway so I think I can start using that trick.

Not directly, no. The underlying mathematics kind of can, but you'd need dedicated circuitry (or bit-hacking) for it because of the floating point parts, and it would fall over around subnormals.

I’m not certain, but while reading I was feeling like there potentially is a relationship. It was reminding me of the algorithm where you can approximate a reciprocal square root using a single subtraction from a magic number constant. https://en.wikipedia.org/wiki/Fast_inverse_square_root