Division algorithm - Revision history

84.238.83.158 at 19:09, 10 May 2025

2025-05-10T19:09:18Z

← Previous revision		Revision as of 19:09, 10 May 2025
Line 359:		Line 359:
	After a sufficient number ''k'' of iterations <math>Q=N_k</math>.		After a sufficient number ''k'' of iterations <math>Q=N_k</math>.

	The Goldschmidt method is used in [[AMD]] Athlon CPUs and later models.<ref>{{cite book \|first=Stuart F. \|last=Oberman \|title=Proceedings 14th IEEE Symposium on Computer Arithmetic (Cat. No.99CB36336) \|chapter=Floating point division and square root algorithms and implementation in the AMD-K7 Microprocessor \|pages=106–115 \|date=1999 \|doi=10.1109/ARITH.1999.762835 \|isbn=0-7695-0116-8 \|s2cid=12793819 \|chapter-url=http://www.acsel-lab.com/arithmetic/arith14/papers/ARITH14_Oberman.pdf \|access-date=2015-09-15 \|archive-date=2015-11-29 \|archive-url=https://web.archive.org/web/20151129095846/http://www.acsel-lab.com/arithmetic/arith14/papers/ARITH14_Oberman.pdf \|url-status=live }}</ref><ref>{{cite journal \|first1=Peter \|last1=Soderquist \|first2=Miriam \|last2=Leeser \|title=Division and Square Root: Choosing the Right Implementation \|journal=IEEE Micro \|volume=17 \|issue=4 \|pages=56–66 \|date=July–August 1997 \|url=https://www.researchgate.net/publication/2511700 \|doi=10.1109/40.612224 }}</ref> It is also known as Anderson Earle Goldschmidt Powers (AEGP) algorithm and is implemented by various [IBM] processors.<ref>S. F. Anderson, J. G. Earle, R. E. Goldschmidt, D. M. Powers. ''The IBM 360/370 model 91: floating-point execution unit'', [[IBM Journal of Research and Development]], January 1997</ref><ref name="goldschmidt-analysis">{{cite journal \|last1=Guy \|first1=Even \|last2=Peter \|first2=Siedel \|last3=Ferguson \|first3=Warren \|title=A parametric error analysis of Goldschmidt's division algorithm \|journal=Journal of Computer and System Sciences \|date=1 February 2005 \|volume=70 \|issue=1 \|pages=118–139 \|doi=10.1016/j.jcss.2004.08.004 \|doi-access=free }}</ref> Although it converges at the same rate as a Newton–Raphson implementation, one advantage of the Goldschmidt method is that the multiplications in the numerator and in the denominator can be done in parallel.<ref name="goldschmidt-analysis" />		The Goldschmidt method is used in [[AMD]] Athlon CPUs and later models.<ref>{{cite book \|first=Stuart F. \|last=Oberman \|title=Proceedings 14th IEEE Symposium on Computer Arithmetic (Cat. No.99CB36336) \|chapter=Floating point division and square root algorithms and implementation in the AMD-K7 Microprocessor \|pages=106–115 \|date=1999 \|doi=10.1109/ARITH.1999.762835 \|isbn=0-7695-0116-8 \|s2cid=12793819 \|chapter-url=http://www.acsel-lab.com/arithmetic/arith14/papers/ARITH14_Oberman.pdf \|access-date=2015-09-15 \|archive-date=2015-11-29 \|archive-url=https://web.archive.org/web/20151129095846/http://www.acsel-lab.com/arithmetic/arith14/papers/ARITH14_Oberman.pdf \|url-status=live }}</ref><ref>{{cite journal \|first1=Peter \|last1=Soderquist \|first2=Miriam \|last2=Leeser \|title=Division and Square Root: Choosing the Right Implementation \|journal=IEEE Micro \|volume=17 \|issue=4 \|pages=56–66 \|date=July–August 1997 \|url=https://www.researchgate.net/publication/2511700 \|doi=10.1109/40.612224 }}</ref> It is also known as Anderson Earle Goldschmidt Powers (AEGP) algorithm and is implemented by various [[IBM]] processors.<ref>S. F. Anderson, J. G. Earle, R. E. Goldschmidt, D. M. Powers. ''The IBM 360/370 model 91: floating-point execution unit'', [[IBM Journal of Research and Development]], January 1997</ref><ref name="goldschmidt-analysis">{{cite journal \|last1=Guy \|first1=Even \|last2=Peter \|first2=Siedel \|last3=Ferguson \|first3=Warren \|title=A parametric error analysis of Goldschmidt's division algorithm \|journal=Journal of Computer and System Sciences \|date=1 February 2005 \|volume=70 \|issue=1 \|pages=118–139 \|doi=10.1016/j.jcss.2004.08.004 \|doi-access=free }}</ref> Although it converges at the same rate as a Newton–Raphson implementation, one advantage of the Goldschmidt method is that the multiplications in the numerator and in the denominator can be done in parallel.<ref name="goldschmidt-analysis" />

	====Binomial theorem====		====Binomial theorem====

84.238.83.158: Added missing IBM refference

2025-05-10T19:08:05Z

Added missing IBM refference

← Previous revision		Revision as of 19:08, 10 May 2025
Line 359:		Line 359:
	After a sufficient number ''k'' of iterations <math>Q=N_k</math>.		After a sufficient number ''k'' of iterations <math>Q=N_k</math>.

	The Goldschmidt method is used in [[AMD]] Athlon CPUs and later models.<ref>{{cite book \|first=Stuart F. \|last=Oberman \|title=Proceedings 14th IEEE Symposium on Computer Arithmetic (Cat. No.99CB36336) \|chapter=Floating point division and square root algorithms and implementation in the AMD-K7 Microprocessor \|pages=106–115 \|date=1999 \|doi=10.1109/ARITH.1999.762835 \|isbn=0-7695-0116-8 \|s2cid=12793819 \|chapter-url=http://www.acsel-lab.com/arithmetic/arith14/papers/ARITH14_Oberman.pdf \|access-date=2015-09-15 \|archive-date=2015-11-29 \|archive-url=https://web.archive.org/web/20151129095846/http://www.acsel-lab.com/arithmetic/arith14/papers/ARITH14_Oberman.pdf \|url-status=live }}</ref><ref>{{cite journal \|first1=Peter \|last1=Soderquist \|first2=Miriam \|last2=Leeser \|title=Division and Square Root: Choosing the Right Implementation \|journal=IEEE Micro \|volume=17 \|issue=4 \|pages=56–66 \|date=July–August 1997 \|url=https://www.researchgate.net/publication/2511700 \|doi=10.1109/40.612224 }}</ref> It is also known as Anderson Earle Goldschmidt Powers (AEGP) algorithm and is implemented by various IBM processors.<ref>S. F. Anderson, J. G. Earle, R. E. Goldschmidt, D. M. Powers. ''The IBM 360/370 model 91: floating-point execution unit'', [[IBM Journal of Research and Development]], January 1997</ref><ref name="goldschmidt-analysis">{{cite journal \|last1=Guy \|first1=Even \|last2=Peter \|first2=Siedel \|last3=Ferguson \|first3=Warren \|title=A parametric error analysis of Goldschmidt's division algorithm \|journal=Journal of Computer and System Sciences \|date=1 February 2005 \|volume=70 \|issue=1 \|pages=118–139 \|doi=10.1016/j.jcss.2004.08.004 \|doi-access=free }}</ref> Although it converges at the same rate as a Newton–Raphson implementation, one advantage of the Goldschmidt method is that the multiplications in the numerator and in the denominator can be done in parallel.<ref name="goldschmidt-analysis" />		The Goldschmidt method is used in [[AMD]] Athlon CPUs and later models.<ref>{{cite book \|first=Stuart F. \|last=Oberman \|title=Proceedings 14th IEEE Symposium on Computer Arithmetic (Cat. No.99CB36336) \|chapter=Floating point division and square root algorithms and implementation in the AMD-K7 Microprocessor \|pages=106–115 \|date=1999 \|doi=10.1109/ARITH.1999.762835 \|isbn=0-7695-0116-8 \|s2cid=12793819 \|chapter-url=http://www.acsel-lab.com/arithmetic/arith14/papers/ARITH14_Oberman.pdf \|access-date=2015-09-15 \|archive-date=2015-11-29 \|archive-url=https://web.archive.org/web/20151129095846/http://www.acsel-lab.com/arithmetic/arith14/papers/ARITH14_Oberman.pdf \|url-status=live }}</ref><ref>{{cite journal \|first1=Peter \|last1=Soderquist \|first2=Miriam \|last2=Leeser \|title=Division and Square Root: Choosing the Right Implementation \|journal=IEEE Micro \|volume=17 \|issue=4 \|pages=56–66 \|date=July–August 1997 \|url=https://www.researchgate.net/publication/2511700 \|doi=10.1109/40.612224 }}</ref> It is also known as Anderson Earle Goldschmidt Powers (AEGP) algorithm and is implemented by various [IBM] processors.<ref>S. F. Anderson, J. G. Earle, R. E. Goldschmidt, D. M. Powers. ''The IBM 360/370 model 91: floating-point execution unit'', [[IBM Journal of Research and Development]], January 1997</ref><ref name="goldschmidt-analysis">{{cite journal \|last1=Guy \|first1=Even \|last2=Peter \|first2=Siedel \|last3=Ferguson \|first3=Warren \|title=A parametric error analysis of Goldschmidt's division algorithm \|journal=Journal of Computer and System Sciences \|date=1 February 2005 \|volume=70 \|issue=1 \|pages=118–139 \|doi=10.1016/j.jcss.2004.08.004 \|doi-access=free }}</ref> Although it converges at the same rate as a Newton–Raphson implementation, one advantage of the Goldschmidt method is that the multiplications in the numerator and in the denominator can be done in parallel.<ref name="goldschmidt-analysis" />

	====Binomial theorem====		====Binomial theorem====

Jason Davies: Fix typo.

2025-05-06T12:38:21Z

Fix typo.

← Previous revision		Revision as of 12:38, 6 May 2025
Line 234:		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 ≤ ''D'' ≤ 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.		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 ≤ ''D'' ≤ 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 minimum worst-case absolute error on ~~interval~~ the interval <math>[0.5,1]</math> is:		The linear [[approximation]] with minimum worst-case absolute error on the interval <math>[0.5,1]</math> is:
	:<math>X_0 = {48 \over 17} - {32 \over 17} D.</math>		:<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		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

Mr. X 235528: /* Initial estimate */

2025-04-01T17:10:35Z

Initial estimate

← Previous revision		Revision as of 17:10, 1 April 2025
Line 234:		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 ≤ ''D'' ≤ 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.		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 ≤ ''D'' ≤ 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 ~~mimimum~~ worst-case absolute error on interval the interval <math>[0.5,1]</math> is:		The linear [[approximation]] with minimum 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>		:<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		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

HaydenWong: /* Slow division methods */ remove redundant whitespaces

2025-02-10T07:06:31Z

Slow division methods: remove redundant whitespaces

← Previous revision		Revision as of 07:06, 10 February 2025
Line 111:		Line 111:

	==Slow division methods==		==Slow division methods==
	Slow division methods are all based on a standard recurrence equation <ref>{{Cite book\|last1=Morris\|first1=James E.\| url=https://books.google.com/books?id=wAhEDwAAQBAJ&q=restoring+division+fixed-point+fractional+numbers&pg=PA243\| title=Nanoelectronic Device Applications Handbook\|last2=Iniewski\|first2=Krzysztof\|date=2017-11-22\|publisher=CRC Press\| isbn=978-1-351-83197-0\|language=en}}</ref>		Slow division methods are all based on a standard recurrence equation<ref>{{Cite book\|last1=Morris\|first1=James E.\| url=https://books.google.com/books?id=wAhEDwAAQBAJ&q=restoring+division+fixed-point+fractional+numbers&pg=PA243\| title=Nanoelectronic Device Applications Handbook\|last2=Iniewski\|first2=Krzysztof\|date=2017-11-22\|publisher=CRC Press\| isbn=978-1-351-83197-0\|language=en}}</ref>
	:<math>R_{j+1} = B \times R_j - q_{n-(j+1)}\times D ,</math>		:<math>R_{j+1} = B \times R_j - q_{n-(j+1)}\times D ,</math>
	where:		where:
Line 121:		Line 121:

	===Restoring division===		===Restoring division===
	Restoring division operates on [[fixed point arithmetic\|fixed-point]] fractional numbers and depends on the assumption 0 < ''D'' < ''N''. {{citation needed\|date=February 2012}} <!-- see "Integer division (unsigned) with remainder" on talk -->		Restoring division operates on [[fixed point arithmetic\|fixed-point]] fractional numbers and depends on the assumption 0 < ''D'' < ''N''.{{citation needed\|date=February 2012}} <!-- see "Integer division (unsigned) with remainder" on talk -->

	The quotient digits ''q'' are formed from the digit set {0,1}.		The quotient digits ''q'' are formed from the digit set {0,1}.

Citation bot: Altered pages. Formatted dashes. | Use this bot. Report bugs. | Suggested by Abductive | Category:Wikipedia articles needing factual verification from January 2025 | #UCB_Category 91/287

2025-02-09T02:02:00Z

Altered pages. Formatted dashes. | Use this bot. Report bugs. | Suggested by Abductive | Category:Wikipedia articles needing factual verification from January 2025 | #UCB_Category 91/287

← Previous revision		Revision as of 02:02, 9 February 2025
Line 334:		Line 334:
	\|chapter=Chapter 7: Reciprocal. Division, Reciprocal Square Root, and Square Root by Iterative Approximation		\|chapter=Chapter 7: Reciprocal. Division, Reciprocal Square Root, and Square Root by Iterative Approximation
	\|first1=Miloš D. \|last1=Ercegovac \|first2=Tomás \|last2=Lang		\|first1=Miloš D. \|last1=Ercegovac \|first2=Tomás \|last2=Lang
	\|pages=~~367-395~~		\|pages=367–395
	\|year=2004 \|publisher=Morgan Kaufmann \|isbn=1-55860-798-6		\|year=2004 \|publisher=Morgan Kaufmann \|isbn=1-55860-798-6
	}}</ref>{{rp\|370}} This can simplify a following rounding step if an exactly-rounded quotient is required.		}}</ref>{{rp\|370}} This can simplify a following rounding step if an exactly-rounded quotient is required.

2409:4060:2E06:6102:C7A4:A771:51DA:6C50: /* Example */

2025-02-06T03:15:19Z

Example

← Previous revision		Revision as of 03:15, 6 February 2025
Line 80:		Line 80:

	====Example====		====Example====
		⚫	If we take N=1100<sub>2</sub> (12<sub>10</sub>) and D=100<sub>2</sub> (4<sub>10</sub>)
	If we take N
⚫	1100<sub>2</sub> (12<sub>10</sub>) and D=100<sub>2</sub> (4<sub>10</sub>)

	''Step 1'': Set R=0 and Q=0 <br />		''Step 1'': Set R=0 and Q=0 <br />

2409:4060:2E06:6102:C7A4:A771:51DA:6C50: /* Example */

2025-02-06T03:14:56Z

Example

← Previous revision		Revision as of 03:14, 6 February 2025
Line 80:		Line 80:

	====Example====		====Example====
	If we take N=1100<sub>2</sub> (12<sub>10</sub>) and D=100<sub>2</sub> (4<sub>10</sub>)		If we take N
			1100<sub>2</sub> (12<sub>10</sub>) and D=100<sub>2</sub> (4<sub>10</sub>)

	''Step 1'': Set R=0 and Q=0 <br />		''Step 1'': Set R=0 and Q=0 <br />

97.102.205.224: /* Fast division methods */ Use \varpsilon consistently for error, rather than a mix of that, \epsilon, and E.

2025-01-26T13:19:01Z

Fast division methods: Use \varpsilon consistently for error, rather than a mix of that, \epsilon, and E.

← Previous revision		Revision as of 13:19, 26 January 2025
Line 240:		Line 240:

	The best quadratic fit to <math>1/D</math> in the interval is		The best quadratic fit to <math>1/D</math> in the interval is
	:<math> X := \frac{140}{33} + ~~D \cdot \left(~~\frac{-64}{11} + D ~~\cdot~~ \frac{256}{99}~~\right)~~ .</math>		:<math> X := \frac{140}{33} - \frac{64}{11} D + \frac{256}{99} D^2.</math>
	It is chosen to make the error equal to a re-scaled third order [[Chebyshev polynomial]] of the first kind, and gives an absolute value of the error less than or equal to 1/99. This improvement is equivalent to <math>\log_2(\log 99/\log 17) \approx 0.7</math> Newton–Raphson iterations, at a computational cost of less than one iteration.		It is chosen to make the error equal to a re-scaled third order [[Chebyshev polynomial]] of the first kind, and gives an absolute value of the error less than or equal to 1/99. This improvement is equivalent to <math>\log_2(\log 99/\log 17) \approx 0.7</math> Newton–Raphson iterations, at a computational cost of less than one iteration.

	It is possible to generate a polynomial fit of degree larger than 2, computing the coefficients using the [[Remez algorithm]]. The trade-off is that the initial guess requires more computational cycles but hopefully in exchange for fewer iterations of Newton–Raphson.		It is possible to generate a polynomial fit of degree larger than 2, computing the coefficients using the [[Remez algorithm]]. The trade-off is that the initial guess requires more computational cycles but hopefully in exchange for fewer iterations of Newton–Raphson.

	Since for this method the [[rate of convergence\|convergence]] is exactly quadratic, it follows that, from an initial error <math>\~~epsilon_0~~</math>, <math>S</math> iterations will give an answer accurate to		Since for this method the [[rate of convergence\|convergence]] is exactly quadratic, it follows that, from an initial error <math>\varepsilon_0</math>, <math>S</math> iterations will give an answer accurate to
	:<math>P = -2^S \log_2 \~~epsilon_0~~ - 1 = 2^S \log_2(1/\~~epsilon_0~~) - 1</math>		:<math>P = -2^S \log_2 \varepsilon_0 - 1 = 2^S \log_2(1/\varepsilon_0) - 1</math>
	binary places. Typical values are:		binary places. Typical values are:
	{\|class=wikitable style="text-align:right;"		{\|class=wikitable style="text-align:right;"
	\|+ Binary digits of reciprocal accuracy		\|+ Binary digits of reciprocal accuracy
	!rowspan=2\| <math>\~~epsilon_0~~</math> \|\|colspan=5\| Iterations		!rowspan=2\| <math>\varepsilon_0</math> \|\|colspan=5\| Iterations
	\|-		\|-
	! 0 \|\| 1 \|\| 2 \|\| 3 \|\| 4		! 0 \|\| 1 \|\| 2 \|\| 3 \|\| 4
Line 286:		Line 286:
	====Cubic iteration====		====Cubic iteration====
	There is an iteration which uses three multiplications to cube the error:		There is an iteration which uses three multiplications to cube the error:
	:<math> ~~E_i~~ = 1 - D ~~\cdot~~ X_i </math>		:<math> \varepsilon_i = 1 - D X_i </math>
	:<math> Y_i = X_i \~~cdot E_i~~ </math>		:<math> Y_i = X_i \varepsilon_i </math>
	:<math> X_{i+1} = X_i + Y_i + Y_i \~~cdot E_i~~ .</math>		:<math> X_{i+1} = X_i + Y_i + Y_i \varepsilon_i .</math>
	The ''Y<sub>i</sub>~~''⋅''E~~<sub>i</sub>'' term is new.		The ''Y<sub>i</sub>ε<sub>i</sub>'' term is new.

	Expanding out the above, <math>X_{i+1}</math> can be written as		Expanding out the above, <math>X_{i+1}</math> can be written as
	:<math>\begin{align}		:<math>\begin{align}
	X_{i+1} &= X_i + ~~X_iE_i~~ + ~~X_iE_i~~^2 \\		X_{i+1} &= X_i + X_i\varepsilon_i + X_i\varepsilon_i^2 \\
	&= X_i + X_i(1-DX_i) + X_i(1-DX_i)^2 \\		&= X_i + X_i(1-DX_i) + X_i(1-DX_i)^2 \\
	&= 3X_i - 3DX_i^2 + D^2X_i^3 ,		&= 3X_i - 3DX_i^2 + D^2X_i^3 ,
Line 299:		Line 299:
	with the result that the error term		with the result that the error term
	:<math>\begin{align}		:<math>\begin{align}
	E_{i+1} &= 1 - DX_{i+1} \\		\varepsilon_{i+1} &= 1 - DX_{i+1} \\
	&= 1 - 3DX_i + 3D^2X_i^2 - D^3X_i^3 \\		&= 1 - 3DX_i + 3D^2X_i^2 - D^3X_i^3 \\
	&= (1 - DX_i)^3 \\		&= (1 - DX_i)^3 \\
	&= ~~E_i~~^3 .		&= \varepsilon_i^3 .
	\end{align}</math>		\end{align}</math>

Line 308:		Line 308:

	The number of correct bits after <math>S</math> iterations is		The number of correct bits after <math>S</math> iterations is
	:<math>P = -3^S \log_2 \~~epsilon_0~~ - 1 = 3^S \log_2(1/\~~epsilon_0~~) - 1</math>		:<math>P = -3^S \log_2 \varepsilon_0 - 1 = 3^S \log_2(1/\varepsilon_0) - 1</math>
	binary places. Typical values are:		binary places. Typical values are:
	{\|class=wikitable style="text-align:right;"		{\|class=wikitable style="text-align:right;"
	\|+ Bits of reciprocal accuracy		\|+ Bits of reciprocal accuracy
	!rowspan=2\| <math>\~~epsilon_0~~</math> \|\|colspan=4\| Iterations		!rowspan=2\| <math>\varepsilon_0</math> \|\|colspan=4\| Iterations
	\|-		\|-
	! 0 \|\| 1 \|\| 2 \|\| 3		! 0 \|\| 1 \|\| 2 \|\| 3

97.102.205.224: /* Cubic iteration */ Contrast precision of 2x cubic with 3x quadratic. Mention one-sided error.

2025-01-20T15:18:10Z

Cubic iteration: Contrast precision of 2x cubic with 3x quadratic. Mention one-sided error.

← Previous revision		Revision as of 15:18, 20 January 2025
Line 328:		Line 328:
	\| {{round\|{{#expr:27*(ln99/ln2) - 1}}\|2}}		\| {{round\|{{#expr:27*(ln99/ln2) - 1}}\|2}}
	\|}		\|}
	It is also possible to use a mixture of quadratic and cubic iterations.		A quadratic initial estimate plus two cubic iterations provides ample precision for an IEEE double-precision result. It is also possible to use a mixture of quadratic and cubic iterations.

			Using at least one quadratic iteration ensures that the error is positive, i.e. the reciprocal is underestimated.<ref name=DigitalArithmetic>{{cite book
			\|title=Digital Arithmetic
			\|chapter=Chapter 7: Reciprocal. Division, Reciprocal Square Root, and Square Root by Iterative Approximation
			\|first1=Miloš D. \|last1=Ercegovac \|first2=Tomás \|last2=Lang
			\|pages=367-395
			\|year=2004 \|publisher=Morgan Kaufmann \|isbn=1-55860-798-6
			}}</ref>{{rp\|370}} This can simplify a following rounding step if an exactly-rounded quotient is required.

	Using higher degree polynomials in either the initialization or the iteration results in a degradation of performance because the extra multiplications required would be better spent on doing more iterations.{{cn\|date=January 2025}}		Using higher degree polynomials in either the initialization or the iteration results in a degradation of performance because the extra multiplications required would be better spent on doing more iterations.{{cn\|date=January 2025}}