21–30 of 75 posts
> And it happens to be the case that 7 × 9 = 63, which is almost 64, a power of 2 While the article goes down a different rabbit hole, this also happens to be a neat example of (n-1)(n+1) = n² - 1, where n = 8. Which is one of those things I haven't managed to find an actual use for but feels like it should have since you can use it with 0xFF (15 × 17), 0xFFFF (255 × 257), and so on.
Earlier quoted context omitted.
See https://godbolt.org/z/3Yqbceaza for what godbolt says clang produces. Keep in mind that this doesn't use the fact that we know that the input is between 0 to 63.
> Keep in mind that this doesn't use the fact that we know that the input is between 0 to 63. You can use __builtin_assume for this: https://godbolt.org/z/K4jKhxnTq
edit uh but when asserts are disabled it won't work: https://godbolt.org/z/4TMs1Wc5z
unless you roll your own assert: https://godbolt.org/z/4v35rrTvn
Don’t modern compilers do this automatically (and aggressively) for almost any division by a constant?
In cases where you need a floored result, or need it rounded in a certain direction, or know that the divisor is always positive, the compiler will often give you sub-optimal assembly. And sometimes the compiler just randomly fails to inline or constant-fold and outputs a big fat IDIV.
Also, if you have to debug with optimizations disabled, the compiler will give you deliberately garbage code, which can make the program you're debugging unusably slow. So you often end up hand-optimizing for that case.
Of course, this depends on where the hot path is, but I've had to do a lot of optimization for code that gets run billions of times per second. I used to think compilers were really smart, but after staring at enough assembly output and learning all their tricks, they don't seem that smart anymore. Especially Microsoft's compiler; I've seen it output redundant division instructions!
Dividing a number by 7 using bitwise operations can be done using a technique called "magic numbers." This involves precomputing a number that, when combined with bitwise operations, will give the correct result.
Here's how it can be done:
First, we need to find a "magic number" that will help us divide by 7. One way to do this is to use the fact that 7 is a prime number, which means that there is a number k such that 2^k ≡ -1 (mod 7). This number is called the "multiplicative inverse" of 2 modulo 7. We can find k by repeatedly squaring 2 until we get -1 modulo 7:
2^1 ≡ 2 (mod 7) 2^2 ≡ 4 (mod 7) 2^3 ≡ 1 (mod 7) 2^4 ≡ 2 (mod 7) 2^5 ≡ 4 (mod 7) 2^6 ≡ 1 (mod 7)
So k = 3, since 2^3 ≡ 1 (mod 7).
Next, we need to combine this magic number with bitwise operations. Specifically, we can use the following formula to divide a number x by 7:
x/7 = (x + (x >> 3)) * k
Here, >> is the bitwise right shift operator, which shifts the bits of x to the right by 3 places, effectively dividing x by 8. The expression (x + (x >> 3)) adds these two values together, which effectively multiplies x by 9. Multiplying by k then gives the correct result of dividing by 7.
Here's some example code in Python that implements this division algorithm:
python
def div_by_7(x): k = 3 return (x + (x >> 3)) * k
Note that this algorithm assumes that the input number x is a non-negative integer. It may not work correctly for negative numbers or floating-point numbers.
Wouldn’t a lookup table be a whole lot easier? I’d think a 64 entry table of integers would be fast to access once cached.
lookup table with 64 entries anyone?
(63 - nlz) / 7, where nlz is between 0 and 63 lookup table with 64 entries anyone?
Horner’s method [0] is also commonly used on small microcontrollers without divide (or multiply) instructions. [0] https://www.ti.com/lit/an/slaa329a/slaa329a.pdf