Barrett's method

The Barrett reduction is an algorithm for the efficient division of large numbers. Whole numbers of length and with are allowed as input . The algorithm works in every number system ; On the calculator, a power of two like or is recommended as a base number. In addition to the quotient , the rest is also returned . ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle n\leq m\leq 2n}$ ${\displaystyle 2^{32}}$ ${\displaystyle 2^{64}}$

The Barrett method is only worthwhile from around 1.5 million decimal places; below that, the Burnikel-Ziegler process is faster. With a sufficient number of divisions by the same number, however, the Barrett's method has an advantage, since the reciprocal can be reused.

description

The division of two numbers and using the Barrett's algorithm takes place in three steps. In the first step, an approximation of ( is the length of ) is calculated using the Newton method , whereby only multiplications, additions and subtractions are required. In the second step, the approximate value is multiplied by, which results in an approximation of . Finally, the exact value is calculated from the approximation, with steps being sufficient. ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle {\tfrac {2^{m}}{b}}}$ ${\displaystyle m}$ ${\displaystyle a}$ ${\displaystyle a}$ ${\displaystyle {\tfrac {2^{m}\cdot a}{b}}}$ ${\displaystyle O(1)}$

Extension to any whole numbers

If the initial values and do not meet the condition (i.e. is more than twice as long as ), the length is divided into sections and each section is treated as a digit. The number is then divided by the school method , with the individual “digits” being divided using the Barrett's method. This can be done efficiently because you only have to calculate the (binary shifted) reciprocal value once and the divisor only has one “digit” (the length ). ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle n\leq m\leq 2n}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle \leq n}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle {\tfrac {2^{m}}{b}}}$ ${\displaystyle b}$ ${\displaystyle n}$

use

The Barrett algorithm is used in GMP .

Web links

• Comparison of Barrett and Burnikel-Ziegler methods; contains a description of the Barrett process on p. 17 (PDF file; 565 kB)

Individual evidence

1. ↑ http://gmplib.org/manual/Block_002dWise-Barrett-Division.html