Division algorithm: Difference between revisions

Revision as of 07:06, 10 February 2025

Revision as of 17:10, 1 April 2025

Line 234:

For the subproblem of choosing an initial estimate <math>X_0</math>, it is convenient to apply a bit-shift to the divisor ''D'' to scale it so that 0.5&nbsp;≤&nbsp;''D''&nbsp;≤&nbsp;1. Applying the same bit-shift to the numerator ''N'' ensures the quotient does not change. Once within a bounded range, a simple polynomial [[approximation]] can be used to find an initial estimate.

The linear [[approximation]] with mimimumminimum worst-case absolute error on interval the interval <math>[0.5,1]</math> is:

:<math>X_0 = {48 \over 17} - {32 \over 17} D.</math>

The coefficients of the linear approximation <math>T_0 +T_1 D</math> are determined as follows. The absolute value of the error is <math>|\varepsilon_0| = |1 - D(T_0 + T_1 D)|</math>. The minimum of the maximum absolute value of the error is determined by the [[Equioscillation theorem|Chebyshev equioscillation theorem]] applied to <math>F(D) = 1 - D(T_0 + T_1 D)</math>. The local minimum of <math>F(D)</math> occurs when <math>F'(D) = 0</math>, which has solution <math>D = -T_0/(2T_1)</math>. The function at that minimum must be of opposite sign as the function at the endpoints, namely, <math>F(1/2) = F(1) = -F(-T_0/(2T_1))</math>. The two equations in the two unknowns have a unique solution <math>T_0 = 48/17</math> and <math>T_1 = -32/17</math>, and the maximum error is <math>F(1) = 1/17</math>. Using this approximation, the absolute value of the error of the initial value is less than