Multiply-Add Constants Finder

The multiply-add method speeds up integer division by a known constant divisor by replacing it with a multiplication, addition, and shift. This tool implements a generalization of this method, which allows multiplication by a known constant rational number (i.e. a fraction) followed by a rounding function. E.g. $\lceil x\cdot 3/7\rceil$.

Tool

/// Converts a value 0..=31 to 0..=255
/// by multiplying with 255/31 and then rounding.
fn convert_range(x: u8) -> u8 {
    debug_assert!(x <= 31);
    ((x as u16 * 527 + 23) >> 6) as u8
}

// Converts a value 0..=31 to 0..=255
// by multiplying with 255/31 and then rounding.
uint8_t convert_range(uint8_t x) {
    assert(x <= 31);
    return ((uint16_t)x * 527 + 23) >> 6;
}

s=6 f=527 a=23

Usage

This tool takes a problem (i.e. find multiply-add constants for $\lceil x\cdot 3/7\rceil$ for $x$ in the range $[0,255]$) and finds suitable constants.

Specify the parameters below and let this tool find suitable constants.

• r is the rounding function. After multiplying by the fraction, the result is rarely an integer, so it needs to be rounded. Supported rounding functions are:

  • round: round to nearest integer, rounding half away from zero
  • floor: round down to negative infinity, $\lfloor \cdot \rfloor$
  • ceil: round up to positive infinity, $\lceil \cdot \rceil$

• t and d are the numerator and denominator of the fraction to multiply by.

• u is the maximum input value (inclusive). Found constants are only valid for inputs $x\in [0,u]$.

  Use the "uN" buttons to quickly set the $u$ value for N-bit unsigned integers.

The tool will output an expression of the Best Solution. There are always infinitely many solutions, but this solution may allow additional compilers optimizations. C and Rust code implementing this solution are generated (some of the integer types used may require third-party libraries).

All solutions for the current problem can be viewed below. Solutions are given by their shift amount, factor, and addend.

Limitations

1. Certain problems are very computationally expensive to solve. In that case, this tool falls back to a solution that is known to be correct, but not necessarily optimal (=having the smallest s). This is indicated by a warning message.

2. While this tool support arbitrarily large integers as input, your browser may not like that. Number inputs may behave weirdly for numbers greater 4.5e+15 (2^52).