A346496 Smallest a(n) so that division by n can be performed by floor(x/n) = floor(x*A346495(n))/2^a(n) for any 0 <= x < 2^32.

0, 1, 33, 2, 34, 34, 35, 3, 33, 35, 35, 35, 34, 36, 35, 4, 36, 34, 37, 36, 37, 36, 36, 36, 35, 35, 37, 37, 36, 36, 37, 5, 35, 37, 38, 35, 38, 38, 38, 37, 37, 38, 35, 37, 38, 37, 37, 37, 36, 36, 37, 36, 38, 38, 38, 38, 38, 37, 35, 37, 36, 38, 38, 6, 38, 36

Offset

1,3

Comments

This sequence is used for division by multiplication with an approximation of the inverse of the divisor on computers if they support multiplying two 32-bit numbers for a 64-bit result. This is usually much faster than a division instruction because integer division is a very slow operation on most computers.

If x and n are unsigned 32-bit quantities, x/n is replaced by (in C notation) ((uint64_t) m * (uint64_t) x) >> a(n) where m is A346495(n).

If n = 2^k, then m=1 and a(n)=k (where the multiplication does not have to be performed).

Those a(n) larger than 2^32, such as a(7), cannot be used directly if the arithmetic is restricted to 32-bit. This requires additional operations.

References

Henry S. Warren, Hacker's Delight, 2nd edition, Addison-Wesley, 2013, pp. 230-234, "Unsigned Division by Divisors >= 1"

Links

Table of n, a(n) for n=1..66.

Formula

If n is a power of two, a(n) = log_2(n). Otherwise, let n_c = 2^32 - (2^32 mod n) - 1 and search for the lowest b so that 2^b > n_c * (n - 1 - ((2^b-1) mod n)). Then, a(n) = b and A346495(n) = (2^b + n - 1 - ((2^b - 1) mod n))/n.

Example

For n=3, m = A346495(3) = 2863311531 = (2^33 + 1)/3 = AAAAAAAB in base 16, b = a(3) = 33, so for 0 <= x < 2^32, x/3 = floor (x*2863311531 / 2^33). For x = 11111, m*x = 31814254420941, and floor(31814254420941/2^33) = 3703 = floor(11111/3).

Prog

(PARI) for(n=1, 65, my(k, j=ispower(n, , &k), n_c=2^32-2^32%n-1, b=1); if(j&&k==2, print1(j, ", "), while(b<=n_c*(n-1-(b-1)%n), b+=b); print1(valuation(b, 2), ", "))) \\ Hugo Pfoertner, Aug 24 2021
(Python)
def power2(n): return n == 2**(n.bit_length()-1)
def a(n):
    if power2(n): return n.bit_length() - 1
    n_c, b = 2**32 - (2**32%n) - 1, 1
    while 2**b <= n_c * (n - 1 - ((2**b - 1)%n)): b += 1
    return b
print([a(n) for n in range(1, 67)]) # Michael S. Branicky, Aug 24 2021

Crossrefs

A346495 gives the corresponding values for m.

Sequence in context: A032445 A333128 A135088 * A113467 A113458 A120584

Adjacent sequences: A346493 A346494 A346495 * A346497 A346498 A346499

Keyword

nonn,easy

Author

Thomas König, Jul 20 2021

Status

approved