7092:
6201:
7070:
3762:
784: – also known as the partial quotients method or the hangman method – is a less-efficient form of long division which may be easier to understand. By allowing one to subtract more multiples than what one currently has at each stage, a more freeform variant of long division can be developed as well.
5875:
2270:
possibilities: { −2, −1, 0, +1, +2 }. Because of this, the choice of a quotient digit need not be perfect; later quotient digits can correct for slight errors. (For example, the quotient digit pairs (0, +2) and (1, −2) are equivalent, since 0×4+2 = 1×4−2.) This tolerance allows quotient digits to
772:
Long division is the standard algorithm used for pen-and-paper division of multi-digit numbers expressed in decimal notation. It shifts gradually from the left to the right end of the dividend, subtracting the largest possible multiple of the divisor (at the digit level) at each stage; the multiples
5684:
Athlon CPUs and later models. It is also known as
Anderson Earle Goldschmidt Powers (AEGP) algorithm and is implemented by various IBM processors. Although it converges at the same rate as a Newton–Raphson implementation, one advantage of the Goldschmidt method is that the multiplications in the
1585:
Non-restoring division uses the digit set {−1, 1} for the quotient digits instead of {0, 1}. The algorithm is more complex, but has the advantage when implemented in hardware that there is only one decision and addition/subtraction per quotient bit; there is no restoring step after the
6928:
3025:
3500:
5398:
3775:, a property that becomes extremely valuable when the numbers involved have many digits (e.g. in the large integer domain). But it also means that the initial convergence of the method can be comparatively slow, especially if the initial estimate
4975:
5635:
5217:
6563:
algorithms. Newton's method is particularly efficient in scenarios where one must divide by the same divisor many times, since after the initial Newton inversion only one (truncated) multiplication is needed for each division.
6196:{\displaystyle {\frac {N}{1-x}}={\frac {N\cdot (1+x)}{1-x^{2}}}={\frac {N\cdot (1+x)\cdot (1+x^{2})}{1-x^{4}}}=\cdots =Q'={\frac {N'=N\cdot (1+x)\cdot (1+x^{2})\cdot \cdot \cdot (1+x^{2^{(n-1)}})}{D'=1-x^{2^{n}}\approx 1}}}
4702:
4846:
753:
This procedure always produces R ≥ 0. Although very simple, it takes Ω(Q) steps, and so is exponentially slower than even slow division algorithms like long division. It is useful if Q is known to be small (being an
6403:
4605:
2223:
The actual remainder is R >> n. (As with restoring division, the low-order bits of R are used up at the same rate as bits of the quotient Q are produced, and it is common to use a single shift register for both.)
8328:
7538:
This rounding causes a small error, which can propagate and accumulate through subsequent calculations. Such errors are particularly pronounced in iterative processes and when subtracting nearly equal values - is told
2764:
2151:
Finally, quotients computed by this algorithm are always odd, and the remainder in R is in the range −D ≤ R < D. For example, 5 / 2 = 3 R −1. To convert to a positive remainder, do a single restoring step
7065:{\displaystyle \left\lfloor {\frac {N}{D}}\right\rfloor =\left\lfloor {\frac {\left\lfloor {\frac {N-b}{2}}\right\rfloor +b}{2^{k-x-1}}}\right\rfloor {\text{ where }}b=\left\lfloor {\frac {Na}{2^{x}}}\right\rfloor }
9204:
6920:
5267:
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.
6270:
1586:
subtraction, which potentially cuts down the numbers of operations by up to half and lets it be executed faster. The basic algorithm for binary (radix 2) non-restoring division of non-negative numbers is:
8288:
3919:
1275:
2271:
be selected using only a few most-significant bits of the dividend and divisor, rather than requiring a full-width subtraction. This simplification in turn allows a radix higher than 2 to be used.
75:
Division algorithms fall into two main categories: slow division and fast division. Slow division algorithms produce one digit of the final quotient per iteration. Examples of slow division include
4111:
4017:
1861:
3757:{\displaystyle {\begin{aligned}\varepsilon _{i+1}&=1-DX_{i+1}\\&=1-D(X_{i}(2-DX_{i}))\\&=1-2DX_{i}+D^{2}X_{i}^{2}\\&=(1-DX_{i})^{2}\\&={\varepsilon _{i}}^{2}.\\\end{aligned}}}
5782:
3505:
4421:
6859:
8647:
3146:
1782:
Following this algorithm, the quotient is in a non-standard form consisting of digits of −1 and +1. This form needs to be converted to binary to form the final quotient. Example:
9208:
6523:. For these large integers, more efficient division algorithms transform the problem to use a small number of multiplications, which can then be done using an asymptotically efficient
3492:
2511:
3217:
5295:
4188:
8716:
8322:
6478:
5867:
4317:
5510:
5111:
7253:
7441:
7414:
7388:
5030:
7358:
7309:
4506:
4257:
2756:
1986:
1927:
1894:
6310:
5255:
5063:
4891:
4462:
2274:
Like non-restoring division, the final steps are a final full-width subtraction to resolve the last quotient bit, and conversion of the quotient to standard binary form.
6443:
3440:
3390:
3290:
4549:
2681:
153:
8749:
2550:
6515:
Methods designed for hardware implementation generally do not scale to integers with thousands or millions of decimal digits; these frequently occur, for example, in
5675:
6505:
5814:
3830:
3800:
3348:
3317:
3248:
3055:
2637:
2401:
4217:
2603:
8348:
7897:
7612:
commonly perform this integer multiply-and-shift optimization; for a constant only known at run-time, however, the program must implement the optimization itself.
5725:
5521:
4726:
2429:
1957:
87:
division. Fast division methods start with a close approximation to the final quotient and produce twice as many digits of the final quotient on each iteration.
7329:
7280:
7166:
7143:
2701:
2574:
2449:
2366:
2344:
2324:
2278:
2106:
2086:
2066:
2044:
2024:
7534:
7209:
6773:, then rounded up. Likewise, division by 10 can be expressed as a multiplication by 3435973837 (0xCCCCCCCD) followed by division by 2 (or 35 right bit shift).
5141:
3954:
5276:
Goldschmidt division (after Robert
Elliott Goldschmidt) uses an iterative process of repeatedly multiplying both the dividend and divisor by a common factor
2252:. They all developed the algorithm independently at approximately the same time (published in February 1957, September 1958, and January 1958 respectively).
8508:
9073:
8709:
7654:
6543:
of the division is of the same order (up to a multiplicative constant) as that of the multiplication. Examples include reduction to multiplication by
4627:
8179:
8041:
4777:
4557:
9279:
8238:
8083:
329:) gives rise to a complete division algorithm, applicable to both negative and positive numbers, using additions, subtractions, and comparisons:
106:
needed for a division is the same, up to a constant factor, as the time needed for a multiplication, whichever multiplication algorithm is used.
4614:. The trade-off is that the initial guess requires more computational cycles but hopefully in exchange for fewer iterations of Newton–Raphson.
8941:
7595:
Despite how "little" problem the optimization causes, this reciprocal optimization is still usually hidden behind a "fast math" flag in modern
2703:(moreover it attempts to compute the exact reciprocal in one step, rather than allow for iterative improvements). A function that does work is
8009:
7984:
8570:
7664:
8883:
8702:
7876:
8812:
8591:
8107:
8989:
6864:
6536:
6214:
4984:
and gives an absolute value of the error less than or equal to 1/99. It is chosen to make the error equal to a re-scaled third order
8787:
8375:
8165:
6325:
3020:{\displaystyle X_{i+1}=X_{i}-{f(X_{i}) \over f'(X_{i})}=X_{i}-{1/X_{i}-D \over -1/X_{i}^{2}}=X_{i}+X_{i}(1-DX_{i})=X_{i}(2-DX_{i}),}
8898:
8936:
8873:
8817:
8780:
3854:
2683:, but the Newton–Raphson iteration for this is unhelpful, since it cannot be computed without already knowing the reciprocal of
1188:
9274:
9078:
8969:
8888:
8878:
7750:
776:
When used with a binary radix, this method forms the basis for the (unsigned) integer division with remainder algorithm below.
8754:
7784:
7075:
In some cases, division by a constant can be accomplished in even less time by converting the "multiply by a constant" into a
6718:, but "close enough" that the error introduced by the approximation is in the bits that are discarded by the shift operation.
8906:
7717:
9159:
4025:
3962:
3924:
to initialize Newton–Raphson. To minimize the maximum of the absolute value of the error of this approximation on interval
1798:
7942:
9154:
9083:
8984:
8481:
8425:
7848:
6532:
5736:
9269:
9121:
9035:
8680:
7634:
6635:) may be used. For example, for division by 3, the factors 1/3, 2/6, 3/9, or 194/582 could be used. Consequently, if
4322:
6811:
3771:
of Newton–Raphson's method – has the effect that the number of correct digits in the result roughly
222:, Book VII, Proposition 1, finds the remainder given two positive integers using only subtractions and comparisons:
9264:
9200:
9190:
9149:
8925:
8919:
8893:
8764:
8364:"Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor"
6609:
4865:
For example, for a double-precision floating-point division, this method uses 10 multiplies, 9 adds, and 2 shifts.
3067:
2266:
is used for the quotient. For example, when implementing radix-4 SRT division, each quotient digit is chosen from
755:
7079:. Of particular interest is division by 10, for which the exact quotient is obtained, with remainder if required.
9185:
9126:
8627:
7548:
7540:
7259:
9088:
8961:
8807:
8759:
7571:
7076:
6552:
6540:
6524:
5393:{\displaystyle Q={\frac {N}{D}}{\frac {F_{1}}{F_{1}}}{\frac {F_{2}}{F_{2}}}{\frac {F_{\ldots }}{F_{\ldots }}}.}
3448:
2457:
103:
99:
35:
6808:-bit multiplication (where only the upper half of the result is used) and several shifts, after precomputing
3151:
9103:
8994:
8563:
8505:
4120:
4114:
2249:
1573:
Non-performing restoring division is similar to restoring division except that the value of 2R is saved, so
212:
5285:, chosen such that the divisor converges to 1. This causes the dividend to converge to the sought quotient
4022:
The coefficients of the linear approximation are determined as follows. The absolute value of the error is
3058:
9214:
9164:
9144:
8407:
7822:
6734:
6577:
4610:
It is possible to generate a polynomial fit of degree larger than 1, computing the coefficients using the
2303:
2241:
1356:
8142:
8032:
8865:
8840:
8769:
8652:
6639:
were a power of two the division step would reduce to a fast right bit shift. The effect of calculating
4763:
Express D as M × 2 where 1 ≤ M < 2 (standard floating point representation) D' := D / 2
9224:
8066:
7740:"Stanford EE486 (Advanced Computer Arithmetic Division) – Chapter 5 Handout (Division)"
6448:
5819:
4262:
2285:
was caused by an incorrectly coded lookup table. Five of the 1066 entries had been mistakenly omitted.
5460:
5069:
9219:
9111:
9093:
9068:
9030:
8774:
7693:
6560:
4985:
1568:-- Where: N = numerator, D = denominator, n = #bits, R = partial remainder, q(i) = bit #i of quotient
216:
8530:
8143:"Floating point division and square root algorithms and implementation in the AMD-K7 Microprocessor"
7216:
4970:{\displaystyle X:={\frac {140}{33}}+D\cdot \left({\frac {-64}{11}}+D\cdot {\frac {256}{99}}\right).}
4873:
The Newton-Raphson division method can be modified to be slightly faster as follows. After shifting
9229:
9195:
9116:
9020:
8979:
8974:
8951:
8855:
8553:
8005:
7964:
7827:
7419:
7392:
7366:
6528:
4997:
4618:
1997:
1993:
781:
30:
This article is about algorithms for division of integers. For the pencil-and-paper algorithm, see
8412:
7334:
7285:
4467:
4319:. The function at that minimum must be of opposite sign as the function at the endpoints, namely,
2706:
1964:
1905:
1872:
9060:
9004:
8845:
8744:
8473:
8171:
6516:
6275:
5228:
5036:
4737:
4426:
1472:-- Trial subtraction from shifted value (multiplication by 2 is a shift in binary representation)
326:
69:
8801:
8794:
7937:
7870:
6544:
6411:
3768:
3403:
3353:
3253:
2299:
8586:
7168:
are approximated to fit within the computer’s precision limits. The
Division Algorithm states:
4551:. Using this approximation, the absolute value of the error of the initial value is less than
4511:
2642:
112:
72:. Some are applied by hand, while others are employed by digital circuit designs and software.
9180:
9136:
8850:
8827:
8632:
8566:
8371:
8342:
8161:
8075:
7891:
7709:
7660:
6719:
6556:
2519:
6659:
replaces a division with a multiply and a shift. Note that the parentheses are important, as
5647:
4222:
9025:
8465:
8417:
8267:
8216:
8153:
8119:
7976:
7932:
7924:
7840:
7832:
7701:
7576:
5694:
5630:{\displaystyle {\frac {N_{i+1}}{D_{i+1}}}={\frac {N_{i}}{D_{i}}}{\frac {F_{i+1}}{F_{i+1}}}.}
4733:
4729:
2282:
6483:
5787:
3808:
3778:
3326:
3295:
3226:
3033:
2608:
2379:
1777:-- Note: N=numerator, D=denominator, n=#bits, R=partial remainder, q(i)=bit #i of quotient.
9015:
8914:
8595:
8512:
7566:
7361:
5427:
If the divisor is sufficiently close to 1, return the dividend, otherwise, loop to step 1.
4611:
4193:
2579:
5702:
5212:{\displaystyle \left\lceil \log _{3}\left({\frac {P+1}{\log _{2}99}}\right)\right\rceil }
4710:
2406:
1936:
1330:+1), where the digit positions are numbered from least-significant 0 to most significant
7697:
6757:
0xAAAAAAAB) followed by a 33 right bit shift. The value of 2863311531 is calculated as
6737:
example, for 32-bit unsigned integers, division by 3 can be replaced with a multiply by
773:
then become the digits of the quotient, and the final difference is then the remainder.
9045:
8946:
8931:
8835:
8736:
8559:
7555:
7314:
7265:
7151:
7128:
6601:
6317:
2686:
2559:
2434:
2351:
2329:
2309:
2233:
2091:
2071:
2051:
2029:
2009:
777:
7448:
7173:
7091:
3927:
9258:
9040:
8725:
7739:
3845:
3223:
bits while making use of the second expression, one must compute the product between
799:
793:
767:
31:
8477:
8175:
17:
9050:
8204:
7775:
6520:
5730:
2516:
Compute the quotient by multiplying the dividend by the reciprocal of the divisor:
2256:
2245:
5693:
The
Goldschmidt method can be used with factors that allow simplifications by the
4765:// scale between 0.5 and 1, can be performed with bit shift / exponent subtraction
3767:
This squaring of the error at each iteration step – the so-called
8296:(M.Sc. in Computer Science thesis). Royal Institute of Technology. Archived from
7681:
7544:
6754:
4697:{\displaystyle S=\left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,}
8272:
8255:
8127:
7912:
2513:
of the reciprocal. This is where one employs the Newton–Raphson method as such.
2088:
is trivial: perform a ones' complement (bit by bit complement) on the original
8694:
8363:
8157:
7836:
7810:
4841:{\displaystyle \left\lceil \log _{2}{\frac {P+1}{\log _{2}17}}\right\rceil \,}
4113:. The minimum of the maximum absolute value of the error is determined by the
818:. In the following pseudo-code, all values are treated as unsigned integers.
8450:
8392:
7980:
7928:
7713:
4988:
of the first kind. The coefficients should be pre-calculated and hard-coded.
4600:{\displaystyle \vert \varepsilon _{0}\vert \leq {1 \over 17}\approx 0.059.\,}
325:
The proof that the quotient and remainder exist and are unique (described at
8728:
8585:
LaBudde, Robert A.; Golovchenko, Nikolai; Newton, James; and Parker, David;
8079:
7774:
Harris, David L.; Oberman, Stuart F.; Horowitz, Mark A. (9 September 1998).
7609:
7146:
197:
65:
46:
8672:
8297:
6796:
is not a power of 2, the following identity converts the division into two
8421:
8150:
Proceedings 14th IEEE Symposium on
Computer Arithmetic (Cat. No.99CB36336)
7965:"Techniques of Multiplication and Division for Automatic Binary Computers"
7596:
7123:
780:
is an abbreviated form of long division suitable for one-digit divisors.
188:
173:
163:
61:
8506:"Labor of Division (Episode III): Faster Unsigned Division by Constants"
8469:
8123:
3844:, one ensures the quotient does not change. Then one could use a linear
2259:
based on the dividend and the divisor to determine each quotient digit.
2146:-- Appropriate if −1 digits in Q are represented as zeros as is common.
1182:
Slow division methods are all based on a standard recurrence equation
50:
8220:
7844:
7705:
964:-- Set the least-significant bit of R equal to bit i of the numerator
6915:{\displaystyle a=\left\lceil {\frac {2^{k}}{D}}\right\rceil -2^{x}}
6588:) once at compile time, and at run time perform the multiplication
6612:
arithmetic the reciprocal will always evaluate to zero (assuming |
1303:
211:
The simplest division algorithm, historically incorporated into a
8256:"A parametric error analysis of Goldschmidt's division algorithm"
2255:
SRT division is similar to non-restoring division, but it uses a
60:(respectively the numerator and the denominator), computes their
6774:
6265:{\displaystyle \left(x\in \left[0,{\tfrac {1}{2}}\right)\right)}
5222:
which is the number of times 99 must be cubed to get to 2. Then
4423:. The two equations in the two unknowns have a unique solution
3840: ≤ 1; by applying the same bit-shift to the numerator
1377:
The basic algorithm for binary (radix 2) restoring division is:
8698:
2236:
implementations. The algorithm is named after D. W. Sweeney of
8254:
Guy, Even; Peter, Siedel; Ferguson, Warren (1 February 2005).
8233:
S. F. Anderson, J. G. Earle, R. E. Goldschmidt, D. M. Powers.
7086:
6580:. Since the denominator is constant, so is its reciprocal (1/
6398:{\displaystyle \varepsilon _{n}={\frac {Q'-N'}{Q'}}=x^{2^{n}}}
5681:
2237:
8205:"Division and Square Root: Choosing the Right Implementation"
3219:
are not equivalent. To obtain a result with a precision of 2
2556:
In order to apply Newton's method to find the reciprocal of
1577:
does not need to be added back in for the case of R < 0.
8290:
Fast
Division of Large Integers: A Comparison of Algorithms
6782:
6778:
5515:
Multiplying the dividend and divisor by the factor yields:
8648:"9. Machine Numbers, Rounding Error and Error Propagation"
7969:
The
Quarterly Journal of Mechanics and Applied Mathematics
7543:. To mitigate these errors, techniques such as the use of
6777:
provides sequences of the constants for multiplication as
5685:
numerator and in the denominator can be done in parallel.
4991:
Then in the loop, use an iteration which cubes the error.
3914:{\displaystyle X_{0}=T_{1}+T_{2}D\approx {\frac {1}{D}}\,}
1270:{\displaystyle R_{j+1}=B\times R_{j}-q_{n-(j+1)}\times D,}
798:
The following algorithm, the binary version of the famous
8526:
5135:
bits, then the number of iterations will be no more than
1306:(base, usually 2 internally in computers and calculators)
8040:(Technical report). Stanford University. CSL-TR-95-675.
7777:
3057:
using only multiplication and subtraction, or using two
2156:
Q is converted from non-standard form to standard form:
1359:
fractional numbers and depends on the assumption 0 <
9245:
indicate that algorithm is for numbers of special forms
8249:
8247:
8235:
The IBM 360/370 model 91: floating-point execution unit
7642:(Technical report). Microsoft Research, Silicon Valley.
7103:
3832:, it is convenient to apply a bit-shift to the divisor
1788:
Convert the following quotient to the digit set {0,1}:
8391:
Granlund, Torbjörn; Montgomery, Peter L. (June 1994).
8203:
Soderquist, Peter; Leeser, Miriam (July–August 1997).
8034:
An
Analysis of Division Algorithms and Implementations
6459:
6241:
5752:
4106:{\displaystyle |\varepsilon _{0}|=|1-D(T_{1}+T_{2}D)|}
2232:
SRT division is a popular method for division in many
8393:"Division by Invariant Integers using Multiplication"
7451:
7422:
7395:
7369:
7337:
7317:
7288:
7268:
7219:
7176:
7154:
7131:
6931:
6867:
6814:
6486:
6451:
6414:
6328:
6278:
6217:
5878:
5822:
5790:
5739:
5705:
5650:
5524:
5463:
5298:
5231:
5144:
5072:
5039:
5000:
4894:
4780:
4713:
4630:
4560:
4514:
4470:
4429:
4325:
4265:
4225:
4196:
4123:
4028:
4012:{\displaystyle X_{0}={48 \over 17}-{32 \over 17}D.\,}
3965:
3930:
3857:
3811:
3781:
3503:
3451:
3406:
3356:
3329:
3298:
3256:
3229:
3154:
3070:
3036:
2767:
2709:
2689:
2645:
2611:
2582:
2562:
2522:
2460:
2437:
2409:
2382:
2354:
2332:
2312:
2094:
2074:
2054:
2032:
2012:
1967:
1939:
1908:
1875:
1856:{\displaystyle Q=111{\bar {1}}1{\bar {1}}1{\bar {1}}}
1801:
1191:
115:
7653:
Morris, James E.; Iniewski, Krzysztof (2017-11-22).
1559:-- New partial remainder is (restored) shifted value
1061:: Take i=3 (one less than the number of bits in N)
9173:
9135:
9102:
9059:
9003:
8960:
8864:
8826:
8735:
8449:Möller, Niels; Granlund, Torbjörn (February 2011).
8031:Oberman, Stuart F.; Flynn, Michael J. (July 1995).
6686:
that satisfies the conditions above. Fortunately, (
5777:{\displaystyle D\in \left({\tfrac {1}{2}},1\right]}
5407:Generate an estimate for the multiplication factor
3805:For the subproblem of choosing an initial estimate
8368:Proceedings on Advances in cryptology---CRYPTO '86
7528:
7435:
7408:
7382:
7352:
7323:
7303:
7274:
7247:
7203:
7160:
7137:
7122:When a division operation is performed, the exact
7064:
6914:
6853:
6584:). Thus it is possible to compute the value of (1/
6499:
6472:
6437:
6397:
6304:
6264:
6195:
5861:
5808:
5776:
5719:
5669:
5629:
5504:
5392:
5249:
5211:
5105:
5057:
5024:
4969:
4840:
4720:
4696:
4599:
4543:
4500:
4456:
4415:
4311:
4251:
4211:
4182:
4105:
4011:
3948:
3913:
3824:
3794:
3756:
3486:
3434:
3384:
3342:
3311:
3284:
3242:
3211:
3140:
3064:From a computation point of view, the expressions
3049:
3019:
2750:
2695:
2675:
2631:
2597:
2568:
2544:
2505:
2443:
2423:
2395:
2360:
2338:
2318:
2100:
2080:
2060:
2038:
2018:
1980:
1951:
1921:
1888:
1855:
1269:
147:
34:. For the division algorithm for polynomials, see
8370:. London, UK: Springer-Verlag. pp. 311–323.
6792:-bit unsigned integer division where the divisor
768:Long division § Algorithm for arbitrary base
758:), and can serve as an executable specification.
4769:// precompute constants with same precision as D
4767:N' := N / 2 X := 48/17 − 32/17 × D'
7869:Cocke, John; Sweeney, D.W. (11 February 1957),
5127:If the loop is performed until X agrees with 1/
4416:{\displaystyle F(1/2)=F(1)=-F(-T_{1}/(2T_{2}))}
2758:, for which the Newton–Raphson iteration gives
2212:-- Needed only if the remainder is of interest.
1621:-- R and D need twice the word width of N and Q
1412:-- R and D need twice the word width of N and Q
7811:"SRT Division Algorithms as Dynamical Systems"
6854:{\displaystyle k=x+\lceil \log _{2}{D}\rceil }
4707:steps are enough to calculate the value up to
98:Variants of these algorithms allow using fast
8710:
8006:"Statistical Analysis of Floating Point Flaw"
3141:{\displaystyle X_{i+1}=X_{i}+X_{i}(1-DX_{i})}
2454:Compute successively more accurate estimates
8:
8321:Joachim Ziegler, Christoph Burnikel (1998),
7682:"Arithmetic Operations in a Binary Computer"
6848:
6827:
6548:
4728:binary places. This evaluates to 3 for IEEE
4574:
4561:
865:-- Initialize quotient and remainder to zero
88:
7656:Nanoelectronic Device Applications Handbook
6619:It is not necessary to use specifically (1/
6576:is equivalent to the multiplication by its
2026:are stored as zeros (0) as is common, then
1784:
102:. It results that, for large integers, the
80:
8717:
8703:
8695:
8347:: CS1 maint: location missing publisher (
7896:: CS1 maint: location missing publisher (
7872:High speed arithmetic in a parallel device
7809:McCann, Mark; Pippenger, Nicholas (2005).
3392:need only be computed with a precision of
2372:The steps of Newton–Raphson division are:
2262:The most significant difference is that a
788:Integer division (unsigned) with remainder
8588:Massmind: "Binary Division by a Constant"
8451:"Improved Division by Invariant Integers"
8411:
8271:
7936:
7913:"A New Class of Digital Division Methods"
7826:
7783:(Technical report). Stanford University.
7517:
7493:
7492:
7480:
7456:
7455:
7450:
7427:
7421:
7400:
7394:
7374:
7368:
7339:
7338:
7336:
7316:
7290:
7289:
7287:
7267:
7240:
7232:
7218:
7175:
7153:
7130:
7050:
7036:
7021:
6997:
6964:
6957:
6936:
6930:
6906:
6884:
6878:
6866:
6843:
6834:
6813:
6491:
6485:
6458:
6450:
6427:
6419:
6413:
6387:
6382:
6342:
6333:
6327:
6294:
6289:
6277:
6240:
6216:
6176:
6171:
6125:
6120:
6089:
6038:
6009:
5988:
5948:
5936:
5900:
5879:
5877:
5851:
5846:
5827:
5821:
5789:
5751:
5738:
5709:
5704:
5661:
5649:
5610:
5594:
5588:
5580:
5570:
5564:
5547:
5531:
5525:
5523:
5493:
5468:
5462:
5439:has been scaled so that 0 <
5379:
5369:
5363:
5355:
5345:
5339:
5331:
5321:
5315:
5305:
5297:
5230:
5185:
5167:
5154:
5143:
5071:
5038:
4999:
4949:
4925:
4901:
4893:
4837:
4817:
4799:
4790:
4779:
4717:
4712:
4693:
4673:
4655:
4646:
4629:
4596:
4580:
4568:
4559:
4533:
4513:
4490:
4475:
4469:
4446:
4434:
4428:
4401:
4386:
4380:
4335:
4324:
4300:
4285:
4279:
4264:
4224:
4195:
4168:
4155:
4122:
4098:
4086:
4073:
4052:
4044:
4038:
4029:
4027:
4008:
3992:
3979:
3970:
3964:
3929:
3910:
3900:
3888:
3875:
3862:
3856:
3816:
3810:
3786:
3780:
3741:
3734:
3729:
3712:
3702:
3670:
3665:
3655:
3642:
3604:
3582:
3544:
3512:
3504:
3502:
3487:{\displaystyle \varepsilon _{i}=1-DX_{i}}
3478:
3456:
3450:
3423:
3405:
3373:
3355:
3334:
3328:
3303:
3297:
3273:
3255:
3234:
3228:
3200:
3178:
3159:
3153:
3129:
3107:
3094:
3075:
3069:
3041:
3035:
3005:
2983:
2967:
2945:
2932:
2916:
2911:
2902:
2882:
2873:
2867:
2858:
2839:
2813:
2800:
2791:
2772:
2766:
2731:
2708:
2688:
2644:
2621:
2610:
2581:
2561:
2536:
2521:
2506:{\displaystyle X_{1},X_{2},\ldots ,X_{S}}
2497:
2478:
2465:
2459:
2436:
2413:
2408:
2387:
2381:
2353:
2331:
2311:
2093:
2073:
2053:
2031:
2011:
1977:
1966:
1938:
1918:
1907:
1885:
1874:
1842:
1841:
1827:
1826:
1812:
1811:
1800:
1322:is the digit of the quotient in position
1234:
1221:
1196:
1190:
119:
114:
92:
8607:Vowels, R. A. (1992). "Division by 10".
7917:IRE Transactions on Electronic Computers
6480:, thus providing a minimum precision of
5403:The steps for Goldschmidt division are:
3323:bits). In contrast, the product between
8527:"libdivide, optimized integer division"
8260:Journal of Computer and System Sciences
8239:IBM Journal of Research and Development
8112:IBM Journal of Research and Development
8068:Applications of Division by Convergence
7625:
7588:
4748:The following computes the quotient of
3212:{\displaystyle X_{i+1}=X_{i}(2-DX_{i})}
76:
8340:
8327:, Max-Planck-Institut für Informatik,
7889:
7077:series of shifts and adds or subtracts
6678:itself is a power of two, there is no
4853:// can be precomputed based on fixed P
4621:is exactly quadratic, it follows that
4183:{\displaystyle F(D)=1-D(T_{1}+T_{2}D)}
8533:from the original on 23 November 2021
8074:(Thesis). M.Sc. dissertation. M.I.T.
7790:from the original on 24 December 2016
5417:Multiply the dividend and divisor by
2576:, it is necessary to find a function
1374:are formed from the digit set {0,1}.
1296:-th partial remainder of the division
7:
8012:from the original on 23 October 2013
7633:Rodeheffer, Thomas L. (2008-08-26).
4980:This is the best quadratic fit to 1/
3836:to scale it so that 0.5 ≤
2283:infamous floating-point division bug
601:-- At this point, N ≥ 0 and D > 0
95:algorithms fall into this category.
7879:from the original on 24 August 2022
3292:with double the given precision of
1340:is number of digits in the quotient
6753:, a multiplication by 2863311531 (
6722:uses powers of 2 for the value of
6608:) presents little problem, but in
5680:The Goldschmidt method is used in
109:Discussion will refer to the form
27:Method for division with remainder
25:
8926:Special number field sieve (SNFS)
8920:General number field sieve (GNFS)
8626:L. Popyack, Jeffrey (June 2000).
7875:(Company Memo), IBM, p. 20,
6706:in integer arithmetic even when (
6698:gives exactly the same result as
6551:, as well as the slightly faster
6473:{\displaystyle x={\tfrac {1}{2}}}
5862:{\displaystyle F_{i}=1+x^{2^{i}}}
4312:{\displaystyle D=-T_{1}/(2T_{2})}
4115:Chebyshev equioscillation theorem
3400:bits (after the binary point) of
910:-- Where n is number of bits in N
84:
8673:"Advanced Arithmetic Techniques"
7686:Review of Scientific Instruments
7090:
5505:{\displaystyle F_{i+1}=2-D_{i}.}
5106:{\displaystyle X:=X+Y+Y\cdot E.}
2326:and multiply that reciprocal by
1992:*.( Signed binary notation with
1651:-- for example 31..0 for 32 bits
1445:-- For example 31..0 for 32 bits
1071:: R=01 (setting R(0) to N(i))
207:Division by repeated subtraction
8683:from the original on 2018-07-03
8487:from the original on 2015-12-22
8431:from the original on 2019-06-06
8331:from the original on 2011-04-26
8185:from the original on 2015-11-29
8089:from the original on 2015-12-10
8065:Goldschmidt, Robert E. (1964).
8047:from the original on 2017-05-17
7987:from the original on 2022-08-24
7945:from the original on 2022-08-24
7911:Robertson, James (1958-09-01).
7851:from the original on 2022-08-24
7756:from the original on 2022-04-18
7720:from the original on 2022-02-28
6800:-bit addition/subtraction, one
4869:Variant Newton–Raphson division
4855:X := X + X × (1 - D' × X)
2639:. The obvious such function is
1355:Restoring division operates on
1149:: R>=D, statement entered
1118:: R>=D, statement entered
1097:: R < D, statement skipped
1076:: R < D, so skip statement
9280:Computer arithmetic algorithms
8458:IEEE Transactions on Computers
7938:2027/uiuo.ark:/13960/t0gt7529c
7523:
7498:
7489:
7486:
7461:
7452:
7344:
7295:
7248:{\displaystyle 0\leq r<|b|}
7241:
7233:
7198:
7177:
6145:
6138:
6126:
6107:
6095:
6076:
6070:
6058:
5994:
5975:
5969:
5957:
5921:
5909:
4524:
4518:
4410:
4407:
4391:
4370:
4358:
4352:
4343:
4329:
4306:
4290:
4240:
4234:
4206:
4200:
4177:
4148:
4133:
4127:
4099:
4095:
4066:
4053:
4045:
4030:
3943:
3931:
3709:
3686:
3613:
3610:
3588:
3575:
3429:
3407:
3379:
3357:
3279:
3257:
3206:
3184:
3135:
3113:
3011:
2989:
2973:
2951:
2845:
2832:
2819:
2806:
2739:
2725:
2719:
2713:
2655:
2649:
2592:
2586:
1847:
1832:
1817:
1253:
1241:
142:
130:
1:
8552:Warren Jr., Henry S. (2013).
7436:{\displaystyle \epsilon _{r}}
7409:{\displaystyle \epsilon _{q}}
7383:{\displaystyle \epsilon _{q}}
5025:{\displaystyle E:=1-D\cdot X}
3030:which can be calculated from
794:Binary number § Division
8884:Lenstra elliptic curve (ECM)
8671:Savard, John J. G. (2018) .
7353:{\displaystyle {\tilde {r}}}
7304:{\displaystyle {\tilde {q}}}
6714:) is not exactly equal to 1/
6537:Schönhage–Strassen algorithm
4501:{\displaystyle T_{2}=-32/17}
2751:{\displaystyle f(X)=(1/X)-D}
1981:{\displaystyle Q=11010101\,}
1922:{\displaystyle M=00010101\,}
1889:{\displaystyle P=11101010\,}
1159:: Q=11 (setting Q(i) to 1)
1128:: Q=10 (setting Q(i) to 1)
1066:: R=00 (left shifted by 1)
79:, non-performing restoring,
8609:Australian Computer Journal
8141:Oberman, Stuart F. (1999).
8008:. Intel Corporation. 1994.
7963:Tocher, K.D. (1958-01-01).
7549:higher precision arithmetic
6781:and for the right shift as
6596:) rather than the division
6572:The division by a constant
6305:{\displaystyle 1-x^{2^{n}}}
5250:{\displaystyle Q:=N\cdot X}
5058:{\displaystyle Y:=X\cdot E}
4508:, and the maximum error is
4457:{\displaystyle T_{1}=48/17}
3773:doubles for every iteration
3445:If the error is defined as
1900:2. Mask the negative term*:
9296:
9191:Exponentiation by squaring
8874:Continued fraction (CFRAC)
8287:Hasselström, Karl (2003).
8273:10.1016/j.jcss.2004.08.004
7553:
6438:{\displaystyle 2^{-2^{n}}}
5640:After a sufficient number
4617:Since for this method the
3435:{\displaystyle (1-DX_{i})}
3396:bits, because the leading
3385:{\displaystyle (1-DX_{i})}
3285:{\displaystyle (2-DX_{i})}
1867:1. Form the positive term:
810:, placing the quotient in
791:
765:
756:output-sensitive algorithm
29:
9238:
8158:10.1109/ARITH.1999.762835
7837:10.1137/S009753970444106X
7815:SIAM Journal on Computing
7636:Software Integer Division
7260:floating-point arithmetic
6671:) will evaluate to zero.
6604:arithmetic the use of (1/
6553:Burnikel-Ziegler division
6539:. The result is that the
4544:{\displaystyle F(1)=1/17}
2676:{\displaystyle f(X)=DX-1}
1991:
1787:
148:{\displaystyle N/D=(Q,R)}
100:multiplication algorithms
7929:10.1109/TEC.1958.5222579
7680:Shaw, Robert F. (1950).
7572:Multiplication algorithm
6541:computational complexity
6533:Toom–Cook multiplication
6525:multiplication algorithm
5443: < 1, each
4885:is in , initialize with
4190:. The local minimum of
2545:{\displaystyle Q=NX_{S}}
2264:redundant representation
2240:, James E. Robertson of
2158:
2110:
1588:
1379:
931:-- Left-shift R by 1 bit
820:
331:
224:
36:Polynomial long division
9104:Greatest common divisor
8564:Pearson Education, Inc.
8324:Fast Recursive Division
5670:{\displaystyle Q=N_{k}}
4252:{\displaystyle F'(D)=0}
2294:Newton–Raphson division
2250:Imperial College London
844:DivisionByZeroException
215:algorithm presented in
213:greatest common divisor
9275:Division (mathematics)
9215:Modular exponentiation
8362:Barrett, Paul (1987).
7981:10.1093/qjmam/11.3.364
7530:
7437:
7410:
7384:
7354:
7325:
7305:
7276:
7249:
7205:
7162:
7139:
7066:
6916:
6855:
6735:fixed-point arithmetic
6730:a simple right shift.
6568:Division by a constant
6501:
6474:
6439:
6399:
6306:
6266:
6197:
5863:
5810:
5778:
5721:
5671:
5631:
5506:
5394:
5251:
5213:
5107:
5059:
5026:
4971:
4842:
4722:
4698:
4601:
4545:
4502:
4458:
4417:
4313:
4253:
4213:
4184:
4107:
4013:
3950:
3915:
3826:
3796:
3758:
3488:
3436:
3386:
3344:
3313:
3286:
3244:
3213:
3142:
3051:
3021:
2752:
2697:
2677:
2633:
2599:
2570:
2546:
2507:
2445:
2425:
2397:
2376:Calculate an estimate
2362:
2340:
2320:
2242:University of Illinois
2102:
2082:
2062:
2040:
2020:
1982:
1953:
1923:
1890:
1857:
1581:Non-restoring division
1271:
149:
8942:Shanks's square forms
8866:Integer factorization
8841:Sieve of Eratosthenes
8653:College of Charleston
8422:10.1145/773473.178249
7554:Further information:
7531:
7438:
7411:
7385:
7355:
7326:
7306:
7277:
7250:
7206:
7163:
7140:
7067:
6917:
6856:
6631:) that reduces to (1/
6511:Large-integer methods
6502:
6500:{\displaystyle 2^{n}}
6475:
6440:
6400:
6307:
6267:
6198:
5864:
5811:
5809:{\displaystyle D=1-x}
5779:
5729:has been scaled by a
5722:
5672:
5632:
5507:
5395:
5252:
5214:
5108:
5060:
5027:
4972:
4843:
4723:
4699:
4602:
4546:
4503:
4459:
4418:
4314:
4259:, which has solution
4254:
4214:
4185:
4108:
4014:
3951:
3916:
3827:
3825:{\displaystyle X_{0}}
3797:
3795:{\displaystyle X_{0}}
3769:quadratic convergence
3759:
3489:
3437:
3387:
3345:
3343:{\displaystyle X_{i}}
3314:
3312:{\displaystyle X_{i}}
3287:
3245:
3243:{\displaystyle X_{i}}
3214:
3143:
3052:
3050:{\displaystyle X_{i}}
3022:
2753:
2698:
2678:
2634:
2632:{\displaystyle X=1/D}
2600:
2571:
2547:
2508:
2446:
2426:
2398:
2396:{\displaystyle X_{0}}
2363:
2341:
2321:
2289:Fast division methods
2103:
2083:
2063:
2041:
2021:
1983:
1954:
1924:
1891:
1858:
1272:
1178:Slow division methods
814:and the remainder in
150:
9220:Montgomery reduction
9094:Function field sieve
9069:Baby-step giant-step
8915:Quadratic sieve (QS)
8152:. pp. 106–115.
7923:(3). IEEE: 218–222.
7541:loss of significance
7449:
7420:
7393:
7367:
7335:
7315:
7286:
7266:
7217:
7174:
7152:
7129:
6929:
6865:
6812:
6726:to make division by
6561:Montgomery reduction
6484:
6449:
6412:
6408:which is maximum at
6326:
6276:
6215:
5876:
5820:
5788:
5737:
5703:
5648:
5522:
5461:
5296:
5272:Goldschmidt division
5229:
5142:
5070:
5037:
4998:
4986:Chebyshev polynomial
4892:
4778:
4756:with a precision of
4711:
4628:
4558:
4512:
4468:
4427:
4323:
4263:
4223:
4212:{\displaystyle F(D)}
4194:
4121:
4026:
3963:
3928:
3855:
3809:
3779:
3501:
3449:
3404:
3354:
3327:
3296:
3254:
3227:
3152:
3068:
3034:
2765:
2707:
2687:
2643:
2609:
2598:{\displaystyle f(X)}
2580:
2560:
2520:
2458:
2435:
2407:
2380:
2352:
2330:
2310:
2298:Newton–Raphson uses
2092:
2072:
2052:
2030:
2010:
2006:If the −1 digits of
1965:
1937:
1906:
1873:
1799:
1370:The quotient digits
1189:
113:
18:Goldschmidt division
9270:Computer arithmetic
9230:Trachtenberg system
9196:Integer square root
9137:Modular square root
8856:Wheel factorization
8808:Quadratic Frobenius
8788:Lucas–Lehmer–Riesel
8470:10.1109/TC.2010.143
8124:10.1147/rd.111.0125
7747:Stanford University
7698:1950RScI...21..687S
6529:Karatsuba algorithm
5720:{\displaystyle N/D}
5260:is the quotient to
4721:{\displaystyle P\,}
3675:
3059:fused multiply–adds
2921:
2605:that has a zero at
2424:{\displaystyle 1/D}
2403:for the reciprocal
1952:{\displaystyle P-M}
1056:: Set R=0 and Q=0
9122:Extended Euclidean
9061:Discrete logarithm
8990:Schönhage–Strassen
8846:Sieve of Pritchard
8656:. 8 February 2021.
8594:2022-01-09 at the
8511:2022-01-08 at the
7526:
7433:
7406:
7380:
7350:
7321:
7311:and the remainder
7301:
7282:is represented as
7272:
7245:
7201:
7158:
7135:
7102:. You can help by
7062:
6912:
6851:
6497:
6470:
6468:
6435:
6395:
6312:can be rounded to
6302:
6272:, the denominator
6262:
6250:
6193:
5859:
5806:
5774:
5761:
5717:
5667:
5627:
5502:
5390:
5247:
5209:
5103:
5055:
5022:
4967:
4838:
4718:
4694:
4597:
4541:
4498:
4454:
4413:
4309:
4249:
4209:
4180:
4103:
4009:
3946:
3911:
3822:
3802:is poorly chosen.
3792:
3754:
3752:
3661:
3484:
3432:
3382:
3340:
3309:
3282:
3240:
3209:
3138:
3047:
3017:
2907:
2748:
2693:
2673:
2629:
2595:
2566:
2542:
2503:
2441:
2421:
2393:
2358:
2336:
2316:
2098:
2078:
2058:
2036:
2016:
1978:
1949:
1919:
1886:
1853:
1351:Restoring division
1267:
327:Euclidean division
180:is the input, and
145:
70:Euclidean division
43:division algorithm
9265:Binary arithmetic
9252:
9251:
8851:Sieve of Sundaram
8633:Drexel University
8572:978-0-321-84268-8
8525:ridiculous_fish.
8504:ridiculous_fish.
8221:10.1109/40.612224
8118:: 125–127. 1967.
7706:10.1063/1.1745692
7666:978-1-351-83197-0
7599:as it is inexact.
7501:
7464:
7347:
7324:{\displaystyle r}
7298:
7275:{\displaystyle q}
7161:{\displaystyle r}
7138:{\displaystyle q}
7120:
7119:
7056:
7024:
7023: where
7015:
6980:
6944:
6893:
6720:Barrett reduction
6557:Barrett reduction
6467:
6373:
6249:
6191:
6016:
5943:
5895:
5760:
5622:
5586:
5559:
5385:
5361:
5337:
5313:
5198:
4957:
4938:
4909:
4830:
4686:
4588:
4000:
3987:
3956:, one should use
3908:
2923:
2849:
2696:{\displaystyle D}
2569:{\displaystyle D}
2444:{\displaystyle D}
2361:{\displaystyle Q}
2339:{\displaystyle N}
2319:{\displaystyle D}
2101:{\displaystyle Q}
2081:{\displaystyle M}
2061:{\displaystyle Q}
2039:{\displaystyle P}
2019:{\displaystyle Q}
2004:
2003:
1850:
1835:
1820:
1034:If we take N=1100
49:which, given two
16:(Redirected from
9287:
9201:Integer relation
9174:Other algorithms
9079:Pollard kangaroo
8970:Ancient Egyptian
8828:Prime-generating
8813:Solovay–Strassen
8726:Number-theoretic
8719:
8712:
8705:
8696:
8691:
8689:
8688:
8658:
8657:
8644:
8638:
8637:
8628:"Rounding Error"
8623:
8617:
8616:
8604:
8598:
8583:
8577:
8576:
8555:Hacker's Delight
8549:
8543:
8542:
8540:
8538:
8522:
8516:
8502:
8496:
8495:
8493:
8492:
8486:
8455:
8446:
8440:
8439:
8437:
8436:
8430:
8415:
8397:
8388:
8382:
8381:
8359:
8353:
8352:
8346:
8338:
8337:
8336:
8318:
8312:
8311:
8309:
8308:
8302:
8295:
8284:
8278:
8277:
8275:
8251:
8242:
8231:
8225:
8224:
8200:
8194:
8193:
8191:
8190:
8184:
8147:
8138:
8132:
8131:
8130:on 18 July 2018.
8126:. Archived from
8104:
8098:
8097:
8095:
8094:
8088:
8073:
8062:
8056:
8055:
8053:
8052:
8046:
8039:
8028:
8022:
8021:
8019:
8017:
8002:
7996:
7995:
7993:
7992:
7960:
7954:
7953:
7951:
7950:
7940:
7908:
7902:
7901:
7895:
7887:
7886:
7884:
7866:
7860:
7859:
7857:
7856:
7830:
7821:(6): 1279–1301.
7806:
7800:
7799:
7797:
7795:
7789:
7782:
7771:
7765:
7764:
7762:
7761:
7755:
7744:
7735:
7729:
7728:
7726:
7725:
7677:
7671:
7670:
7650:
7644:
7643:
7641:
7630:
7613:
7606:
7600:
7593:
7577:Pentium FDIV bug
7535:
7533:
7532:
7529:{\displaystyle }
7527:
7522:
7521:
7503:
7502:
7494:
7485:
7484:
7466:
7465:
7457:
7442:
7440:
7439:
7434:
7432:
7431:
7415:
7413:
7412:
7407:
7405:
7404:
7389:
7387:
7386:
7381:
7379:
7378:
7359:
7357:
7356:
7351:
7349:
7348:
7340:
7330:
7328:
7327:
7322:
7310:
7308:
7307:
7302:
7300:
7299:
7291:
7281:
7279:
7278:
7273:
7254:
7252:
7251:
7246:
7244:
7236:
7210:
7208:
7207:
7204:{\displaystyle }
7202:
7167:
7165:
7164:
7159:
7144:
7142:
7141:
7136:
7115:
7112:
7094:
7087:
7071:
7069:
7068:
7063:
7061:
7057:
7055:
7054:
7045:
7037:
7025:
7022:
7020:
7016:
7014:
7013:
6992:
6985:
6981:
6976:
6965:
6958:
6949:
6945:
6937:
6921:
6919:
6918:
6913:
6911:
6910:
6898:
6894:
6889:
6888:
6879:
6860:
6858:
6857:
6852:
6847:
6839:
6838:
6807:
6803:
6799:
6795:
6791:
6772:
6770:
6769:
6766:
6763:
6752:
6750:
6749:
6746:
6743:
6674:However, unless
6506:
6504:
6503:
6498:
6496:
6495:
6479:
6477:
6476:
6471:
6469:
6460:
6444:
6442:
6441:
6436:
6434:
6433:
6432:
6431:
6404:
6402:
6401:
6396:
6394:
6393:
6392:
6391:
6374:
6372:
6364:
6363:
6352:
6343:
6338:
6337:
6315:
6311:
6309:
6308:
6303:
6301:
6300:
6299:
6298:
6271:
6269:
6268:
6263:
6261:
6257:
6256:
6252:
6251:
6242:
6210:
6202:
6200:
6199:
6194:
6192:
6190:
6183:
6182:
6181:
6180:
6157:
6148:
6144:
6143:
6142:
6141:
6094:
6093:
6048:
6039:
6034:
6017:
6015:
6014:
6013:
5997:
5993:
5992:
5949:
5944:
5942:
5941:
5940:
5924:
5901:
5896:
5894:
5880:
5868:
5866:
5865:
5860:
5858:
5857:
5856:
5855:
5832:
5831:
5815:
5813:
5812:
5807:
5783:
5781:
5780:
5775:
5773:
5769:
5762:
5753:
5728:
5726:
5724:
5723:
5718:
5713:
5695:binomial theorem
5689:Binomial theorem
5676:
5674:
5673:
5668:
5666:
5665:
5636:
5634:
5633:
5628:
5623:
5621:
5620:
5605:
5604:
5589:
5587:
5585:
5584:
5575:
5574:
5565:
5560:
5558:
5557:
5542:
5541:
5526:
5511:
5509:
5508:
5503:
5498:
5497:
5479:
5478:
5399:
5397:
5396:
5391:
5386:
5384:
5383:
5374:
5373:
5364:
5362:
5360:
5359:
5350:
5349:
5340:
5338:
5336:
5335:
5326:
5325:
5316:
5314:
5306:
5256:
5254:
5253:
5248:
5218:
5216:
5215:
5210:
5208:
5204:
5203:
5199:
5197:
5190:
5189:
5179:
5168:
5159:
5158:
5112:
5110:
5109:
5104:
5064:
5062:
5061:
5056:
5031:
5029:
5028:
5023:
4976:
4974:
4973:
4968:
4963:
4959:
4958:
4950:
4939:
4934:
4926:
4910:
4902:
4851:
4847:
4845:
4844:
4839:
4836:
4832:
4831:
4829:
4822:
4821:
4811:
4800:
4795:
4794:
4734:double precision
4730:single precision
4727:
4725:
4724:
4719:
4703:
4701:
4700:
4695:
4692:
4688:
4687:
4685:
4678:
4677:
4667:
4656:
4651:
4650:
4606:
4604:
4603:
4598:
4589:
4581:
4573:
4572:
4550:
4548:
4547:
4542:
4537:
4507:
4505:
4504:
4499:
4494:
4480:
4479:
4463:
4461:
4460:
4455:
4450:
4439:
4438:
4422:
4420:
4419:
4414:
4406:
4405:
4390:
4385:
4384:
4339:
4318:
4316:
4315:
4310:
4305:
4304:
4289:
4284:
4283:
4258:
4256:
4255:
4250:
4233:
4218:
4216:
4215:
4210:
4189:
4187:
4186:
4181:
4173:
4172:
4160:
4159:
4112:
4110:
4109:
4104:
4102:
4091:
4090:
4078:
4077:
4056:
4048:
4043:
4042:
4033:
4018:
4016:
4015:
4010:
4001:
3993:
3988:
3980:
3975:
3974:
3955:
3953:
3952:
3949:{\displaystyle }
3947:
3920:
3918:
3917:
3912:
3909:
3901:
3893:
3892:
3880:
3879:
3867:
3866:
3831:
3829:
3828:
3823:
3821:
3820:
3801:
3799:
3798:
3793:
3791:
3790:
3763:
3761:
3760:
3755:
3753:
3746:
3745:
3740:
3739:
3738:
3721:
3717:
3716:
3707:
3706:
3679:
3674:
3669:
3660:
3659:
3647:
3646:
3619:
3609:
3608:
3587:
3586:
3559:
3555:
3554:
3523:
3522:
3493:
3491:
3490:
3485:
3483:
3482:
3461:
3460:
3441:
3439:
3438:
3433:
3428:
3427:
3391:
3389:
3388:
3383:
3378:
3377:
3349:
3347:
3346:
3341:
3339:
3338:
3318:
3316:
3315:
3310:
3308:
3307:
3291:
3289:
3288:
3283:
3278:
3277:
3249:
3247:
3246:
3241:
3239:
3238:
3218:
3216:
3215:
3210:
3205:
3204:
3183:
3182:
3170:
3169:
3147:
3145:
3144:
3139:
3134:
3133:
3112:
3111:
3099:
3098:
3086:
3085:
3056:
3054:
3053:
3048:
3046:
3045:
3026:
3024:
3023:
3018:
3010:
3009:
2988:
2987:
2972:
2971:
2950:
2949:
2937:
2936:
2924:
2922:
2920:
2915:
2906:
2894:
2887:
2886:
2877:
2868:
2863:
2862:
2850:
2848:
2844:
2843:
2831:
2822:
2818:
2817:
2801:
2796:
2795:
2783:
2782:
2757:
2755:
2754:
2749:
2735:
2702:
2700:
2699:
2694:
2682:
2680:
2679:
2674:
2638:
2636:
2635:
2630:
2625:
2604:
2602:
2601:
2596:
2575:
2573:
2572:
2567:
2551:
2549:
2548:
2543:
2541:
2540:
2512:
2510:
2509:
2504:
2502:
2501:
2483:
2482:
2470:
2469:
2450:
2448:
2447:
2442:
2430:
2428:
2427:
2422:
2417:
2402:
2400:
2399:
2394:
2392:
2391:
2369:
2367:
2365:
2364:
2359:
2345:
2343:
2342:
2337:
2325:
2323:
2322:
2317:
2219:
2216:
2213:
2210:
2207:
2204:
2201:
2198:
2195:
2192:
2189:
2186:
2183:
2180:
2177:
2174:
2171:
2168:
2165:
2162:
2147:
2144:
2141:
2138:
2135:
2132:
2129:
2126:
2123:
2120:
2117:
2114:
2107:
2105:
2104:
2099:
2087:
2085:
2084:
2079:
2067:
2065:
2064:
2059:
2045:
2043:
2042:
2037:
2025:
2023:
2022:
2017:
1998:two's complement
1994:ones' complement
1987:
1985:
1984:
1979:
1958:
1956:
1955:
1950:
1928:
1926:
1925:
1920:
1895:
1893:
1892:
1887:
1862:
1860:
1859:
1854:
1852:
1851:
1843:
1837:
1836:
1828:
1822:
1821:
1813:
1785:
1778:
1775:
1772:
1769:
1766:
1763:
1760:
1757:
1754:
1751:
1748:
1745:
1742:
1739:
1736:
1733:
1730:
1727:
1724:
1721:
1718:
1715:
1712:
1709:
1706:
1703:
1700:
1697:
1694:
1691:
1688:
1685:
1682:
1679:
1676:
1673:
1670:
1667:
1664:
1661:
1658:
1655:
1652:
1649:
1646:
1643:
1640:
1637:
1634:
1631:
1628:
1625:
1622:
1619:
1616:
1613:
1610:
1607:
1604:
1601:
1598:
1595:
1592:
1569:
1566:
1563:
1560:
1557:
1554:
1551:
1548:
1545:
1542:
1539:
1536:
1533:
1530:
1527:
1524:
1521:
1518:
1515:
1512:
1509:
1506:
1503:
1500:
1497:
1494:
1491:
1488:
1485:
1482:
1479:
1476:
1473:
1470:
1467:
1464:
1461:
1458:
1455:
1452:
1449:
1446:
1443:
1440:
1437:
1434:
1431:
1428:
1425:
1422:
1419:
1416:
1413:
1410:
1407:
1404:
1401:
1398:
1395:
1392:
1389:
1386:
1383:
1276:
1274:
1273:
1268:
1257:
1256:
1226:
1225:
1207:
1206:
1025:
1022:
1019:
1016:
1013:
1010:
1007:
1004:
1001:
998:
995:
992:
989:
986:
983:
980:
977:
974:
971:
968:
965:
962:
959:
956:
953:
950:
947:
944:
941:
938:
935:
932:
929:
926:
923:
920:
917:
914:
911:
908:
905:
902:
899:
896:
893:
890:
887:
884:
881:
878:
875:
872:
869:
866:
863:
860:
857:
854:
851:
848:
845:
842:
839:
836:
833:
830:
827:
824:
749:
746:
743:
740:
737:
734:
731:
728:
725:
722:
719:
716:
713:
710:
707:
704:
701:
698:
695:
692:
689:
686:
683:
680:
677:
674:
671:
668:
665:
662:
659:
656:
653:
650:
647:
644:
641:
638:
635:
632:
629:
626:
623:
620:
617:
614:
611:
608:
605:
602:
599:
596:
593:
590:
587:
584:
581:
578:
575:
572:
569:
566:
563:
560:
557:
554:
551:
548:
545:
542:
539:
536:
533:
530:
527:
524:
521:
518:
515:
512:
509:
506:
503:
500:
497:
494:
491:
488:
485:
482:
479:
476:
473:
470:
467:
464:
461:
458:
455:
452:
449:
446:
443:
440:
437:
434:
431:
428:
425:
422:
419:
416:
413:
410:
407:
404:
401:
398:
395:
392:
389:
386:
383:
380:
377:
374:
371:
368:
365:
362:
359:
356:
353:
350:
347:
344:
341:
338:
335:
321:
318:
315:
312:
309:
306:
303:
300:
297:
294:
291:
288:
285:
282:
279:
276:
273:
270:
267:
264:
261:
258:
255:
252:
249:
246:
243:
240:
237:
234:
231:
228:
154:
152:
151:
146:
123:
68:, the result of
21:
9295:
9294:
9290:
9289:
9288:
9286:
9285:
9284:
9255:
9254:
9253:
9248:
9234:
9169:
9131:
9098:
9055:
8999:
8956:
8860:
8822:
8795:Proth's theorem
8737:Primality tests
8731:
8723:
8686:
8684:
8670:
8667:
8665:Further reading
8662:
8661:
8646:
8645:
8641:
8625:
8624:
8620:
8606:
8605:
8601:
8596:Wayback Machine
8584:
8580:
8573:
8551:
8550:
8546:
8536:
8534:
8524:
8523:
8519:
8513:Wayback Machine
8503:
8499:
8490:
8488:
8484:
8453:
8448:
8447:
8443:
8434:
8432:
8428:
8400:SIGPLAN Notices
8395:
8390:
8389:
8385:
8378:
8361:
8360:
8356:
8339:
8334:
8332:
8320:
8319:
8315:
8306:
8304:
8300:
8293:
8286:
8285:
8281:
8253:
8252:
8245:
8232:
8228:
8202:
8201:
8197:
8188:
8186:
8182:
8168:
8145:
8140:
8139:
8135:
8106:
8105:
8101:
8092:
8090:
8086:
8071:
8064:
8063:
8059:
8050:
8048:
8044:
8037:
8030:
8029:
8025:
8015:
8013:
8004:
8003:
7999:
7990:
7988:
7962:
7961:
7957:
7948:
7946:
7910:
7909:
7905:
7888:
7882:
7880:
7868:
7867:
7863:
7854:
7852:
7808:
7807:
7803:
7793:
7791:
7787:
7780:
7773:
7772:
7768:
7759:
7757:
7753:
7742:
7737:
7736:
7732:
7723:
7721:
7679:
7678:
7674:
7667:
7652:
7651:
7647:
7639:
7632:
7631:
7627:
7622:
7617:
7616:
7607:
7603:
7594:
7590:
7585:
7567:Galley division
7563:
7558:
7513:
7476:
7447:
7446:
7423:
7418:
7417:
7396:
7391:
7390:
7370:
7365:
7364:
7362:rounding errors
7333:
7332:
7313:
7312:
7284:
7283:
7264:
7263:
7262:, the quotient
7215:
7214:
7172:
7171:
7150:
7149:
7127:
7126:
7116:
7110:
7107:
7100:needs expansion
7085:
7046:
7038:
7032:
6993:
6966:
6960:
6959:
6953:
6932:
6927:
6926:
6902:
6880:
6874:
6863:
6862:
6830:
6810:
6809:
6805:
6801:
6797:
6793:
6789:
6767:
6764:
6761:
6760:
6758:
6747:
6744:
6741:
6740:
6738:
6570:
6549:described above
6545:Newton's method
6513:
6507:binary digits.
6487:
6482:
6481:
6447:
6446:
6423:
6415:
6410:
6409:
6383:
6378:
6365:
6356:
6345:
6344:
6329:
6324:
6323:
6313:
6290:
6285:
6274:
6273:
6233:
6229:
6222:
6218:
6213:
6212:
6208:
6172:
6167:
6150:
6149:
6121:
6116:
6085:
6041:
6040:
6027:
6005:
5998:
5984:
5950:
5932:
5925:
5902:
5884:
5874:
5873:
5847:
5842:
5823:
5818:
5817:
5786:
5785:
5750:
5746:
5735:
5734:
5701:
5700:
5698:
5691:
5657:
5646:
5645:
5606:
5590:
5576:
5566:
5543:
5527:
5520:
5519:
5489:
5464:
5459:
5458:
5448:
5422:
5412:
5375:
5365:
5351:
5341:
5327:
5317:
5294:
5293:
5284:
5274:
5227:
5226:
5181:
5180:
5169:
5163:
5150:
5149:
5145:
5140:
5139:
5131:on its leading
5068:
5067:
5035:
5034:
4996:
4995:
4927:
4924:
4920:
4890:
4889:
4871:
4863:
4813:
4812:
4801:
4786:
4785:
4781:
4776:
4775:
4771:
4760:binary places:
4759:
4755:
4751:
4746:
4738:double extended
4732:and 4 for both
4709:
4708:
4669:
4668:
4657:
4642:
4641:
4637:
4626:
4625:
4612:Remez algorithm
4564:
4556:
4555:
4510:
4509:
4471:
4466:
4465:
4430:
4425:
4424:
4397:
4376:
4321:
4320:
4296:
4275:
4261:
4260:
4226:
4221:
4220:
4192:
4191:
4164:
4151:
4119:
4118:
4082:
4069:
4034:
4024:
4023:
3966:
3961:
3960:
3926:
3925:
3884:
3871:
3858:
3853:
3852:
3812:
3807:
3806:
3782:
3777:
3776:
3751:
3750:
3730:
3728:
3719:
3718:
3708:
3698:
3677:
3676:
3651:
3638:
3617:
3616:
3600:
3578:
3557:
3556:
3540:
3524:
3508:
3499:
3498:
3474:
3452:
3447:
3446:
3419:
3402:
3401:
3369:
3352:
3351:
3330:
3325:
3324:
3299:
3294:
3293:
3269:
3252:
3251:
3230:
3225:
3224:
3196:
3174:
3155:
3150:
3149:
3125:
3103:
3090:
3071:
3066:
3065:
3037:
3032:
3031:
3001:
2979:
2963:
2941:
2928:
2895:
2878:
2869:
2854:
2835:
2824:
2823:
2809:
2802:
2787:
2768:
2763:
2762:
2705:
2704:
2685:
2684:
2641:
2640:
2607:
2606:
2578:
2577:
2558:
2557:
2532:
2518:
2517:
2493:
2474:
2461:
2456:
2455:
2433:
2432:
2431:of the divisor
2405:
2404:
2383:
2378:
2377:
2350:
2349:
2348:final quotient
2347:
2328:
2327:
2308:
2307:
2300:Newton's method
2296:
2291:
2230:
2221:
2220:
2217:
2214:
2211:
2208:
2205:
2202:
2199:
2196:
2193:
2190:
2187:
2184:
2181:
2178:
2175:
2172:
2169:
2166:
2163:
2160:
2149:
2148:
2145:
2142:
2139:
2136:
2133:
2130:
2127:
2124:
2121:
2118:
2115:
2112:
2090:
2089:
2070:
2069:
2050:
2049:
2028:
2027:
2008:
2007:
1963:
1962:
1935:
1934:
1904:
1903:
1871:
1870:
1797:
1796:
1780:
1779:
1776:
1773:
1770:
1767:
1764:
1761:
1758:
1755:
1752:
1749:
1746:
1743:
1740:
1737:
1734:
1731:
1728:
1725:
1722:
1719:
1716:
1713:
1710:
1707:
1704:
1701:
1698:
1695:
1692:
1689:
1686:
1683:
1680:
1677:
1674:
1671:
1668:
1665:
1662:
1659:
1656:
1653:
1650:
1647:
1644:
1641:
1638:
1635:
1632:
1629:
1626:
1623:
1620:
1617:
1614:
1611:
1608:
1605:
1602:
1599:
1596:
1593:
1590:
1583:
1571:
1570:
1567:
1564:
1561:
1558:
1555:
1552:
1549:
1546:
1543:
1540:
1538:-- Result-bit 0
1537:
1534:
1531:
1528:
1525:
1522:
1519:
1516:
1513:
1511:-- Result-bit 1
1510:
1507:
1504:
1501:
1498:
1495:
1492:
1489:
1486:
1483:
1480:
1477:
1474:
1471:
1468:
1465:
1462:
1459:
1456:
1453:
1450:
1447:
1444:
1441:
1438:
1435:
1432:
1429:
1426:
1423:
1420:
1417:
1414:
1411:
1408:
1405:
1402:
1399:
1396:
1393:
1390:
1387:
1384:
1381:
1353:
1321:
1291:
1230:
1217:
1192:
1187:
1186:
1180:
1173:
1169:
1165:
1155:
1150:
1145:
1140:
1135:
1124:
1123:: R=10 (R−D)
1119:
1114:
1109:
1104:
1093:
1088:
1083:
1072:
1067:
1062:
1057:
1049:
1045:
1041:
1037:
1032:
1027:
1026:
1023:
1020:
1017:
1014:
1011:
1008:
1005:
1002:
999:
996:
993:
990:
987:
984:
981:
978:
975:
972:
969:
966:
963:
960:
957:
954:
951:
948:
945:
942:
939:
936:
933:
930:
927:
924:
921:
918:
915:
912:
909:
906:
903:
900:
897:
894:
891:
888:
885:
882:
879:
876:
873:
870:
867:
864:
861:
858:
855:
852:
849:
846:
843:
840:
837:
834:
831:
828:
825:
822:
796:
790:
770:
764:
751:
750:
747:
744:
741:
738:
735:
732:
729:
726:
723:
720:
717:
714:
711:
708:
705:
702:
699:
696:
693:
690:
687:
684:
681:
678:
675:
672:
669:
666:
663:
660:
657:
654:
651:
648:
645:
642:
639:
636:
633:
631:divide_unsigned
630:
627:
624:
621:
618:
615:
612:
609:
607:divide_unsigned
606:
603:
600:
597:
594:
591:
588:
585:
582:
579:
576:
573:
570:
567:
564:
561:
558:
555:
552:
549:
546:
543:
540:
537:
534:
531:
528:
525:
522:
519:
516:
513:
510:
507:
504:
501:
498:
495:
492:
489:
486:
483:
480:
477:
474:
471:
468:
465:
462:
459:
456:
453:
450:
447:
444:
441:
438:
435:
432:
429:
426:
423:
420:
417:
414:
411:
408:
405:
402:
399:
396:
393:
390:
387:
384:
381:
378:
375:
372:
369:
366:
363:
360:
357:
354:
351:
348:
345:
342:
339:
336:
333:
323:
322:
319:
316:
313:
310:
307:
304:
301:
298:
295:
292:
289:
286:
283:
280:
277:
274:
271:
268:
265:
262:
259:
256:
253:
250:
247:
244:
241:
238:
235:
232:
229:
226:
209:
203:is the output.
111:
110:
39:
28:
23:
22:
15:
12:
11:
5:
9293:
9291:
9283:
9282:
9277:
9272:
9267:
9257:
9256:
9250:
9249:
9247:
9246:
9239:
9236:
9235:
9233:
9232:
9227:
9222:
9217:
9212:
9198:
9193:
9188:
9183:
9177:
9175:
9171:
9170:
9168:
9167:
9162:
9157:
9155:Tonelli–Shanks
9152:
9147:
9141:
9139:
9133:
9132:
9130:
9129:
9124:
9119:
9114:
9108:
9106:
9100:
9099:
9097:
9096:
9091:
9089:Index calculus
9086:
9084:Pohlig–Hellman
9081:
9076:
9071:
9065:
9063:
9057:
9056:
9054:
9053:
9048:
9043:
9038:
9036:Newton-Raphson
9033:
9028:
9023:
9018:
9012:
9010:
9001:
9000:
8998:
8997:
8992:
8987:
8982:
8977:
8972:
8966:
8964:
8962:Multiplication
8958:
8957:
8955:
8954:
8949:
8947:Trial division
8944:
8939:
8934:
8932:Rational sieve
8929:
8922:
8917:
8912:
8904:
8896:
8891:
8886:
8881:
8876:
8870:
8868:
8862:
8861:
8859:
8858:
8853:
8848:
8843:
8838:
8836:Sieve of Atkin
8832:
8830:
8824:
8823:
8821:
8820:
8815:
8810:
8805:
8798:
8791:
8784:
8777:
8772:
8767:
8762:
8760:Elliptic curve
8757:
8752:
8747:
8741:
8739:
8733:
8732:
8724:
8722:
8721:
8714:
8707:
8699:
8693:
8692:
8666:
8663:
8660:
8659:
8639:
8618:
8599:
8578:
8571:
8560:Addison Wesley
8558:(2 ed.).
8544:
8517:
8497:
8464:(2): 165–175.
8441:
8383:
8376:
8354:
8313:
8303:on 8 July 2017
8279:
8266:(1): 118–139.
8243:
8241:, January 1997
8226:
8195:
8166:
8133:
8099:
8057:
8023:
7997:
7975:(3): 364–384.
7955:
7903:
7861:
7828:10.1.1.72.6993
7801:
7766:
7730:
7672:
7665:
7645:
7624:
7623:
7621:
7618:
7615:
7614:
7601:
7587:
7586:
7584:
7581:
7580:
7579:
7574:
7569:
7562:
7559:
7556:Floating point
7551:are employed.
7525:
7520:
7516:
7512:
7509:
7506:
7500:
7497:
7491:
7488:
7483:
7479:
7475:
7472:
7469:
7463:
7460:
7454:
7430:
7426:
7403:
7399:
7377:
7373:
7360:, introducing
7346:
7343:
7320:
7297:
7294:
7271:
7243:
7239:
7235:
7231:
7228:
7225:
7222:
7200:
7197:
7194:
7191:
7188:
7185:
7182:
7179:
7157:
7134:
7118:
7117:
7111:September 2012
7097:
7095:
7084:
7083:Rounding error
7081:
7073:
7072:
7060:
7053:
7049:
7044:
7041:
7035:
7031:
7028:
7019:
7012:
7009:
7006:
7003:
7000:
6996:
6991:
6988:
6984:
6979:
6975:
6972:
6969:
6963:
6956:
6952:
6948:
6943:
6940:
6935:
6909:
6905:
6901:
6897:
6892:
6887:
6883:
6877:
6873:
6870:
6850:
6846:
6842:
6837:
6833:
6829:
6826:
6823:
6820:
6817:
6733:As a concrete
6623:); any value (
6602:floating-point
6569:
6566:
6519:reductions in
6512:
6509:
6494:
6490:
6466:
6463:
6457:
6454:
6430:
6426:
6422:
6418:
6406:
6405:
6390:
6386:
6381:
6377:
6371:
6368:
6362:
6359:
6355:
6351:
6348:
6341:
6336:
6332:
6318:relative error
6297:
6293:
6288:
6284:
6281:
6260:
6255:
6248:
6245:
6239:
6236:
6232:
6228:
6225:
6221:
6205:
6204:
6189:
6186:
6179:
6175:
6170:
6166:
6163:
6160:
6156:
6153:
6147:
6140:
6137:
6134:
6131:
6128:
6124:
6119:
6115:
6112:
6109:
6106:
6103:
6100:
6097:
6092:
6088:
6084:
6081:
6078:
6075:
6072:
6069:
6066:
6063:
6060:
6057:
6054:
6051:
6047:
6044:
6037:
6033:
6030:
6026:
6023:
6020:
6012:
6008:
6004:
6001:
5996:
5991:
5987:
5983:
5980:
5977:
5974:
5971:
5968:
5965:
5962:
5959:
5956:
5953:
5947:
5939:
5935:
5931:
5928:
5923:
5920:
5917:
5914:
5911:
5908:
5905:
5899:
5893:
5890:
5887:
5883:
5869:. This yields
5854:
5850:
5845:
5841:
5838:
5835:
5830:
5826:
5805:
5802:
5799:
5796:
5793:
5772:
5768:
5765:
5759:
5756:
5749:
5745:
5742:
5716:
5712:
5708:
5690:
5687:
5664:
5660:
5656:
5653:
5644:of iterations
5638:
5637:
5626:
5619:
5616:
5613:
5609:
5603:
5600:
5597:
5593:
5583:
5579:
5573:
5569:
5563:
5556:
5553:
5550:
5546:
5540:
5537:
5534:
5530:
5513:
5512:
5501:
5496:
5492:
5488:
5485:
5482:
5477:
5474:
5471:
5467:
5446:
5429:
5428:
5425:
5420:
5415:
5410:
5401:
5400:
5389:
5382:
5378:
5372:
5368:
5358:
5354:
5348:
5344:
5334:
5330:
5324:
5320:
5312:
5309:
5304:
5301:
5280:
5273:
5270:
5258:
5257:
5246:
5243:
5240:
5237:
5234:
5220:
5219:
5207:
5202:
5196:
5193:
5188:
5184:
5178:
5175:
5172:
5166:
5162:
5157:
5153:
5148:
5114:
5113:
5102:
5099:
5096:
5093:
5090:
5087:
5084:
5081:
5078:
5075:
5065:
5054:
5051:
5048:
5045:
5042:
5032:
5021:
5018:
5015:
5012:
5009:
5006:
5003:
4978:
4977:
4966:
4962:
4956:
4953:
4948:
4945:
4942:
4937:
4933:
4930:
4923:
4919:
4916:
4913:
4908:
4905:
4900:
4897:
4870:
4867:
4835:
4828:
4825:
4820:
4816:
4810:
4807:
4804:
4798:
4793:
4789:
4784:
4762:
4757:
4753:
4749:
4745:
4742:
4716:
4705:
4704:
4691:
4684:
4681:
4676:
4672:
4666:
4663:
4660:
4654:
4649:
4645:
4640:
4636:
4633:
4608:
4607:
4595:
4592:
4587:
4584:
4579:
4576:
4571:
4567:
4563:
4540:
4536:
4532:
4529:
4526:
4523:
4520:
4517:
4497:
4493:
4489:
4486:
4483:
4478:
4474:
4453:
4449:
4445:
4442:
4437:
4433:
4412:
4409:
4404:
4400:
4396:
4393:
4389:
4383:
4379:
4375:
4372:
4369:
4366:
4363:
4360:
4357:
4354:
4351:
4348:
4345:
4342:
4338:
4334:
4331:
4328:
4308:
4303:
4299:
4295:
4292:
4288:
4282:
4278:
4274:
4271:
4268:
4248:
4245:
4242:
4239:
4236:
4232:
4229:
4208:
4205:
4202:
4199:
4179:
4176:
4171:
4167:
4163:
4158:
4154:
4150:
4147:
4144:
4141:
4138:
4135:
4132:
4129:
4126:
4101:
4097:
4094:
4089:
4085:
4081:
4076:
4072:
4068:
4065:
4062:
4059:
4055:
4051:
4047:
4041:
4037:
4032:
4020:
4019:
4007:
4004:
3999:
3996:
3991:
3986:
3983:
3978:
3973:
3969:
3945:
3942:
3939:
3936:
3933:
3922:
3921:
3907:
3904:
3899:
3896:
3891:
3887:
3883:
3878:
3874:
3870:
3865:
3861:
3819:
3815:
3789:
3785:
3765:
3764:
3749:
3744:
3737:
3733:
3727:
3724:
3722:
3720:
3715:
3711:
3705:
3701:
3697:
3694:
3691:
3688:
3685:
3682:
3680:
3678:
3673:
3668:
3664:
3658:
3654:
3650:
3645:
3641:
3637:
3634:
3631:
3628:
3625:
3622:
3620:
3618:
3615:
3612:
3607:
3603:
3599:
3596:
3593:
3590:
3585:
3581:
3577:
3574:
3571:
3568:
3565:
3562:
3560:
3558:
3553:
3550:
3547:
3543:
3539:
3536:
3533:
3530:
3527:
3525:
3521:
3518:
3515:
3511:
3507:
3506:
3481:
3477:
3473:
3470:
3467:
3464:
3459:
3455:
3431:
3426:
3422:
3418:
3415:
3412:
3409:
3381:
3376:
3372:
3368:
3365:
3362:
3359:
3337:
3333:
3306:
3302:
3281:
3276:
3272:
3268:
3265:
3262:
3259:
3237:
3233:
3208:
3203:
3199:
3195:
3192:
3189:
3186:
3181:
3177:
3173:
3168:
3165:
3162:
3158:
3137:
3132:
3128:
3124:
3121:
3118:
3115:
3110:
3106:
3102:
3097:
3093:
3089:
3084:
3081:
3078:
3074:
3044:
3040:
3028:
3027:
3016:
3013:
3008:
3004:
3000:
2997:
2994:
2991:
2986:
2982:
2978:
2975:
2970:
2966:
2962:
2959:
2956:
2953:
2948:
2944:
2940:
2935:
2931:
2927:
2919:
2914:
2910:
2905:
2901:
2898:
2893:
2890:
2885:
2881:
2876:
2872:
2866:
2861:
2857:
2853:
2847:
2842:
2838:
2834:
2830:
2827:
2821:
2816:
2812:
2808:
2805:
2799:
2794:
2790:
2786:
2781:
2778:
2775:
2771:
2747:
2744:
2741:
2738:
2734:
2730:
2727:
2724:
2721:
2718:
2715:
2712:
2692:
2672:
2669:
2666:
2663:
2660:
2657:
2654:
2651:
2648:
2628:
2624:
2620:
2617:
2614:
2594:
2591:
2588:
2585:
2565:
2554:
2553:
2539:
2535:
2531:
2528:
2525:
2514:
2500:
2496:
2492:
2489:
2486:
2481:
2477:
2473:
2468:
2464:
2452:
2440:
2420:
2416:
2412:
2390:
2386:
2357:
2335:
2315:
2295:
2292:
2290:
2287:
2234:microprocessor
2229:
2226:
2159:
2111:
2097:
2077:
2068:and computing
2057:
2035:
2015:
2002:
2001:
1989:
1988:
1976:
1973:
1970:
1960:
1948:
1945:
1942:
1930:
1929:
1917:
1914:
1911:
1901:
1897:
1896:
1884:
1881:
1878:
1868:
1864:
1863:
1849:
1846:
1840:
1834:
1831:
1825:
1819:
1816:
1810:
1807:
1804:
1794:
1790:
1789:
1589:
1582:
1579:
1380:
1352:
1349:
1348:
1347:
1346:is the divisor
1341:
1335:
1312:
1307:
1297:
1287:
1278:
1277:
1266:
1263:
1260:
1255:
1252:
1249:
1246:
1243:
1240:
1237:
1233:
1229:
1224:
1220:
1216:
1213:
1210:
1205:
1202:
1199:
1195:
1179:
1176:
1171:
1167:
1154:: R=0 (R−D)
1047:
1043:
1039:
1035:
1031:
1028:
821:
802:, will divide
789:
786:
778:Short division
766:Main article:
763:
760:
376:DivisionByZero
332:
225:
208:
205:
201:
200:
191:
178:
177:
167:
144:
141:
138:
135:
132:
129:
126:
122:
118:
89:Newton–Raphson
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
9292:
9281:
9278:
9276:
9273:
9271:
9268:
9266:
9263:
9262:
9260:
9244:
9241:
9240:
9237:
9231:
9228:
9226:
9223:
9221:
9218:
9216:
9213:
9210:
9206:
9202:
9199:
9197:
9194:
9192:
9189:
9187:
9184:
9182:
9179:
9178:
9176:
9172:
9166:
9163:
9161:
9158:
9156:
9153:
9151:
9150:Pocklington's
9148:
9146:
9143:
9142:
9140:
9138:
9134:
9128:
9125:
9123:
9120:
9118:
9115:
9113:
9110:
9109:
9107:
9105:
9101:
9095:
9092:
9090:
9087:
9085:
9082:
9080:
9077:
9075:
9072:
9070:
9067:
9066:
9064:
9062:
9058:
9052:
9049:
9047:
9044:
9042:
9039:
9037:
9034:
9032:
9029:
9027:
9024:
9022:
9019:
9017:
9014:
9013:
9011:
9009:
9006:
9002:
8996:
8993:
8991:
8988:
8986:
8983:
8981:
8978:
8976:
8973:
8971:
8968:
8967:
8965:
8963:
8959:
8953:
8950:
8948:
8945:
8943:
8940:
8938:
8935:
8933:
8930:
8928:
8927:
8923:
8921:
8918:
8916:
8913:
8911:
8909:
8905:
8903:
8901:
8897:
8895:
8894:Pollard's rho
8892:
8890:
8887:
8885:
8882:
8880:
8877:
8875:
8872:
8871:
8869:
8867:
8863:
8857:
8854:
8852:
8849:
8847:
8844:
8842:
8839:
8837:
8834:
8833:
8831:
8829:
8825:
8819:
8816:
8814:
8811:
8809:
8806:
8804:
8803:
8799:
8797:
8796:
8792:
8790:
8789:
8785:
8783:
8782:
8778:
8776:
8773:
8771:
8768:
8766:
8763:
8761:
8758:
8756:
8753:
8751:
8748:
8746:
8743:
8742:
8740:
8738:
8734:
8730:
8727:
8720:
8715:
8713:
8708:
8706:
8701:
8700:
8697:
8682:
8678:
8674:
8669:
8668:
8664:
8655:
8654:
8649:
8643:
8640:
8635:
8634:
8629:
8622:
8619:
8614:
8610:
8603:
8600:
8597:
8593:
8590:
8589:
8582:
8579:
8574:
8568:
8565:
8561:
8557:
8556:
8548:
8545:
8532:
8528:
8521:
8518:
8514:
8510:
8507:
8501:
8498:
8483:
8479:
8475:
8471:
8467:
8463:
8459:
8452:
8445:
8442:
8427:
8423:
8419:
8414:
8413:10.1.1.1.2556
8409:
8405:
8401:
8394:
8387:
8384:
8379:
8377:0-387-18047-8
8373:
8369:
8365:
8358:
8355:
8350:
8344:
8330:
8326:
8325:
8317:
8314:
8299:
8292:
8291:
8283:
8280:
8274:
8269:
8265:
8261:
8257:
8250:
8248:
8244:
8240:
8236:
8230:
8227:
8222:
8218:
8214:
8210:
8206:
8199:
8196:
8181:
8177:
8173:
8169:
8167:0-7695-0116-8
8163:
8159:
8155:
8151:
8144:
8137:
8134:
8129:
8125:
8121:
8117:
8113:
8109:
8103:
8100:
8085:
8081:
8077:
8070:
8069:
8061:
8058:
8043:
8036:
8035:
8027:
8024:
8011:
8007:
8001:
7998:
7986:
7982:
7978:
7974:
7970:
7966:
7959:
7956:
7944:
7939:
7934:
7930:
7926:
7922:
7918:
7914:
7907:
7904:
7899:
7893:
7878:
7874:
7873:
7865:
7862:
7850:
7846:
7842:
7838:
7834:
7829:
7824:
7820:
7816:
7812:
7805:
7802:
7786:
7779:
7778:
7770:
7767:
7752:
7748:
7741:
7734:
7731:
7719:
7715:
7711:
7707:
7703:
7699:
7695:
7691:
7687:
7683:
7676:
7673:
7668:
7662:
7659:. CRC Press.
7658:
7657:
7649:
7646:
7638:
7637:
7629:
7626:
7619:
7611:
7605:
7602:
7598:
7592:
7589:
7582:
7578:
7575:
7573:
7570:
7568:
7565:
7564:
7560:
7557:
7552:
7550:
7546:
7542:
7536:
7518:
7514:
7510:
7507:
7504:
7495:
7481:
7477:
7473:
7470:
7467:
7458:
7444:
7428:
7424:
7401:
7397:
7375:
7371:
7363:
7341:
7318:
7292:
7269:
7261:
7256:
7237:
7229:
7226:
7223:
7220:
7211:
7195:
7192:
7189:
7186:
7183:
7180:
7169:
7155:
7148:
7132:
7125:
7114:
7105:
7101:
7098:This section
7096:
7093:
7089:
7088:
7082:
7080:
7078:
7058:
7051:
7047:
7042:
7039:
7033:
7029:
7026:
7017:
7010:
7007:
7004:
7001:
6998:
6994:
6989:
6986:
6982:
6977:
6973:
6970:
6967:
6961:
6954:
6950:
6946:
6941:
6938:
6933:
6925:
6924:
6923:
6907:
6903:
6899:
6895:
6890:
6885:
6881:
6875:
6871:
6868:
6844:
6840:
6835:
6831:
6824:
6821:
6818:
6815:
6786:
6784:
6780:
6776:
6756:
6736:
6731:
6729:
6725:
6721:
6717:
6713:
6709:
6705:
6701:
6697:
6693:
6689:
6685:
6681:
6677:
6672:
6670:
6666:
6662:
6658:
6654:
6650:
6646:
6642:
6638:
6634:
6630:
6626:
6622:
6617:
6615:
6611:
6607:
6603:
6599:
6595:
6591:
6587:
6583:
6579:
6575:
6567:
6565:
6562:
6558:
6554:
6550:
6546:
6542:
6538:
6534:
6530:
6526:
6522:
6518:
6510:
6508:
6492:
6488:
6464:
6461:
6455:
6452:
6428:
6424:
6420:
6416:
6388:
6384:
6379:
6375:
6369:
6366:
6360:
6357:
6353:
6349:
6346:
6339:
6334:
6330:
6322:
6321:
6320:
6319:
6295:
6291:
6286:
6282:
6279:
6258:
6253:
6246:
6243:
6237:
6234:
6230:
6226:
6223:
6219:
6187:
6184:
6177:
6173:
6168:
6164:
6161:
6158:
6154:
6151:
6135:
6132:
6129:
6122:
6117:
6113:
6110:
6104:
6101:
6098:
6090:
6086:
6082:
6079:
6073:
6067:
6064:
6061:
6055:
6052:
6049:
6045:
6042:
6035:
6031:
6028:
6024:
6021:
6018:
6010:
6006:
6002:
5999:
5989:
5985:
5981:
5978:
5972:
5966:
5963:
5960:
5954:
5951:
5945:
5937:
5933:
5929:
5926:
5918:
5915:
5912:
5906:
5903:
5897:
5891:
5888:
5885:
5881:
5872:
5871:
5870:
5852:
5848:
5843:
5839:
5836:
5833:
5828:
5824:
5803:
5800:
5797:
5794:
5791:
5770:
5766:
5763:
5757:
5754:
5747:
5743:
5740:
5732:
5714:
5710:
5706:
5696:
5688:
5686:
5683:
5678:
5662:
5658:
5654:
5651:
5643:
5624:
5617:
5614:
5611:
5607:
5601:
5598:
5595:
5591:
5581:
5577:
5571:
5567:
5561:
5554:
5551:
5548:
5544:
5538:
5535:
5532:
5528:
5518:
5517:
5516:
5499:
5494:
5490:
5486:
5483:
5480:
5475:
5472:
5469:
5465:
5457:
5456:
5455:
5453:
5449:
5442:
5438:
5434:
5426:
5423:
5416:
5413:
5406:
5405:
5404:
5387:
5380:
5376:
5370:
5366:
5356:
5352:
5346:
5342:
5332:
5328:
5322:
5318:
5310:
5307:
5302:
5299:
5292:
5291:
5290:
5288:
5283:
5279:
5271:
5269:
5265:
5263:
5244:
5241:
5238:
5235:
5232:
5225:
5224:
5223:
5205:
5200:
5194:
5191:
5186:
5182:
5176:
5173:
5170:
5164:
5160:
5155:
5151:
5146:
5138:
5137:
5136:
5134:
5130:
5125:
5124:term is new.
5123:
5119:
5100:
5097:
5094:
5091:
5088:
5085:
5082:
5079:
5076:
5073:
5066:
5052:
5049:
5046:
5043:
5040:
5033:
5019:
5016:
5013:
5010:
5007:
5004:
5001:
4994:
4993:
4992:
4989:
4987:
4983:
4964:
4960:
4954:
4951:
4946:
4943:
4940:
4935:
4931:
4928:
4921:
4917:
4914:
4911:
4906:
4903:
4898:
4895:
4888:
4887:
4886:
4884:
4880:
4876:
4868:
4866:
4861:
4858:
4854:
4850:
4833:
4826:
4823:
4818:
4814:
4808:
4805:
4802:
4796:
4791:
4787:
4782:
4774:
4770:
4766:
4761:
4743:
4741:
4739:
4735:
4731:
4714:
4689:
4682:
4679:
4674:
4670:
4664:
4661:
4658:
4652:
4647:
4643:
4638:
4634:
4631:
4624:
4623:
4622:
4620:
4615:
4613:
4593:
4590:
4585:
4582:
4577:
4569:
4565:
4554:
4553:
4552:
4538:
4534:
4530:
4527:
4521:
4515:
4495:
4491:
4487:
4484:
4481:
4476:
4472:
4451:
4447:
4443:
4440:
4435:
4431:
4402:
4398:
4394:
4387:
4381:
4377:
4373:
4367:
4364:
4361:
4355:
4349:
4346:
4340:
4336:
4332:
4326:
4301:
4297:
4293:
4286:
4280:
4276:
4272:
4269:
4266:
4246:
4243:
4237:
4230:
4227:
4203:
4197:
4174:
4169:
4165:
4161:
4156:
4152:
4145:
4142:
4139:
4136:
4130:
4124:
4116:
4092:
4087:
4083:
4079:
4074:
4070:
4063:
4060:
4057:
4049:
4039:
4035:
4005:
4002:
3997:
3994:
3989:
3984:
3981:
3976:
3971:
3967:
3959:
3958:
3957:
3940:
3937:
3934:
3905:
3902:
3897:
3894:
3889:
3885:
3881:
3876:
3872:
3868:
3863:
3859:
3851:
3850:
3849:
3847:
3846:approximation
3843:
3839:
3835:
3817:
3813:
3803:
3787:
3783:
3774:
3770:
3747:
3742:
3735:
3731:
3725:
3723:
3713:
3703:
3699:
3695:
3692:
3689:
3683:
3681:
3671:
3666:
3662:
3656:
3652:
3648:
3643:
3639:
3635:
3632:
3629:
3626:
3623:
3621:
3605:
3601:
3597:
3594:
3591:
3583:
3579:
3572:
3569:
3566:
3563:
3561:
3551:
3548:
3545:
3541:
3537:
3534:
3531:
3528:
3526:
3519:
3516:
3513:
3509:
3497:
3496:
3495:
3479:
3475:
3471:
3468:
3465:
3462:
3457:
3453:
3443:
3424:
3420:
3416:
3413:
3410:
3399:
3395:
3374:
3370:
3366:
3363:
3360:
3335:
3331:
3322:
3304:
3300:
3274:
3270:
3266:
3263:
3260:
3235:
3231:
3222:
3201:
3197:
3193:
3190:
3187:
3179:
3175:
3171:
3166:
3163:
3160:
3156:
3130:
3126:
3122:
3119:
3116:
3108:
3104:
3100:
3095:
3091:
3087:
3082:
3079:
3076:
3072:
3062:
3060:
3042:
3038:
3014:
3006:
3002:
2998:
2995:
2992:
2984:
2980:
2976:
2968:
2964:
2960:
2957:
2954:
2946:
2942:
2938:
2933:
2929:
2925:
2917:
2912:
2908:
2903:
2899:
2896:
2891:
2888:
2883:
2879:
2874:
2870:
2864:
2859:
2855:
2851:
2840:
2836:
2828:
2825:
2814:
2810:
2803:
2797:
2792:
2788:
2784:
2779:
2776:
2773:
2769:
2761:
2760:
2759:
2745:
2742:
2736:
2732:
2728:
2722:
2716:
2710:
2690:
2670:
2667:
2664:
2661:
2658:
2652:
2646:
2626:
2622:
2618:
2615:
2612:
2589:
2583:
2563:
2537:
2533:
2529:
2526:
2523:
2515:
2498:
2494:
2490:
2487:
2484:
2479:
2475:
2471:
2466:
2462:
2453:
2438:
2418:
2414:
2410:
2388:
2384:
2375:
2374:
2373:
2370:
2355:
2333:
2313:
2305:
2301:
2293:
2288:
2286:
2284:
2280:
2279:Intel Pentium
2275:
2272:
2269:
2265:
2260:
2258:
2253:
2251:
2247:
2243:
2239:
2235:
2227:
2225:
2157:
2155:
2109:
2095:
2075:
2055:
2048:
2033:
2013:
1999:
1995:
1990:
1974:
1971:
1968:
1961:
1946:
1943:
1940:
1933:3. Subtract:
1932:
1931:
1915:
1912:
1909:
1902:
1899:
1898:
1882:
1879:
1876:
1869:
1866:
1865:
1844:
1838:
1829:
1823:
1814:
1808:
1805:
1802:
1795:
1792:
1791:
1786:
1783:
1587:
1580:
1578:
1576:
1378:
1375:
1373:
1368:
1366:
1362:
1358:
1350:
1345:
1342:
1339:
1336:
1333:
1329:
1325:
1319:
1315:
1311:
1308:
1305:
1301:
1298:
1295:
1290:
1286:
1283:
1282:
1281:
1264:
1261:
1258:
1250:
1247:
1244:
1238:
1235:
1231:
1227:
1222:
1218:
1214:
1211:
1208:
1203:
1200:
1197:
1193:
1185:
1184:
1183:
1177:
1175:
1164:
1160:
1158:
1153:
1148:
1143:
1138:
1133:
1129:
1127:
1122:
1117:
1112:
1107:
1102:
1098:
1096:
1091:
1086:
1081:
1077:
1075:
1070:
1065:
1060:
1055:
1051:
1029:
819:
817:
813:
809:
805:
801:
800:long division
795:
787:
785:
783:
779:
774:
769:
762:Long division
761:
759:
757:
330:
328:
223:
221:
220:
214:
206:
204:
199:
195:
192:
190:
186:
183:
182:
181:
175:
171:
168:
165:
161:
158:
157:
156:
139:
136:
133:
127:
124:
120:
116:
107:
105:
104:computer time
101:
96:
94:
90:
86:
82:
81:non-restoring
78:
73:
71:
67:
63:
59:
55:
52:
48:
44:
37:
33:
32:Long division
19:
9242:
9007:
8924:
8907:
8899:
8818:Miller–Rabin
8800:
8793:
8786:
8781:Lucas–Lehmer
8779:
8685:. Retrieved
8676:
8651:
8642:
8631:
8621:
8612:
8608:
8602:
8587:
8581:
8554:
8547:
8535:. Retrieved
8520:
8500:
8489:. Retrieved
8461:
8457:
8444:
8433:. Retrieved
8406:(6): 61–72.
8403:
8399:
8386:
8367:
8357:
8333:, retrieved
8323:
8316:
8305:. Retrieved
8298:the original
8289:
8282:
8263:
8259:
8234:
8229:
8215:(4): 56–66.
8212:
8208:
8198:
8187:. Retrieved
8149:
8136:
8128:the original
8115:
8111:
8102:
8091:. Retrieved
8067:
8060:
8049:. Retrieved
8033:
8026:
8014:. Retrieved
8000:
7989:. Retrieved
7972:
7968:
7958:
7947:. Retrieved
7920:
7916:
7906:
7881:, retrieved
7871:
7864:
7853:. Retrieved
7818:
7814:
7804:
7792:. Retrieved
7776:
7769:
7758:. Retrieved
7746:
7733:
7722:. Retrieved
7689:
7685:
7675:
7655:
7648:
7635:
7628:
7604:
7591:
7545:guard digits
7537:
7445:
7257:
7212:
7170:
7121:
7108:
7104:adding to it
7099:
7074:
6788:For general
6787:
6732:
6727:
6723:
6715:
6711:
6707:
6703:
6699:
6695:
6691:
6687:
6683:
6679:
6675:
6673:
6668:
6664:
6660:
6656:
6652:
6648:
6644:
6640:
6636:
6632:
6628:
6624:
6620:
6618:
6613:
6605:
6597:
6593:
6589:
6585:
6581:
6573:
6571:
6527:such as the
6521:cryptography
6514:
6407:
6206:
5784:. We choose
5731:power of two
5692:
5679:
5641:
5639:
5514:
5451:
5450:is based on
5444:
5440:
5436:
5432:
5430:
5418:
5408:
5402:
5286:
5281:
5277:
5275:
5266:
5261:
5259:
5221:
5132:
5128:
5126:
5121:
5117:
5115:
4990:
4981:
4979:
4882:
4878:
4874:
4872:
4864:
4859:
4856:
4852:
4848:
4772:
4768:
4764:
4747:
4706:
4616:
4609:
4219:occurs when
4021:
3923:
3848:in the form
3841:
3837:
3833:
3804:
3772:
3766:
3444:
3397:
3393:
3320:
3220:
3063:
3029:
2555:
2371:
2346:to find the
2302:to find the
2297:
2281:processor's
2276:
2273:
2267:
2263:
2261:
2257:lookup table
2254:
2246:K. D. Tocher
2231:
2228:SRT division
2222:
2153:
2150:
2046:
2005:
1781:
1584:
1574:
1572:
1376:
1371:
1369:
1364:
1360:
1354:
1343:
1337:
1331:
1327:
1323:
1317:
1313:
1309:
1299:
1293:
1288:
1284:
1279:
1181:
1162:
1161:
1156:
1151:
1146:
1141:
1136:
1134:: Set i=0
1131:
1130:
1125:
1120:
1115:
1110:
1105:
1103:: Set i=1
1100:
1099:
1094:
1089:
1084:
1082:: Set i=2
1079:
1078:
1073:
1068:
1063:
1058:
1053:
1052:
1033:
815:
811:
807:
803:
797:
775:
771:
752:
324:
218:
210:
202:
193:
184:
179:
169:
159:
108:
97:
74:
57:
53:
42:
40:
9074:Pollard rho
9031:Goldschmidt
8765:Pocklington
8755:Baillie–PSW
8615:(3): 81–85.
7794:23 December
6755:hexadecimal
6616:| > 1).
4619:convergence
4117:applied to
3442:are zeros.
1357:fixed-point
1174:) and R=0.
1113:: R=0110
1108:: R=0110
1042:) and D=100
174:denominator
93:Goldschmidt
9259:Categories
9186:Cornacchia
9181:Chakravala
8729:algorithms
8687:2018-07-16
8491:2015-12-08
8435:2015-12-08
8335:2021-09-10
8307:2017-07-08
8209:IEEE Micro
8189:2015-09-15
8093:2015-09-15
8051:2016-12-23
8016:22 October
7991:2022-08-24
7949:2022-08-24
7855:2022-08-24
7845:2429/12179
7760:2019-06-24
7724:2022-02-28
7692:(8): 690.
7620:References
6742:2863311531
6578:reciprocal
5733:such that
4744:Pseudocode
2304:reciprocal
1144:: R=100
1139:: R=100
1092:: R=011
1087:: R=010
792:See also:
166:(dividend)
9160:Berlekamp
9117:Euclidean
9005:Euclidean
8985:Toom–Cook
8980:Karatsuba
8677:quadibloc
8408:CiteSeerX
8108:"Authors"
7883:24 August
7823:CiteSeerX
7714:0034-6748
7610:compilers
7597:compilers
7515:ϵ
7499:~
7478:ϵ
7462:~
7425:ϵ
7398:ϵ
7372:ϵ
7345:~
7296:~
7224:≤
7147:remainder
7008:−
7002:−
6971:−
6900:−
6849:⌉
6841:
6828:⌈
6421:−
6354:−
6331:ε
6283:−
6227:∈
6185:≈
6165:−
6133:−
6105:⋅
6102:⋅
6099:⋅
6074:⋅
6056:⋅
6022:⋯
6003:−
5973:⋅
5955:⋅
5930:−
5907:⋅
5889:−
5801:−
5744:∈
5697:. Assume
5487:−
5431:Assuming
5381:…
5371:…
5242:⋅
5192:
5161:
5095:⋅
5050:⋅
5017:⋅
5011:−
4947:⋅
4929:−
4918:⋅
4824:
4797:
4740:formats.
4680:
4653:
4591:≈
4578:≤
4566:ε
4485:−
4374:−
4365:−
4273:−
4143:−
4061:−
4036:ε
3990:−
3898:≈
3732:ε
3693:−
3630:−
3595:−
3570:−
3535:−
3510:ε
3469:−
3454:ε
3414:−
3364:−
3264:−
3191:−
3120:−
2996:−
2958:−
2897:−
2889:−
2865:−
2798:−
2743:−
2668:−
2488:…
1944:−
1848:¯
1833:¯
1818:¯
1259:×
1239:−
1228:−
1215:×
217:Euclid's
198:remainder
176:(divisor)
164:numerator
77:restoring
66:remainder
47:algorithm
9127:Lehmer's
9021:Chunking
9008:division
8937:Fermat's
8681:Archived
8592:Archived
8531:Archived
8509:Archived
8482:Archived
8478:13347152
8426:Archived
8343:citation
8329:archived
8180:Archived
8176:12793819
8084:Archived
8080:34136725
8042:Archived
8010:Archived
7985:Archived
7943:Archived
7892:citation
7877:archived
7849:Archived
7785:Archived
7751:Archived
7718:Archived
7561:See also
7124:quotient
7059:⌋
7034:⌊
7018:⌋
6983:⌋
6962:⌊
6955:⌊
6947:⌋
6934:⌊
6896:⌉
6876:⌈
6804:-bit by
6370:′
6361:′
6350:′
6155:′
6046:′
6032:′
5206:⌉
5147:⌈
4881:so that
4834:⌉
4783:⌈
4690:⌉
4639:⌈
4231:′
3494:, then:
2829:′
1996:without
1975:11010101
1916:00010101
1883:11101010
1615:<<
1406:<<
925:<<
782:Chunking
628:function
334:function
219:Elements
189:quotient
155:, where
62:quotient
51:integers
9243:Italics
9165:Kunerth
9145:Cipolla
9026:Fourier
8995:Fürer's
8889:Euler's
8879:Dixon's
8802:Pépin's
8515:. 2011.
7738:Flynn.
7694:Bibcode
7608:Modern
6783:A346496
6779:A346495
6771:
6759:
6751:
6739:
6610:integer
6535:or the
6517:modular
6316:with a
5727:
5699:
5120:⋅
4862:N' × X
1302:is the
1292:is the
1280:where:
1157:Step 5c
1152:Step 5b
1126:Step 5c
1121:Step 5b
1030:Example
64:and/or
9225:Schoof
9112:Binary
9016:Binary
8952:Shor's
8770:Fermat
8569:
8537:6 July
8476:
8410:
8374:
8174:
8164:
8078:
7825:
7712:
7663:
7213:where
6211:steps
6207:After
5264:bits.
4860:return
4773:repeat
4594:0.059.
2244:, and
1793:Start:
1147:Step 5
1142:Step 4
1137:Step 3
1132:Step 2
1116:Step 5
1111:Step 4
1106:Step 3
1101:Step 2
1095:Step 5
1090:Step 4
1085:Step 3
1080:Step 2
1074:Step 5
1069:Step 4
1064:Step 3
1059:Step 2
1054:Step 1
730:return
604:return
562:return
538:return
502:divide
442:return
421:divide
337:divide
305:return
83:, and
45:is an
9046:Short
8775:Lucas
8485:(PDF)
8474:S2CID
8454:(PDF)
8429:(PDF)
8396:(PDF)
8301:(PDF)
8294:(PDF)
8183:(PDF)
8172:S2CID
8146:(PDF)
8087:(PDF)
8072:(PDF)
8045:(PDF)
8038:(PDF)
7788:(PDF)
7781:(PDF)
7754:(PDF)
7743:(PDF)
7640:(PDF)
7583:Notes
6600:. In
6445:when
4849:times
2154:after
1660:>=
1481:>=
1363:<
1304:radix
838:error
676:while
370:error
251:while
9041:Long
8975:Long
8567:ISBN
8539:2021
8372:ISBN
8349:link
8162:ISBN
8076:OCLC
8018:2013
7921:EC-7
7898:link
7885:2022
7796:2016
7710:ISSN
7661:ISBN
7416:and
7230:<
7145:and
6861:and
6775:OEIS
6682:and
6647:as (
6592:·(1/
6559:and
5816:and
5116:The
4877:and
4752:and
4736:and
4464:and
3350:and
3250:and
3148:and
2277:The
2268:five
2173:then
2167:<
2134:bnot
1717:else
1666:then
1514:else
1487:then
1367:.
1320:+ 1)
1166:Q=11
979:then
835:then
559:else
535:then
478:then
472:<
397:then
391:<
367:then
91:and
56:and
9205:LLL
9051:SRT
8910:+ 1
8902:− 1
8750:APR
8745:AKS
8466:doi
8418:doi
8268:doi
8217:doi
8154:doi
8120:doi
7977:doi
7933:hdl
7925:doi
7841:hdl
7833:doi
7702:doi
7547:or
7331:as
7258:In
7106:.
6832:log
6598:N/D
6547:as
5682:AMD
5183:log
5152:log
4952:256
4904:140
4857:end
4815:log
4788:log
4671:log
4644:log
3935:0.5
2306:of
2248:of
2238:IBM
2215:end
2128:bit
1809:111
1774:end
1768:end
1624:for
1565:end
1562:end
1415:for
1316:− (
1163:end
1038:(12
1024:end
1021:end
880:for
850:end
806:by
748:end
727:end
625:end
598:end
595:end
463:end
382:end
302:end
85:SRT
9261::
9209:KZ
9207:;
8679:.
8675:.
8650:.
8630:.
8613:24
8611:.
8562:-
8529:.
8480:.
8472:.
8462:60
8460:.
8456:.
8424:.
8416:.
8404:29
8402:.
8398:.
8366:.
8345:}}
8341:{{
8264:70
8262:.
8258:.
8246:^
8237:,
8213:17
8211:.
8207:.
8178:.
8170:.
8160:.
8148:.
8116:11
8114:.
8110:.
8082:.
7983:.
7973:11
7971:.
7967:.
7941:.
7931:.
7919:.
7915:.
7894:}}
7890:{{
7847:.
7839:.
7831:.
7819:34
7817:.
7813:.
7749:.
7745:.
7716:.
7708:.
7700:.
7690:21
7688:.
7684:.
7443::
7255:.
6922::
6785:.
6694:)/
6663:·(
6655:)/
6555:,
6531:,
5677:.
5454::
5289::
5236::=
5195:99
5077::=
5044::=
5005::=
4955:99
4936:11
4932:64
4907:33
4899::=
4827:17
4683:17
4586:17
4539:17
4496:17
4488:32
4452:17
4444:48
3998:17
3995:32
3985:17
3982:48
3061:.
2218:if
2161:if
2108:.
2047:is
2000:)
1771:if
1654:if
1648:do
1642:..
1475:if
1442:do
1436:..
1334:−1
1326:−(
1172:10
1170:(3
1050:)
1048:10
1046:(4
1040:10
967:if
907:do
901:..
823:if
688:do
523:if
466:if
439:);
385:if
355:if
263:do
196:=
187:=
172:=
162:=
41:A
9211:)
9203:(
8908:p
8900:p
8718:e
8711:t
8704:v
8690:.
8636:.
8575:.
8541:.
8494:.
8468::
8438:.
8420::
8380:.
8351:)
8310:.
8276:.
8270::
8223:.
8219::
8192:.
8156::
8122::
8096:.
8054:.
8020:.
7994:.
7979::
7952:.
7935::
7927::
7900:)
7858:.
7843::
7835::
7798:.
7763:.
7727:.
7704::
7696::
7669:.
7524:]
7519:r
7511:+
7508:r
7505:=
7496:r
7490:[
7487:]
7482:q
7474:+
7471:q
7468:=
7459:q
7453:[
7429:r
7402:q
7376:q
7342:r
7319:r
7293:q
7270:q
7242:|
7238:b
7234:|
7227:r
7221:0
7199:]
7196:r
7193:+
7190:q
7187:b
7184:=
7181:a
7178:[
7156:r
7133:q
7113:)
7109:(
7052:x
7048:2
7043:a
7040:N
7030:=
7027:b
7011:1
7005:x
6999:k
6995:2
6990:b
6987:+
6978:2
6974:b
6968:N
6951:=
6942:D
6939:N
6908:x
6904:2
6891:D
6886:k
6882:2
6872:=
6869:a
6845:D
6836:2
6825:+
6822:x
6819:=
6816:k
6806:x
6802:x
6798:x
6794:D
6790:x
6768:3
6765:/
6762:2
6748:2
6745:/
6728:Y
6724:Y
6716:D
6712:Y
6710:/
6708:X
6704:D
6702:/
6700:N
6696:Y
6692:X
6690:·
6688:N
6684:Y
6680:X
6676:D
6669:Y
6667:/
6665:X
6661:N
6657:Y
6653:X
6651:·
6649:N
6645:D
6643:/
6641:N
6637:Y
6633:D
6629:Y
6627:/
6625:X
6621:D
6614:D
6606:D
6594:D
6590:N
6586:D
6582:D
6574:D
6493:n
6489:2
6465:2
6462:1
6456:=
6453:x
6429:n
6425:2
6417:2
6389:n
6385:2
6380:x
6376:=
6367:Q
6358:N
6347:Q
6340:=
6335:n
6314:1
6296:n
6292:2
6287:x
6280:1
6259:)
6254:)
6247:2
6244:1
6238:,
6235:0
6231:[
6224:x
6220:(
6209:n
6203:.
6188:1
6178:n
6174:2
6169:x
6162:1
6159:=
6152:D
6146:)
6139:)
6136:1
6130:n
6127:(
6123:2
6118:x
6114:+
6111:1
6108:(
6096:)
6091:2
6087:x
6083:+
6080:1
6077:(
6071:)
6068:x
6065:+
6062:1
6059:(
6053:N
6050:=
6043:N
6036:=
6029:Q
6025:=
6019:=
6011:4
6007:x
6000:1
5995:)
5990:2
5986:x
5982:+
5979:1
5976:(
5970:)
5967:x
5964:+
5961:1
5958:(
5952:N
5946:=
5938:2
5934:x
5927:1
5922:)
5919:x
5916:+
5913:1
5910:(
5904:N
5898:=
5892:x
5886:1
5882:N
5853:i
5849:2
5844:x
5840:+
5837:1
5834:=
5829:i
5825:F
5804:x
5798:1
5795:=
5792:D
5771:]
5767:1
5764:,
5758:2
5755:1
5748:(
5741:D
5715:D
5711:/
5707:N
5663:k
5659:N
5655:=
5652:Q
5642:k
5625:.
5618:1
5615:+
5612:i
5608:F
5602:1
5599:+
5596:i
5592:F
5582:i
5578:D
5572:i
5568:N
5562:=
5555:1
5552:+
5549:i
5545:D
5539:1
5536:+
5533:i
5529:N
5500:.
5495:i
5491:D
5484:2
5481:=
5476:1
5473:+
5470:i
5466:F
5452:D
5447:i
5445:F
5441:D
5437:D
5435:/
5433:N
5424:.
5421:i
5419:F
5414:.
5411:i
5409:F
5388:.
5377:F
5367:F
5357:2
5353:F
5347:2
5343:F
5333:1
5329:F
5323:1
5319:F
5311:D
5308:N
5303:=
5300:Q
5287:Q
5282:i
5278:F
5262:P
5245:X
5239:N
5233:Q
5201:)
5187:2
5177:1
5174:+
5171:P
5165:(
5156:3
5133:P
5129:D
5122:E
5118:Y
5101:.
5098:E
5092:Y
5089:+
5086:Y
5083:+
5080:X
5074:X
5053:E
5047:X
5041:Y
5020:X
5014:D
5008:1
5002:E
4982:D
4965:.
4961:)
4944:D
4941:+
4922:(
4915:D
4912:+
4896:X
4883:D
4879:D
4875:N
4819:2
4809:1
4806:+
4803:P
4792:2
4758:P
4754:D
4750:N
4715:P
4675:2
4665:1
4662:+
4659:P
4648:2
4635:=
4632:S
4583:1
4575:|
4570:0
4562:|
4535:/
4531:1
4528:=
4525:)
4522:1
4519:(
4516:F
4492:/
4482:=
4477:2
4473:T
4448:/
4441:=
4436:1
4432:T
4411:)
4408:)
4403:2
4399:T
4395:2
4392:(
4388:/
4382:1
4378:T
4371:(
4368:F
4362:=
4359:)
4356:1
4353:(
4350:F
4347:=
4344:)
4341:2
4337:/
4333:1
4330:(
4327:F
4307:)
4302:2
4298:T
4294:2
4291:(
4287:/
4281:1
4277:T
4270:=
4267:D
4247:0
4244:=
4241:)
4238:D
4235:(
4228:F
4207:)
4204:D
4201:(
4198:F
4178:)
4175:D
4170:2
4166:T
4162:+
4157:1
4153:T
4149:(
4146:D
4140:1
4137:=
4134:)
4131:D
4128:(
4125:F
4100:|
4096:)
4093:D
4088:2
4084:T
4080:+
4075:1
4071:T
4067:(
4064:D
4058:1
4054:|
4050:=
4046:|
4040:0
4031:|
4006:.
4003:D
3977:=
3972:0
3968:X
3944:]
3941:1
3938:,
3932:[
3906:D
3903:1
3895:D
3890:2
3886:T
3882:+
3877:1
3873:T
3869:=
3864:0
3860:X
3842:N
3838:D
3834:D
3818:0
3814:X
3788:0
3784:X
3748:.
3743:2
3736:i
3726:=
3714:2
3710:)
3704:i
3700:X
3696:D
3690:1
3687:(
3684:=
3672:2
3667:i
3663:X
3657:2
3653:D
3649:+
3644:i
3640:X
3636:D
3633:2
3627:1
3624:=
3614:)
3611:)
3606:i
3602:X
3598:D
3592:2
3589:(
3584:i
3580:X
3576:(
3573:D
3567:1
3564:=
3552:1
3549:+
3546:i
3542:X
3538:D
3532:1
3529:=
3520:1
3517:+
3514:i
3480:i
3476:X
3472:D
3466:1
3463:=
3458:i
3430:)
3425:i
3421:X
3417:D
3411:1
3408:(
3398:n
3394:n
3380:)
3375:i
3371:X
3367:D
3361:1
3358:(
3336:i
3332:X
3321:n
3319:(
3305:i
3301:X
3280:)
3275:i
3271:X
3267:D
3261:2
3258:(
3236:i
3232:X
3221:n
3207:)
3202:i
3198:X
3194:D
3188:2
3185:(
3180:i
3176:X
3172:=
3167:1
3164:+
3161:i
3157:X
3136:)
3131:i
3127:X
3123:D
3117:1
3114:(
3109:i
3105:X
3101:+
3096:i
3092:X
3088:=
3083:1
3080:+
3077:i
3073:X
3043:i
3039:X
3015:,
3012:)
3007:i
3003:X
2999:D
2993:2
2990:(
2985:i
2981:X
2977:=
2974:)
2969:i
2965:X
2961:D
2955:1
2952:(
2947:i
2943:X
2939:+
2934:i
2930:X
2926:=
2918:2
2913:i
2909:X
2904:/
2900:1
2892:D
2884:i
2880:X
2875:/
2871:1
2860:i
2856:X
2852:=
2846:)
2841:i
2837:X
2833:(
2826:f
2820:)
2815:i
2811:X
2807:(
2804:f
2793:i
2789:X
2785:=
2780:1
2777:+
2774:i
2770:X
2746:D
2740:)
2737:X
2733:/
2729:1
2726:(
2723:=
2720:)
2717:X
2714:(
2711:f
2691:D
2671:1
2665:X
2662:D
2659:=
2656:)
2653:X
2650:(
2647:f
2627:D
2623:/
2619:1
2616:=
2613:X
2593:)
2590:X
2587:(
2584:f
2564:D
2552:.
2538:S
2534:X
2530:N
2527:=
2524:Q
2499:S
2495:X
2491:,
2485:,
2480:2
2476:X
2472:,
2467:1
2463:X
2451:.
2439:D
2419:D
2415:/
2411:1
2389:0
2385:X
2368:.
2356:Q
2334:N
2314:D
2209:D
2206:+
2203:R
2200:=
2197::
2194:R
2191:1
2188:−
2185:Q
2182:=
2179::
2176:Q
2170:0
2164:R
2143:)
2140:Q
2137:(
2131:.
2125:−
2122:Q
2119:=
2116::
2113:Q
2096:Q
2076:M
2056:Q
2034:P
2014:Q
1972:=
1969:Q
1959::
1947:M
1941:P
1913:=
1910:M
1880:=
1877:P
1845:1
1839:1
1830:1
1824:1
1815:1
1806:=
1803:Q
1765:D
1762:+
1759:R
1756:*
1753:2
1750:=
1747::
1744:R
1741:1
1738:−
1735:=
1732::
1729:)
1726:i
1723:(
1720:q
1714:D
1711:−
1708:R
1705:*
1702:2
1699:=
1696::
1693:R
1690:1
1687:+
1684:=
1681::
1678:)
1675:i
1672:(
1669:q
1663:0
1657:R
1645:0
1639:1
1636:−
1633:n
1630:=
1627:i
1618:n
1612:D
1609:=
1606::
1603:D
1600:N
1597:=
1594::
1591:R
1575:D
1556:D
1553:+
1550:R
1547:=
1544::
1541:R
1535:0
1532:=
1529::
1526:)
1523:i
1520:(
1517:q
1508:1
1505:=
1502::
1499:)
1496:i
1493:(
1490:q
1484:0
1478:R
1469:D
1466:−
1463:R
1460:*
1457:2
1454:=
1451::
1448:R
1439:0
1433:1
1430:−
1427:n
1424:=
1421::
1418:i
1409:n
1403:D
1400:=
1397::
1394:D
1391:N
1388:=
1385::
1382:R
1372:q
1365:N
1361:D
1344:D
1338:n
1332:n
1328:j
1324:n
1318:j
1314:n
1310:q
1300:B
1294:j
1289:j
1285:R
1265:,
1262:D
1254:)
1251:1
1248:+
1245:j
1242:(
1236:n
1232:q
1223:j
1219:R
1212:B
1209:=
1204:1
1201:+
1198:j
1194:R
1168:2
1044:2
1036:2
1018:1
1015:=
1012::
1009:)
1006:i
1003:(
1000:Q
997:D
994:−
991:R
988:=
985::
982:R
976:D
973:≥
970:R
961:)
958:i
955:(
952:N
949:=
946::
943:)
940:0
937:(
934:R
928:1
922:R
919:=
916::
913:R
904:0
898:1
895:−
892:n
889:=
886::
883:i
877:0
874:=
871::
868:R
862:0
859:=
856::
853:Q
847:)
841:(
832:0
829:=
826:D
816:R
812:Q
808:D
804:N
745:)
742:R
739:,
736:Q
733:(
724:D
721:−
718:R
715:=
712::
709:R
706:1
703:+
700:Q
697:=
694::
691:Q
685:D
682:≥
679:R
673:N
670:=
667::
664:R
661:;
658:0
655:=
652::
649:Q
646:)
643:D
640:,
637:N
634:(
622:)
619:D
616:,
613:N
610:(
592:)
589:R
586:−
583:D
580:,
577:1
574:−
571:Q
568:−
565:(
556:)
553:0
550:,
547:Q
544:−
541:(
532:0
529:=
526:R
520:)
517:D
514:,
511:N
508:−
505:(
499:=
496::
493:)
490:R
487:,
484:Q
481:(
475:0
469:N
460:)
457:R
454:,
451:Q
448:−
445:(
436:D
433:−
430:,
427:N
424:(
418:=
415::
412:)
409:R
406:,
403:Q
400:(
394:0
388:D
379:)
373:(
364:0
361:=
358:D
352:)
349:D
346:,
343:N
340:(
320:)
317:R
314:,
311:Q
308:(
299:1
296:+
293:Q
290:=
287::
284:Q
281:D
278:−
275:R
272:=
269::
266:R
260:D
257:≥
254:R
248:0
245:=
242::
239:Q
236:N
233:=
230::
227:R
194:R
185:Q
170:D
160:N
143:)
140:R
137:,
134:Q
131:(
128:=
125:D
121:/
117:N
58:D
54:N
38:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.