Divide by Constant Optimization

[NCGThompson]

We expect the compiler to look for redundant division and remainder operations on primitive types, and replace those with a single division. However, the compiler doesn't do this for ethnum's types, so ethnum has a separate divrem function. Following that same reasoning, it would make sense to provide a separate function for dividing by small compile time constants.

This is particularly useful for printing a big number in base 10.

[nlordell]

Just to make sure I understood the issue correctly, this would provide U256::div_u64(divisor: u64) functions that don’t needlessly compute the remainder? Or do you mean provide a const fn U256::div_64?

[NCGThompson]

The div_rem mention was just an analogy. It doesn't need to be a const function, but it takes advantage of precomputation when the divisor is known but not the dividend. Here is a widget showing how it works.

If I understand it correctly, then the precomputation cost is only dependent on the divisor, not the dividend, so dividing by constants that fit in a usize is particularily effecient. I experimented with compiler explorer some, and on x86_64, a hand written 256 x 64 multiplication yields good assembly without any LLVM-IR usage or nightly-only functions.