816:
455:
811:{\displaystyle {\begin{aligned}&k=0:\lfloor {\sqrt {2\times 100^{0}}}\rfloor =\lfloor {\sqrt {2}}\rfloor =1\\&k=1:\lfloor {\sqrt {2\times 100^{1}}}\rfloor =\lfloor {\sqrt {200}}\rfloor =14\\&k=2:\lfloor {\sqrt {2\times 100^{2}}}\rfloor =\lfloor {\sqrt {20000}}\rfloor =141\\&k=3:\lfloor {\sqrt {2\times 100^{3}}}\rfloor =\lfloor {\sqrt {2000000}}\rfloor =1414\\&\vdots \\&k=8:\lfloor {\sqrt {2\times 100^{8}}}\rfloor =\lfloor {\sqrt {20000000000000000}}\rfloor =141421356\\&\vdots \\\end{aligned}}}
2865:
4985:
2435:
4876:
3894:
3739:
2860:{\displaystyle {\begin{aligned}&\rightarrow \rightarrow \rightarrow \rightarrow \rightarrow \rightarrow \rightarrow \\&\rightarrow \rightarrow \rightarrow \rightarrow \rightarrow \rightarrow \rightarrow \rightarrow \\&\rightarrow \rightarrow \rightarrow \rightarrow \rightarrow \rightarrow \end{aligned}}}
5778:
The algorithm works by first normalizing the input. It then recursively calls itself (or another algorithm that's faster when the number of bits gets small enough) with the most-significant half of the normalized input's bits. It then processes the returned integer square root and remainder to
3746:
4987:
In total 13 iteration steps are needed. Although Heron's method converges quadratically close to the solution, less than one bit precision per iteration is gained at the beginning. This means that the choice of the initial estimate is critical for the performance of the algorithm.
4980:{\displaystyle {\begin{aligned}&1000000\rightarrow 500001\rightarrow 250002\rightarrow 125004\rightarrow 62509\rightarrow 31270\rightarrow 15666\rightarrow 7896\\&\rightarrow 4074\rightarrow 2282\rightarrow 1579\rightarrow 1422\rightarrow 1414\rightarrow 1414\end{aligned}}}
3581:
5750:
Traditional pen-and-paper presentations of the digit-by-digit algorithm include various optimizations not present in the code above, in particular the trick of pre-subtracting the square of the previous digits which makes a general multiplication step unnecessary. See
167:
3122:
1403:
4214:
5254:
4327:
848:
1459:
7835:
99:
4124:
3367:
4443:
4385:
3889:{\displaystyle \left\lfloor {\frac {1}{2}}\!\left(x_{k}+\left\lfloor {\frac {n}{x_{k}}}\right\rfloor \right)\right\rfloor =\left\lfloor {\frac {1}{2}}\!\left(x_{k}+{\frac {n}{x_{k}}}\right)\right\rfloor ,}
1893:
7039:
5087:
1513:
418:
3007:
4881:
2440:
460:
5327:, the choice of digit is simplified to that between 0 (the "small candidate") and 1 (the "large candidate"), and digit manipulations can be expressed in terms of binary shift operations. With
3734:{\displaystyle x_{k+1}=\left\lfloor {\frac {1}{2}}\!\left(x_{k}+\left\lfloor {\frac {n}{x_{k}}}\right\rfloor \right)\right\rfloor ,\quad k\geq 0,\quad x_{0}>0,\quad x_{0}\in \mathbb {Z} .}
2398:
1070:
5164:
4628:
1003:
4592:
4510:
4476:
3926:
3564:
305:
7839:
3526:
2955:
1035:
940:
3966:
106:
4075:
3312:
7347:
5210:
4038:
1314:
5215:
3216:
5290:
5115:
3406:
3190:
2923:
1094:
908:
332:
245:
2140:
5883:
3463:
3160:
3002:
7380:
3992:
877:
5313:
4268:
4241:
3490:
4562:
4536:
3250:
980:
450:
5844:
5824:
5804:
3430:
2887:
2107:
1309:
960:
375:
352:
268:
214:
194:
2430:
6961:
The square roots of the perfect squares (e.g., 0, 1, 4, 9, 16) are integers. In all other cases, the square roots of positive integers are irrational numbers.
4129:
53:
4273:
823:
7168:
7704:
7340:
7204:
1785:
6744:
dedicate an explicit operation to the integer square root calculation in addition to the general case or can be extended by libraries to this end.
5010:
7572:
1410:
7895:
7514:
7333:
4080:
7443:
7620:
7032:
3317:
3574:
for both of the division operations. This has the advantage of only using integers for each intermediate value, thus making the use of
4390:
4332:
7096:
7418:
7299:
6941:
5752:
5265:
2958:
1270:
7529:
7905:
7567:
7504:
7013:
1037:
is already defined and — for the sake of the argument — that all variables can hold integers of unlimited magnitude.
7448:
7411:
7709:
7600:
7519:
7509:
7385:
7537:
6795:
5764:
5292:
is based on working from higher digit places to lower, and as each new digit pick the largest that will still yield a square
7790:
1464:
3376:
exactly (for example, floating point), a stopping constant less than 1 should be used to protect against round-off errors.
380:
6904:
6855:
6840:
6761:
3255:
7785:
7714:
7615:
7752:
6810:
5340:
7666:
7222:
6874:
2371:
1043:
7831:
7821:
7780:
7556:
7550:
7524:
7395:
5124:
4597:
1782:
In the program above (linear search, ascending) one can replace multiplication by addition, using the equivalence
988:
7816:
7757:
4567:
4485:
4479:
4451:
3901:
3539:
280:
7060:
7719:
7592:
7438:
7390:
5768:
3499:
2928:
1008:
913:
162:{\displaystyle \operatorname {isqrt} (27)=\lfloor {\sqrt {27}}\rfloor =\lfloor 5.19615242270663...\rfloor =5.}
3117:{\displaystyle x_{k+1}={\frac {1}{2}}\!\left(x_{k}+{\frac {n}{x_{k}}}\right),\quad k\geq 0,\quad x_{0}>0.}
7734:
7625:
2146:
2086:
5782:
Here is an example implementation for 64-bit unsigned integers that uses an unshown 32-bit implementation (
3934:
7900:
7845:
7795:
7775:
4043:
220:
7496:
7471:
7400:
7855:
5169:
3997:
7850:
7742:
7724:
7699:
7661:
7405:
6741:
1289:
28:
7317:
7132:
7078:
7860:
7747:
7651:
7610:
7605:
7582:
7486:
5772:
3493:
3165:
3162:
3195:
7691:
7638:
7635:
7476:
7375:
5271:
5096:
3571:
3387:
3171:
2904:
1075:
889:
313:
226:
7432:
7425:
2962:
2112:
5849:
3578:
representations of large numbers unnecessary. It is equivalent to using the iterative formula
3435:
3132:
2968:
7811:
7767:
7481:
7458:
7305:
7295:
7264:
7043:
3409:
3971:
855:
7656:
6825:
5295:
4992:
4246:
4219:
3468:
2869:
This computation takes 21 iteration steps, whereas linear search (ascending, starting from
7646:
7545:
5315:. If stopping after the one's place, the result computed will be the integer square root.
3373:
7150:
7114:
5779:
produce the normalized correct result. It then denormalizes the result and returns that.
4541:
4515:
3229:
965:
429:
1398:{\displaystyle \lfloor {\sqrt {y}}\rfloor =x:x^{2}\leq y<(x+1)^{2},x\in \mathbb {N} }
7676:
7577:
7562:
7466:
7367:
7288:
5829:
5809:
5789:
5344:
3575:
3415:
2872:
2092:
1294:
945:
360:
337:
253:
199:
179:
39:
7186:
7017:
4209:{\displaystyle x_{k}\geq \lfloor x_{k}\rfloor >x_{k+1}\geq \lfloor x_{k+1}\rfloor }
2403:
7889:
7671:
7356:
7283:
7240:
5249:{\displaystyle 2048\rightarrow 1512\rightarrow 1417\rightarrow 1414\rightarrow 1414.}
4322:{\displaystyle \lfloor {\sqrt {n}}\rfloor \leq \lfloor x_{s}\rfloor \leq {\sqrt {n}}}
271:
20:
7681:
5090:
843:{\displaystyle {\sqrt {2}}=1.41421356237309504880168872420969807856967187537694...}
6960:
6780:
43:
7325:
7309:
4996:
7359:
6889:
3127:
1454:{\displaystyle \operatorname {isqrt} (27)=\lfloor {\sqrt {27}}\rfloor =5}
5004:
4564:
is a perfect square, the sequence ends up in a period-two cycle between
5753:
Methods of computing square roots § Binary numeral system (base 2)
6987:
The fractional part of square roots of perfect squares is rendered as
3372:
In implementations which use number formats that cannot represent all
94:{\displaystyle \operatorname {isqrt} (n)=\lfloor {\sqrt {n}}\rfloor .}
5324:
4119:{\displaystyle \lfloor x_{k}\rfloor \geq \lfloor {\sqrt {n}}\rfloor }
6156:// most significant bit or its neighbor must be a 1. Since aâ's
6153:// bit (010...0) in binary. Since aâ must be at least b/4, aâ's
6138:// algorithm precondition "aâ â„ b/4" where aâ is the most
3362:{\displaystyle \lfloor x_{k+1}\rfloor =\lfloor {\sqrt {n}}\rfloor }
3492:
is rational. Thus, with this method it is unnecessary to exit the
7205:"Elements of the ring †of integers - Standard Commutative Rings"
6159:// most significant bits are `n`'s most significant bits, the
4438:{\displaystyle \lfloor x_{k+1}\rfloor \geq \lfloor x_{k}\rfloor }
4380:{\displaystyle \lfloor x_{s+1}\rfloor \geq \lfloor x_{s}\rfloor }
3252:
is the largest possible number for which the stopping criterion
7329:
6141:// significant quarter of `n`'s bits and b is the number of
6919:
6171:// even number of bits produces the square root shifted to the
6168:// The reason to shift by an even number of bits is because an
6150:// b/4 would then be all 0s except the second most significant
6144:// values that can be represented by that quarter of the bits.
6135:// The normalization shift satisfies the Karatsuba square root
1888:{\displaystyle (L+1)^{2}=L^{2}+2L+1=L^{2}+1+\sum _{i=1}^{L}2.}
1523:
The following C programs are straightforward implementations.
5694:# Same as result ^ 1 (xor), because the last bit is always 0.
4482:
of the above iterative formula. Indeed, it can be shown that
6054:// If `n` fits in a `u32`, let the `u32` function handle it.
5763:
The
Karatsuba square root algorithm is a fast algorithm for
6198:// Shifting by an odd number of bits leaves an ugly sqrt(2)
5082:{\displaystyle x_{0}=2^{\lfloor (\log _{2}n)/2\rfloor +1},}
2089:
sequentially checks every value until it hits the smallest
5583:# shift = ceil(log2(n) * 0.5) * 2 = ceil(ffs(n) * 0.5) * 2
4869:
For example, if one computes the integer square root of
2149:
instead. The following C-program is an implementation.
7876:
indicate that algorithm is for numbers of special forms
838:
1.41421356237309504880168872420969807856967187537694...
6971:
It is no surprise that the repeated multiplication by
1508:{\displaystyle 6^{2}>27{\text{ and }}5^{2}\ngtr 27}
413:{\textstyle \lfloor {\sqrt {y\times 100^{k}}}\rfloor }
383:
5852:
5832:
5812:
5792:
5298:
5274:
5218:
5172:
5127:
5099:
5013:
4879:
4600:
4570:
4544:
4518:
4488:
4454:
4393:
4335:
4276:
4249:
4222:
4132:
4083:
4046:
4000:
3974:
3937:
3904:
3749:
3584:
3542:
3502:
3471:
3438:
3418:
3390:
3320:
3258:
3232:
3198:
3174:
3135:
3010:
2971:
2931:
2907:
2875:
2438:
2406:
2374:
2115:
2095:
1788:
1467:
1413:
1317:
1297:
1078:
1046:
1011:
991:
968:
948:
916:
892:
858:
826:
458:
432:
363:
340:
316:
283:
256:
229:
202:
182:
109:
56:
4991:
When a fast computation for the integer part of the
4873:
using the algorithm above, one obtains the sequence
7804:
7766:
7733:
7690:
7634:
7591:
7495:
7457:
7366:
7241:"mathfunc manual page - Tcl Mathematical Functions"
7223:"Revised Report on the Algorithmic Language Scheme"
5556:"sqrt works for only non-negative inputs"
5397:"sqrt works for only non-negative inputs"
5256:In this case only four iteration steps are needed.
1272:
1266:
852:It appears that the multiplication of the input by
7287:
5877:
5838:
5818:
5798:
5307:
5284:
5248:
5204:
5158:
5109:
5081:
4979:
4622:
4586:
4556:
4530:
4504:
4470:
4437:
4379:
4321:
4262:
4235:
4208:
4118:
4069:
4032:
3986:
3960:
3920:
3888:
3733:
3558:
3520:
3484:
3457:
3424:
3400:
3361:
3306:
3244:
3210:
3184:
3154:
3116:
2996:
2949:
2917:
2881:
2859:
2424:
2392:
2134:
2101:
1887:
1507:
1453:
1397:
1303:
1088:
1064:
1029:
997:
974:
954:
934:
902:
886:To compute the (entire) decimal representation of
871:
842:
810:
444:
412:
369:
346:
326:
299:
262:
239:
208:
188:
161:
93:
16:Greatest integer less than or equal to square root
5343:algorithm to find the integer square root of any
3837:
3765:
3619:
3040:
5890:/// Performs a Karatsuba square root on a `u64`.
3528:, a fact which has some theoretical advantages.
1265:The conclusion is that algorithms which compute
1072:will print the entire decimal representation of
7318:"A geometric view of the square root algorithm"
7065:Chapel Documentation - Chapel Documentation 2.1
5117:. In the example of the integer square root of
2393:{\displaystyle \operatorname {isqrt} (2000000)}
1065:{\displaystyle \operatorname {sqrtForever} (y)}
7341:
5159:{\displaystyle \lfloor \log _{2}n\rfloor =20}
4623:{\displaystyle \lfloor {\sqrt {n}}\rfloor +1}
310:. They are nevertheless capable of computing
8:
7014:"Square root by abacus algorithm (archived)"
5147:
5128:
5065:
5032:
4611:
4601:
4581:
4571:
4499:
4489:
4465:
4455:
4432:
4419:
4413:
4394:
4374:
4361:
4355:
4336:
4306:
4293:
4287:
4277:
4203:
4184:
4159:
4146:
4113:
4103:
4097:
4084:
3915:
3905:
3553:
3543:
3452:
3439:
3356:
3346:
3340:
3321:
3149:
3136:
2154:// Integer square root (using binary search)
1902:// (linear search, ascending) using addition
1442:
1432:
1328:
1318:
1170:// print result, followed by a decimal point
998:{\displaystyle \operatorname {sqrtForever} }
785:
775:
769:
746:
710:
700:
694:
671:
645:
635:
629:
606:
580:
570:
564:
541:
515:
505:
499:
476:
407:
384:
294:
284:
150:
144:
138:
128:
85:
75:
6174:// left by half of the normalization shift:
4587:{\displaystyle \lfloor {\sqrt {n}}\rfloor }
4505:{\displaystyle \lfloor {\sqrt {n}}\rfloor }
4471:{\displaystyle \lfloor {\sqrt {n}}\rfloor }
3921:{\displaystyle \lfloor {\sqrt {n}}\rfloor }
3559:{\displaystyle \lfloor {\sqrt {n}}\rfloor }
1209:// theoretical example: overflow is ignored
300:{\displaystyle \lfloor {\sqrt {y}}\rfloor }
7348:
7334:
7326:
7286:(1967). "9. The Computable Real Numbers".
3496:of rational numbers in order to calculate
1563:// initial underestimate, L <= isqrt(y)
7290:Computation: Finite and Infinite Machines
7101:The Crystal Programming Language API docs
6771:BigInteger.sqrtRem(result, remainder, n);
5869:
5851:
5831:
5811:
5791:
5297:
5275:
5273:
5217:
5190:
5177:
5171:
5135:
5126:
5100:
5098:
5057:
5042:
5031:
5018:
5012:
4880:
4878:
4604:
4599:
4574:
4569:
4543:
4517:
4492:
4487:
4458:
4453:
4426:
4401:
4392:
4368:
4343:
4334:
4312:
4300:
4280:
4275:
4254:
4248:
4227:
4221:
4191:
4169:
4153:
4137:
4131:
4106:
4091:
4082:
4060:
4051:
4045:
4018:
4005:
3999:
3973:
3951:
3942:
3936:
3908:
3903:
3865:
3856:
3847:
3827:
3797:
3788:
3775:
3755:
3748:
3724:
3723:
3714:
3694:
3651:
3642:
3629:
3609:
3589:
3583:
3546:
3541:
3521:{\displaystyle \operatorname {isqrt} (n)}
3501:
3476:
3470:
3446:
3437:
3417:
3391:
3389:
3349:
3328:
3319:
3293:
3287:
3268:
3259:
3257:
3231:
3197:
3175:
3173:
3143:
3134:
3102:
3068:
3059:
3050:
3030:
3015:
3009:
2976:
2970:
2950:{\displaystyle \operatorname {isqrt} (n)}
2930:
2908:
2906:
2874:
2439:
2437:
2405:
2373:
2120:
2114:
2094:
1876:
1865:
1846:
1818:
1805:
1787:
1698:// initial overestimate, isqrt(y) <= R
1493:
1484:
1472:
1466:
1435:
1412:
1391:
1390:
1375:
1344:
1321:
1316:
1296:
1079:
1077:
1045:
1030:{\displaystyle \operatorname {isqrt} (y)}
1010:
990:
967:
947:
935:{\displaystyle \operatorname {isqrt} (y)}
915:
893:
891:
863:
857:
827:
825:
778:
761:
749:
703:
686:
674:
638:
621:
609:
573:
556:
544:
508:
491:
479:
459:
457:
431:
399:
387:
382:
362:
339:
317:
315:
287:
282:
255:
230:
228:
201:
181:
131:
108:
78:
55:
7119:Julia Documentation - The Julia Language
6746:
5806:) and produces the integer square root (
942:an infinite number of times, increasing
7061:"BigInteger - Chapel Documentation 2.1"
7004:
6953:
7042:(published 2006-05-24). Archived from
6976:
4703:// Initial estimate (must be too high)
3928:within a finite number of iterations.
2965:, to find a solution for the equation
7155:Python Standard Library documentation
4077:. So in the integer version, one has
3961:{\displaystyle x_{k}\geq {\sqrt {n}}}
2400:using binary search, one obtains the
7:
7187:"class Integer - RDoc Documentation"
5580:# Find the shift amount. See also ],
4070:{\displaystyle x_{k}>{\sqrt {n}}}
3307:{\displaystyle |x_{k+1}-x_{k}|<c}
1668:// (using linear search, descending)
5769:Burnikel-Ziegler Karatsuba division
4243:is reached. For the final solution
1533:// (using linear search, ascending)
40:greatest integer less than or equal
7115:"Mathematics - The Julia Language"
3898:one can show that this will reach
3465:contains only rational terms when
3205:
1269:are computationally equivalent to
14:
7557:Special number field sieve (SNFS)
7551:General number field sieve (GNFS)
6942:Methods of computing square roots
5205:{\displaystyle x_{0}=2^{11}=2048}
3931:In the original version, one has
1101:// Print sqrt(y), without halting
985:Assume that in the next program (
5212:, and the resulting sequence is
4512:is a fixed point if and only if
4033:{\displaystyle x_{k}>x_{k+1}}
2145:A speed-up is achieved by using
6186:// sqrt(2.pow(2 * p)) * sqrt(n)
5767:of "50 to 1,000,000 digits" if
5759:Karatsuba square root algorithm
5007:), one should better start at
4387:, so the stopping criterion is
3709:
3689:
3676:
3097:
3084:
3004:, giving the iterative formula
2897:Algorithm using Newton's method
7263:Jarvis, Ashley Frazer (2006).
5631:# Unroll the bit-setting loop.
5268:for computing the square root
5240:
5234:
5228:
5222:
5054:
5035:
4967:
4961:
4955:
4949:
4943:
4937:
4924:
4918:
4912:
4906:
4900:
4894:
4888:
3570:, one can use the quotient of
3515:
3509:
3294:
3260:
3202:
2944:
2938:
2850:
2838:
2835:
2832:
2820:
2817:
2814:
2802:
2799:
2796:
2784:
2781:
2778:
2766:
2763:
2760:
2748:
2745:
2735:
2723:
2720:
2717:
2705:
2702:
2699:
2687:
2684:
2681:
2669:
2666:
2663:
2651:
2648:
2645:
2633:
2630:
2627:
2615:
2612:
2609:
2597:
2594:
2584:
2572:
2569:
2566:
2554:
2551:
2548:
2536:
2533:
2530:
2518:
2515:
2512:
2500:
2497:
2494:
2482:
2479:
2476:
2464:
2461:
2458:
2446:
2419:
2407:
2387:
2381:
1802:
1789:
1426:
1420:
1372:
1359:
1059:
1053:
1024:
1018:
929:
923:
122:
116:
69:
63:
1:
7265:"Square roots by subtraction"
5339:being logical right shift, a
2961:, which is a special case of
2368:For example, if one computes
2082:Algorithm using binary search
1519:Algorithm using linear search
1254:// print last digit of result
219:Algorithms that compute (the
7515:Lenstra elliptic curve (ECM)
7079:"CLHS: Function SQRT, ISQRT"
4538:is not a perfect square. If
3211:{\displaystyle k\to \infty }
1778:Linear search using addition
34:is the non-negative integer
7896:Number theoretic algorithms
6767:BigInteger.sqrt(result, n);
6180:// sqrt(n << (2 * p))
5285:{\displaystyle {\sqrt {n}}}
5110:{\displaystyle {\sqrt {n}}}
4634:Example implementation in C
3532:Using only integer division
3401:{\displaystyle {\sqrt {n}}}
3185:{\displaystyle {\sqrt {n}}}
2918:{\displaystyle {\sqrt {n}}}
1089:{\displaystyle {\sqrt {y}}}
903:{\displaystyle {\sqrt {y}}}
334:up to any desired accuracy
327:{\displaystyle {\sqrt {y}}}
240:{\displaystyle {\sqrt {y}}}
7922:
7822:Exponentiation by squaring
7505:Continued fraction (CFRAC)
7083:Common Lisp HyperSpec (TM)
6865:(integer-sqrt/remainder n)
2135:{\displaystyle x^{2}>y}
216:be non-negative integers.
7869:
7038:. Research report #3805.
7031:Zimmermann, Paul (1999).
6183:// sqrt(2.pow(2 * p) * n)
5878:{\displaystyle r=n-s^{2}}
4640:// Square root of integer
4216:until the final solution
3458:{\displaystyle \{x_{k}\}}
3155:{\displaystyle \{x_{k}\}}
2997:{\displaystyle x^{2}-n=0}
1271:algorithms which compute
820:Compare the results with
7169:"4.3.2 Generic Numerics"
7151:"Mathematical functions"
6736:In programming languages
6343:u32_isqrt_with_remainder
6078:u32_isqrt_with_remainder
5896:u64_isqrt_with_remainder
5887:
5784:u32_isqrt_with_remainder
5773:Karatsuba multiplication
5349:
5319:Using bitwise operations
5260:Digit-by-digit algorithm
4999:is available (like e.g.
4637:
3566:for very large integers
3369:in the algorithm above.
2151:
1896:
1662:
1527:
1098:
277:Algorithms that compute
7906:Root-finding algorithms
7735:Greatest common divisor
7097:"Math - Crystal 1.13.2"
7033:"Karatsuba Square Root"
6162:// same applies to `n`.
5266:pen-and-paper algorithm
4630:instead of converging.
3987:{\displaystyle k\geq 1}
3743:By using the fact that
2901:One way of calculating
872:{\displaystyle 100^{k}}
7846:Modular exponentiation
7209:SageMath Documentation
6910:(exact-integer-sqrt n)
5879:
5840:
5820:
5800:
5786:) and takes an input (
5335:being left shift, and
5331:being multiplication,
5309:
5308:{\displaystyle \leq n}
5286:
5250:
5206:
5160:
5111:
5083:
4981:
4624:
4588:
4558:
4532:
4506:
4472:
4439:
4381:
4323:
4264:
4237:
4210:
4120:
4071:
4034:
3988:
3962:
3922:
3890:
3735:
3560:
3522:
3486:
3459:
3426:
3402:
3363:
3308:
3246:
3212:
3186:
3156:
3118:
2998:
2951:
2919:
2896:
2883:
2861:
2426:
2394:
2136:
2103:
1899:// Integer square root
1889:
1881:
1665:// Integer square root
1530:// Integer square root
1509:
1455:
1399:
1305:
1090:
1066:
1031:
999:
976:
956:
936:
904:
873:
844:
812:
446:
414:
371:
348:
328:
301:
264:
241:
221:decimal representation
210:
190:
163:
95:
7573:Shanks's square forms
7497:Integer factorization
7472:Sieve of Eratosthenes
7272:Mathematical Spectrum
6742:programming languages
6721:denormalization_shift
6709:denormalization_shift
6679:denormalization_shift
6192:// sqrt(n) << p
6189:// 2.pow(p) * sqrt(n)
5880:
5841:
5826:) and the remainder (
5821:
5801:
5310:
5287:
5251:
5207:
5161:
5112:
5084:
4982:
4625:
4589:
4559:
4533:
4507:
4478:is not necessarily a
4473:
4440:
4382:
4324:
4265:
4263:{\displaystyle x_{s}}
4238:
4236:{\displaystyle x_{s}}
4211:
4121:
4072:
4035:
3989:
3963:
3923:
3891:
3736:
3561:
3523:
3487:
3485:{\displaystyle x_{0}}
3460:
3427:
3403:
3380:Domain of computation
3364:
3309:
3247:
3213:
3187:
3157:
3119:
2999:
2952:
2920:
2884:
2862:
2427:
2395:
2137:
2104:
1890:
1861:
1510:
1456:
1400:
1306:
1185:// repeat forever ...
1091:
1067:
1032:
1000:
977:
957:
937:
905:
879:gives an accuracy of
874:
845:
813:
447:
415:
372:
349:
329:
302:
265:
242:
211:
191:
164:
96:
7851:Montgomery reduction
7725:Function field sieve
7700:Baby-step giant-step
7546:Quadratic sieve (QS)
7173:Racket Documentation
7012:Woo, C (June 1985).
6750:Programming language
5850:
5830:
5810:
5790:
5296:
5272:
5216:
5170:
5125:
5097:
5011:
4877:
4598:
4568:
4542:
4516:
4486:
4452:
4391:
4333:
4274:
4247:
4220:
4130:
4081:
4044:
3998:
3972:
3935:
3902:
3747:
3582:
3540:
3500:
3469:
3436:
3416:
3388:
3318:
3256:
3230:
3196:
3172:
3133:
3008:
2969:
2929:
2905:
2873:
2436:
2404:
2372:
2113:
2093:
1786:
1465:
1411:
1315:
1295:
1290:non-negative integer
1076:
1044:
1009:
989:
966:
946:
914:
890:
856:
824:
456:
430:
381:
361:
338:
314:
281:
254:
227:
200:
180:
107:
54:
29:non-negative integer
7861:Trachtenberg system
7827:Integer square root
7768:Modular square root
7487:Wheel factorization
7439:Quadratic Frobenius
7419:LucasâLehmerâRiesel
7133:"iroot- Maple Help"
6756:Version introduced
6685:normalization_shift
6262:normalization_shift
6250:EVEN_MAKING_BITMASK
6229:normalization_shift
6207:EVEN_MAKING_BITMASK
5089:which is the least
4670:// Zero yields zero
4557:{\displaystyle n+1}
4531:{\displaystyle n+1}
3245:{\displaystyle c=1}
3226:One can prove that
1286:integer square root
975:{\displaystyle 100}
445:{\displaystyle y=2}
172:Introductory remark
148:5.19615242270663...
25:integer square root
7753:Extended Euclidean
7692:Discrete logarithm
7621:SchönhageâStrassen
7477:Sieve of Pritchard
7191:RDoc Documentation
5875:
5836:
5816:
5796:
5305:
5282:
5246:
5202:
5156:
5107:
5079:
4977:
4975:
4620:
4584:
4554:
4528:
4502:
4468:
4435:
4377:
4319:
4260:
4233:
4206:
4116:
4067:
4030:
3984:
3958:
3918:
3886:
3731:
3572:Euclidean division
3556:
3518:
3482:
3455:
3422:
3398:
3359:
3304:
3242:
3222:Stopping criterion
3208:
3182:
3152:
3114:
2994:
2947:
2915:
2879:
2857:
2855:
2422:
2390:
2132:
2099:
1885:
1505:
1451:
1395:
1311:can be defined as
1301:
1086:
1062:
1027:
995:
972:
952:
932:
910:, one can execute
900:
869:
840:
808:
806:
442:
410:
367:
344:
324:
308:do not run forever
297:
260:
237:
206:
186:
159:
91:
7883:
7882:
7482:Sieve of Sundaram
7294:. Prentice-Hall.
7245:Tcl/Tk 8.6 Manual
6933:
6932:
6316:LOWER_HALF_1_BITS
6201:// multiplied in.
5995:LOWER_HALF_1_BITS
5839:{\displaystyle r}
5819:{\displaystyle s}
5799:{\displaystyle n}
5514:integer_sqrt_iter
5421:# Recursive call:
5280:
5105:
4865:Numerical example
4673:// One yields one
4609:
4579:
4497:
4463:
4317:
4285:
4111:
4065:
3956:
3913:
3871:
3835:
3803:
3763:
3657:
3617:
3551:
3425:{\displaystyle n}
3396:
3354:
3180:
3074:
3038:
2913:
2882:{\displaystyle 0}
2364:Numerical example
2102:{\displaystyle x}
1487:
1440:
1326:
1304:{\displaystyle y}
1084:
955:{\displaystyle y}
898:
832:
783:
781:20000000000000000
767:
708:
692:
643:
627:
578:
562:
513:
497:
405:
370:{\displaystyle k}
347:{\displaystyle k}
322:
292:
263:{\displaystyle y}
235:
209:{\displaystyle k}
189:{\displaystyle y}
136:
83:
7913:
7832:Integer relation
7805:Other algorithms
7710:Pollard kangaroo
7601:Ancient Egyptian
7459:Prime-generating
7444:SolovayâStrassen
7357:Number-theoretic
7350:
7343:
7336:
7327:
7321:
7313:
7293:
7279:
7269:
7249:
7248:
7237:
7231:
7230:
7227:Scheme Standards
7219:
7213:
7212:
7201:
7195:
7194:
7183:
7177:
7176:
7165:
7159:
7158:
7147:
7141:
7140:
7137:Help - Maplesoft
7129:
7123:
7122:
7111:
7105:
7104:
7093:
7087:
7086:
7075:
7069:
7068:
7057:
7051:
7050:
7048:
7037:
7028:
7022:
7021:
7016:. Archived from
7009:
6992:
6990:
6985:
6979:
6975:is a feature in
6974:
6969:
6963:
6958:
6926:
6911:
6896:
6881:
6866:
6862:
6861:(integer-sqrt n)
6847:
6832:
6817:
6802:
6787:
6772:
6768:
6747:
6731:
6728:
6725:
6722:
6719:
6716:
6713:
6710:
6707:
6704:
6701:
6698:
6695:
6692:
6689:
6686:
6683:
6680:
6677:
6674:
6671:
6668:
6665:
6662:
6659:
6656:
6653:
6650:
6647:
6644:
6641:
6638:
6635:
6632:
6629:
6626:
6623:
6620:
6617:
6614:
6611:
6608:
6605:
6602:
6599:
6596:
6593:
6590:
6587:
6584:
6581:
6578:
6575:
6572:
6569:
6566:
6563:
6560:
6557:
6554:
6551:
6548:
6545:
6542:
6539:
6536:
6533:
6530:
6527:
6524:
6521:
6518:
6515:
6512:
6509:
6506:
6503:
6500:
6497:
6494:
6491:
6488:
6485:
6482:
6479:
6476:
6473:
6470:
6467:
6464:
6461:
6458:
6455:
6452:
6449:
6446:
6443:
6440:
6437:
6434:
6431:
6428:
6425:
6422:
6419:
6416:
6413:
6410:
6407:
6404:
6401:
6398:
6395:
6392:
6389:
6386:
6383:
6380:
6377:
6374:
6371:
6368:
6365:
6362:
6359:
6356:
6353:
6350:
6347:
6344:
6341:
6338:
6335:
6332:
6329:
6326:
6323:
6320:
6317:
6314:
6311:
6308:
6305:
6302:
6299:
6296:
6293:
6290:
6287:
6284:
6281:
6278:
6275:
6272:
6269:
6266:
6263:
6260:
6257:
6254:
6251:
6248:
6245:
6242:
6239:
6236:
6233:
6230:
6227:
6224:
6221:
6218:
6215:
6212:
6208:
6205:
6202:
6199:
6196:
6193:
6190:
6187:
6184:
6181:
6178:
6175:
6172:
6169:
6166:
6163:
6160:
6157:
6154:
6151:
6148:
6145:
6142:
6139:
6136:
6133:
6130:
6127:
6124:
6121:
6118:
6115:
6112:
6109:
6106:
6103:
6100:
6097:
6094:
6091:
6088:
6085:
6082:
6079:
6076:
6073:
6070:
6067:
6064:
6061:
6058:
6055:
6052:
6049:
6046:
6043:
6039:
6036:
6033:
6030:
6027:
6024:
6021:
6018:
6015:
6012:
6009:
6006:
6003:
6000:
5996:
5993:
5990:
5987:
5984:
5981:
5977:
5974:
5971:
5967:
5964:
5961:
5958:
5955:
5952:
5948:
5945:
5942:
5938:
5935:
5932:
5929:
5926:
5923:
5920:
5917:
5913:
5910:
5906:
5903:
5900:
5897:
5894:
5891:
5884:
5882:
5881:
5876:
5874:
5873:
5845:
5843:
5842:
5837:
5825:
5823:
5822:
5817:
5805:
5803:
5802:
5797:
5785:
5755:for an example.
5746:
5743:
5740:
5737:
5734:
5731:
5728:
5725:
5722:
5719:
5716:
5713:
5710:
5707:
5704:
5701:
5698:
5695:
5692:
5689:
5686:
5683:
5680:
5677:
5674:
5671:
5668:
5665:
5662:
5659:
5656:
5653:
5650:
5647:
5644:
5641:
5638:
5635:
5632:
5629:
5626:
5623:
5620:
5617:
5614:
5611:
5608:
5605:
5602:
5599:
5596:
5593:
5590:
5587:
5584:
5581:
5578:
5575:
5572:
5569:
5566:
5563:
5560:
5557:
5554:
5551:
5548:
5545:
5542:
5539:
5536:
5533:
5530:
5527:
5524:
5521:
5518:
5515:
5512:
5509:
5506:
5503:
5500:
5497:
5494:
5491:
5488:
5485:
5482:
5479:
5476:
5473:
5470:
5467:
5464:
5461:
5458:
5455:
5452:
5449:
5446:
5443:
5440:
5437:
5434:
5431:
5428:
5425:
5422:
5419:
5416:
5413:
5410:
5407:
5404:
5401:
5398:
5395:
5392:
5389:
5386:
5383:
5380:
5377:
5374:
5371:
5368:
5365:
5362:
5359:
5356:
5353:
5338:
5334:
5330:
5314:
5312:
5311:
5306:
5291:
5289:
5288:
5283:
5281:
5276:
5264:The traditional
5255:
5253:
5252:
5247:
5211:
5209:
5208:
5203:
5195:
5194:
5182:
5181:
5165:
5163:
5162:
5157:
5140:
5139:
5120:
5116:
5114:
5113:
5108:
5106:
5101:
5088:
5086:
5085:
5080:
5075:
5074:
5061:
5047:
5046:
5023:
5022:
5002:
4993:binary logarithm
4986:
4984:
4983:
4978:
4976:
4933:
4883:
4872:
4860:
4857:
4854:
4851:
4848:
4845:
4842:
4839:
4836:
4833:
4830:
4827:
4824:
4821:
4818:
4815:
4812:
4809:
4806:
4803:
4800:
4797:
4794:
4791:
4788:
4785:
4782:
4779:
4776:
4773:
4770:
4767:
4764:
4761:
4758:
4755:
4752:
4749:
4746:
4743:
4740:
4737:
4734:
4731:
4728:
4725:
4722:
4719:
4716:
4713:
4710:
4707:
4704:
4701:
4698:
4695:
4692:
4689:
4686:
4683:
4680:
4677:
4674:
4671:
4668:
4665:
4662:
4659:
4656:
4653:
4650:
4647:
4644:
4641:
4629:
4627:
4626:
4621:
4610:
4605:
4593:
4591:
4590:
4585:
4580:
4575:
4563:
4561:
4560:
4555:
4537:
4535:
4534:
4529:
4511:
4509:
4508:
4503:
4498:
4493:
4477:
4475:
4474:
4469:
4464:
4459:
4444:
4442:
4441:
4436:
4431:
4430:
4412:
4411:
4386:
4384:
4383:
4378:
4373:
4372:
4354:
4353:
4328:
4326:
4325:
4320:
4318:
4313:
4305:
4304:
4286:
4281:
4269:
4267:
4266:
4261:
4259:
4258:
4242:
4240:
4239:
4234:
4232:
4231:
4215:
4213:
4212:
4207:
4202:
4201:
4180:
4179:
4158:
4157:
4142:
4141:
4125:
4123:
4122:
4117:
4112:
4107:
4096:
4095:
4076:
4074:
4073:
4068:
4066:
4061:
4056:
4055:
4039:
4037:
4036:
4031:
4029:
4028:
4010:
4009:
3993:
3991:
3990:
3985:
3967:
3965:
3964:
3959:
3957:
3952:
3947:
3946:
3927:
3925:
3924:
3919:
3914:
3909:
3895:
3893:
3892:
3887:
3882:
3878:
3877:
3873:
3872:
3870:
3869:
3857:
3852:
3851:
3836:
3828:
3818:
3814:
3813:
3809:
3808:
3804:
3802:
3801:
3789:
3780:
3779:
3764:
3756:
3740:
3738:
3737:
3732:
3727:
3719:
3718:
3699:
3698:
3672:
3668:
3667:
3663:
3662:
3658:
3656:
3655:
3643:
3634:
3633:
3618:
3610:
3600:
3599:
3565:
3563:
3562:
3557:
3552:
3547:
3527:
3525:
3524:
3519:
3491:
3489:
3488:
3483:
3481:
3480:
3464:
3462:
3461:
3456:
3451:
3450:
3431:
3429:
3428:
3423:
3407:
3405:
3404:
3399:
3397:
3392:
3374:rational numbers
3368:
3366:
3365:
3360:
3355:
3350:
3339:
3338:
3313:
3311:
3310:
3305:
3297:
3292:
3291:
3279:
3278:
3263:
3251:
3249:
3248:
3243:
3217:
3215:
3214:
3209:
3191:
3189:
3188:
3183:
3181:
3176:
3161:
3159:
3158:
3153:
3148:
3147:
3123:
3121:
3120:
3115:
3107:
3106:
3080:
3076:
3075:
3073:
3072:
3060:
3055:
3054:
3039:
3031:
3026:
3025:
3003:
3001:
3000:
2995:
2981:
2980:
2956:
2954:
2953:
2948:
2924:
2922:
2921:
2916:
2914:
2909:
2892:
2888:
2886:
2885:
2880:
2866:
2864:
2863:
2858:
2856:
2741:
2590:
2442:
2431:
2429:
2428:
2425:{\displaystyle }
2423:
2399:
2397:
2396:
2391:
2359:
2356:
2353:
2350:
2347:
2344:
2341:
2338:
2335:
2332:
2329:
2326:
2323:
2320:
2317:
2314:
2311:
2308:
2305:
2302:
2299:
2296:
2293:
2290:
2287:
2284:
2281:
2278:
2275:
2272:
2269:
2266:
2263:
2260:
2257:
2254:
2251:
2248:
2245:
2242:
2239:
2236:
2233:
2230:
2227:
2224:
2221:
2218:
2215:
2212:
2209:
2206:
2203:
2200:
2197:
2194:
2191:
2188:
2185:
2182:
2179:
2176:
2173:
2170:
2167:
2164:
2161:
2158:
2155:
2141:
2139:
2138:
2133:
2125:
2124:
2108:
2106:
2105:
2100:
2077:
2074:
2071:
2068:
2065:
2062:
2059:
2056:
2053:
2050:
2047:
2044:
2041:
2038:
2035:
2032:
2029:
2026:
2023:
2020:
2017:
2014:
2011:
2008:
2005:
2002:
1999:
1996:
1993:
1990:
1987:
1984:
1981:
1978:
1975:
1972:
1969:
1966:
1963:
1960:
1957:
1954:
1951:
1948:
1945:
1942:
1939:
1936:
1933:
1930:
1927:
1924:
1921:
1918:
1915:
1912:
1909:
1906:
1903:
1900:
1894:
1892:
1891:
1886:
1880:
1875:
1851:
1850:
1823:
1822:
1810:
1809:
1771:
1768:
1765:
1762:
1759:
1756:
1753:
1750:
1747:
1744:
1741:
1738:
1735:
1732:
1729:
1726:
1723:
1720:
1717:
1714:
1711:
1708:
1705:
1702:
1699:
1696:
1693:
1690:
1687:
1684:
1681:
1678:
1675:
1672:
1669:
1666:
1657:
1654:
1651:
1648:
1645:
1642:
1639:
1636:
1633:
1630:
1627:
1624:
1621:
1618:
1615:
1612:
1609:
1606:
1603:
1600:
1597:
1594:
1591:
1588:
1585:
1582:
1579:
1576:
1573:
1570:
1567:
1564:
1561:
1558:
1555:
1552:
1549:
1546:
1543:
1540:
1537:
1534:
1531:
1514:
1512:
1511:
1506:
1498:
1497:
1488:
1485:
1477:
1476:
1460:
1458:
1457:
1452:
1441:
1436:
1404:
1402:
1401:
1396:
1394:
1380:
1379:
1349:
1348:
1327:
1322:
1310:
1308:
1307:
1302:
1280:Basic algorithms
1274:
1268:
1261:
1258:
1255:
1252:
1249:
1246:
1243:
1240:
1237:
1234:
1231:
1228:
1225:
1222:
1219:
1216:
1213:
1210:
1207:
1204:
1201:
1198:
1195:
1192:
1189:
1186:
1183:
1180:
1177:
1174:
1171:
1168:
1165:
1162:
1159:
1156:
1153:
1150:
1147:
1144:
1141:
1138:
1135:
1132:
1129:
1126:
1123:
1120:
1117:
1114:
1111:
1108:
1105:
1102:
1095:
1093:
1092:
1087:
1085:
1080:
1071:
1069:
1068:
1063:
1036:
1034:
1033:
1028:
1005:) the procedure
1004:
1002:
1001:
996:
981:
979:
978:
973:
961:
959:
958:
953:
941:
939:
938:
933:
909:
907:
906:
901:
899:
894:
883:decimal digits.
882:
878:
876:
875:
870:
868:
867:
849:
847:
846:
841:
833:
828:
817:
815:
814:
809:
807:
797:
784:
779:
768:
766:
765:
750:
732:
722:
709:
704:
693:
691:
690:
675:
657:
644:
639:
628:
626:
625:
610:
592:
579:
574:
563:
561:
560:
545:
527:
514:
509:
498:
496:
495:
480:
462:
451:
449:
448:
443:
419:
417:
416:
411:
406:
404:
403:
388:
376:
374:
373:
368:
353:
351:
350:
345:
333:
331:
330:
325:
323:
318:
306:
304:
303:
298:
293:
288:
269:
267:
266:
261:
246:
244:
243:
238:
236:
231:
215:
213:
212:
207:
195:
193:
192:
187:
168:
166:
165:
160:
137:
132:
100:
98:
97:
92:
84:
79:
49:
37:
33:
7921:
7920:
7916:
7915:
7914:
7912:
7911:
7910:
7886:
7885:
7884:
7879:
7865:
7800:
7762:
7729:
7686:
7630:
7587:
7491:
7453:
7426:Proth's theorem
7368:Primality tests
7362:
7354:
7324:
7316:
7302:
7282:
7267:
7262:
7258:
7253:
7252:
7239:
7238:
7234:
7221:
7220:
7216:
7203:
7202:
7198:
7185:
7184:
7180:
7167:
7166:
7162:
7149:
7148:
7144:
7131:
7130:
7126:
7113:
7112:
7108:
7095:
7094:
7090:
7077:
7076:
7072:
7059:
7058:
7054:
7046:
7035:
7030:
7029:
7025:
7011:
7010:
7006:
7001:
6996:
6995:
6988:
6986:
6982:
6972:
6970:
6966:
6959:
6955:
6950:
6938:
6924:
6909:
6894:
6880:Integer.sqrt(n)
6879:
6864:
6863:
6860:
6845:
6830:
6815:
6800:
6785:
6770:
6769:
6766:
6738:
6733:
6732:
6729:
6726:
6723:
6720:
6717:
6714:
6711:
6708:
6705:
6702:
6699:
6696:
6693:
6690:
6687:
6684:
6681:
6678:
6675:
6672:
6669:
6666:
6663:
6660:
6657:
6654:
6651:
6648:
6645:
6642:
6639:
6636:
6633:
6630:
6627:
6624:
6621:
6618:
6615:
6612:
6609:
6606:
6603:
6600:
6598:overflowing_sub
6597:
6594:
6591:
6588:
6585:
6582:
6579:
6576:
6573:
6570:
6567:
6564:
6561:
6558:
6555:
6552:
6549:
6546:
6543:
6540:
6537:
6534:
6531:
6528:
6525:
6522:
6519:
6516:
6513:
6510:
6507:
6504:
6501:
6498:
6495:
6492:
6489:
6486:
6483:
6480:
6477:
6474:
6471:
6468:
6465:
6462:
6459:
6456:
6453:
6450:
6447:
6444:
6441:
6438:
6435:
6432:
6429:
6426:
6423:
6420:
6417:
6414:
6411:
6408:
6405:
6402:
6399:
6396:
6393:
6390:
6387:
6384:
6381:
6378:
6375:
6372:
6369:
6366:
6363:
6360:
6357:
6354:
6351:
6348:
6345:
6342:
6339:
6336:
6333:
6330:
6327:
6324:
6321:
6318:
6315:
6312:
6309:
6306:
6303:
6300:
6297:
6294:
6291:
6288:
6285:
6282:
6279:
6276:
6273:
6270:
6267:
6264:
6261:
6258:
6255:
6252:
6249:
6246:
6243:
6240:
6237:
6234:
6231:
6228:
6225:
6222:
6219:
6216:
6213:
6210:
6206:
6203:
6200:
6197:
6194:
6191:
6188:
6185:
6182:
6179:
6176:
6173:
6170:
6167:
6164:
6161:
6158:
6155:
6152:
6149:
6146:
6143:
6140:
6137:
6134:
6131:
6128:
6125:
6122:
6119:
6116:
6113:
6110:
6107:
6104:
6101:
6098:
6095:
6092:
6089:
6086:
6083:
6080:
6077:
6074:
6071:
6068:
6065:
6062:
6059:
6056:
6053:
6050:
6047:
6044:
6041:
6037:
6034:
6031:
6028:
6025:
6022:
6019:
6016:
6013:
6010:
6007:
6004:
6001:
5998:
5994:
5991:
5988:
5985:
5982:
5979:
5975:
5972:
5969:
5965:
5962:
5959:
5956:
5953:
5950:
5946:
5943:
5940:
5936:
5933:
5930:
5927:
5924:
5921:
5918:
5915:
5911:
5908:
5904:
5901:
5898:
5895:
5892:
5889:
5865:
5848:
5847:
5828:
5827:
5808:
5807:
5788:
5787:
5783:
5761:
5748:
5747:
5744:
5741:
5738:
5735:
5732:
5729:
5726:
5723:
5720:
5717:
5714:
5711:
5708:
5705:
5702:
5699:
5696:
5693:
5690:
5687:
5684:
5681:
5678:
5675:
5672:
5669:
5666:
5663:
5660:
5657:
5654:
5651:
5648:
5645:
5642:
5639:
5636:
5633:
5630:
5627:
5624:
5621:
5618:
5615:
5612:
5609:
5606:
5603:
5600:
5597:
5594:
5591:
5588:
5585:
5582:
5579:
5576:
5573:
5570:
5567:
5564:
5561:
5558:
5555:
5552:
5549:
5546:
5543:
5540:
5537:
5534:
5531:
5528:
5525:
5522:
5519:
5516:
5513:
5510:
5508:# equivalently:
5507:
5504:
5501:
5498:
5495:
5492:
5489:
5486:
5483:
5480:
5477:
5474:
5471:
5468:
5465:
5462:
5459:
5456:
5453:
5450:
5447:
5444:
5441:
5438:
5435:
5432:
5429:
5426:
5423:
5420:
5417:
5414:
5411:
5408:
5405:
5402:
5399:
5396:
5393:
5390:
5387:
5384:
5381:
5378:
5375:
5372:
5369:
5366:
5363:
5360:
5357:
5354:
5351:
5336:
5332:
5328:
5321:
5294:
5293:
5270:
5269:
5262:
5214:
5213:
5186:
5173:
5168:
5167:
5131:
5123:
5122:
5118:
5095:
5094:
5038:
5027:
5014:
5009:
5008:
5000:
4974:
4973:
4931:
4930:
4875:
4874:
4870:
4867:
4862:
4861:
4858:
4855:
4852:
4849:
4846:
4843:
4840:
4837:
4834:
4831:
4828:
4825:
4822:
4819:
4816:
4813:
4810:
4807:
4804:
4801:
4798:
4795:
4792:
4789:
4786:
4783:
4780:
4777:
4774:
4771:
4768:
4765:
4762:
4759:
4756:
4753:
4750:
4747:
4744:
4741:
4738:
4735:
4732:
4729:
4726:
4723:
4720:
4717:
4714:
4711:
4708:
4705:
4702:
4699:
4696:
4693:
4690:
4687:
4684:
4681:
4678:
4675:
4672:
4669:
4666:
4663:
4660:
4657:
4654:
4651:
4648:
4645:
4642:
4639:
4636:
4596:
4595:
4566:
4565:
4540:
4539:
4514:
4513:
4484:
4483:
4450:
4449:
4422:
4397:
4389:
4388:
4364:
4339:
4331:
4330:
4296:
4272:
4271:
4250:
4245:
4244:
4223:
4218:
4217:
4187:
4165:
4149:
4133:
4128:
4127:
4087:
4079:
4078:
4047:
4042:
4041:
4014:
4001:
3996:
3995:
3970:
3969:
3938:
3933:
3932:
3900:
3899:
3861:
3843:
3842:
3838:
3826:
3822:
3793:
3784:
3771:
3770:
3766:
3754:
3750:
3745:
3744:
3710:
3690:
3647:
3638:
3625:
3624:
3620:
3608:
3604:
3585:
3580:
3579:
3538:
3537:
3534:
3498:
3497:
3472:
3467:
3466:
3442:
3434:
3433:
3432:, the sequence
3414:
3413:
3386:
3385:
3382:
3324:
3316:
3315:
3283:
3264:
3254:
3253:
3228:
3227:
3224:
3194:
3193:
3170:
3169:
3139:
3131:
3130:
3098:
3064:
3046:
3045:
3041:
3011:
3006:
3005:
2972:
2967:
2966:
2963:Newton's method
2927:
2926:
2903:
2902:
2899:
2890:
2871:
2870:
2854:
2853:
2739:
2738:
2588:
2587:
2434:
2433:
2402:
2401:
2370:
2369:
2361:
2360:
2357:
2354:
2351:
2348:
2345:
2342:
2339:
2336:
2333:
2330:
2327:
2324:
2321:
2318:
2315:
2312:
2309:
2306:
2303:
2300:
2297:
2294:
2291:
2288:
2285:
2282:
2279:
2276:
2273:
2270:
2267:
2264:
2261:
2258:
2255:
2252:
2249:
2246:
2243:
2240:
2237:
2234:
2231:
2228:
2225:
2222:
2219:
2216:
2213:
2210:
2207:
2204:
2201:
2198:
2195:
2192:
2189:
2186:
2183:
2180:
2177:
2174:
2171:
2168:
2165:
2162:
2159:
2156:
2153:
2116:
2111:
2110:
2091:
2090:
2084:
2079:
2078:
2075:
2072:
2069:
2066:
2063:
2060:
2057:
2054:
2051:
2048:
2045:
2042:
2039:
2036:
2033:
2030:
2027:
2024:
2021:
2018:
2015:
2012:
2009:
2006:
2003:
2000:
1997:
1994:
1991:
1988:
1985:
1982:
1979:
1976:
1973:
1970:
1967:
1964:
1961:
1958:
1955:
1952:
1949:
1946:
1943:
1940:
1937:
1934:
1931:
1928:
1925:
1922:
1919:
1916:
1913:
1910:
1907:
1904:
1901:
1898:
1842:
1814:
1801:
1784:
1783:
1780:
1775:
1774:
1773:
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:
1660:
1659:
1658:
1655:
1652:
1649:
1646:
1643:
1640:
1637:
1634:
1631:
1628:
1625:
1622:
1619:
1616:
1613:
1610:
1607:
1604:
1601:
1598:
1595:
1592:
1589:
1586:
1583:
1580:
1577:
1574:
1571:
1568:
1565:
1562:
1559:
1556:
1553:
1550:
1547:
1544:
1541:
1538:
1535:
1532:
1529:
1521:
1489:
1486: and
1468:
1463:
1462:
1409:
1408:
1371:
1340:
1313:
1312:
1293:
1292:
1282:
1263:
1262:
1259:
1256:
1253:
1250:
1247:
1244:
1241:
1238:
1235:
1232:
1229:
1226:
1223:
1220:
1217:
1214:
1211:
1208:
1205:
1202:
1199:
1196:
1193:
1190:
1187:
1184:
1181:
1178:
1175:
1172:
1169:
1166:
1163:
1160:
1158:"%d."
1157:
1154:
1151:
1148:
1145:
1142:
1139:
1136:
1133:
1130:
1127:
1124:
1121:
1118:
1115:
1112:
1109:
1106:
1103:
1100:
1074:
1073:
1042:
1041:
1007:
1006:
987:
986:
964:
963:
944:
943:
912:
911:
888:
887:
880:
859:
854:
853:
822:
821:
805:
804:
795:
794:
757:
730:
729:
720:
719:
682:
655:
654:
617:
590:
589:
552:
525:
524:
487:
454:
453:
428:
427:
395:
379:
378:
359:
358:
336:
335:
312:
311:
279:
278:
270:which is not a
252:
251:
225:
224:
198:
197:
178:
177:
174:
105:
104:
52:
51:
47:
35:
31:
17:
12:
11:
5:
7919:
7917:
7909:
7908:
7903:
7898:
7888:
7887:
7881:
7880:
7878:
7877:
7870:
7867:
7866:
7864:
7863:
7858:
7853:
7848:
7843:
7829:
7824:
7819:
7814:
7808:
7806:
7802:
7801:
7799:
7798:
7793:
7788:
7786:TonelliâShanks
7783:
7778:
7772:
7770:
7764:
7763:
7761:
7760:
7755:
7750:
7745:
7739:
7737:
7731:
7730:
7728:
7727:
7722:
7720:Index calculus
7717:
7715:PohligâHellman
7712:
7707:
7702:
7696:
7694:
7688:
7687:
7685:
7684:
7679:
7674:
7669:
7667:Newton-Raphson
7664:
7659:
7654:
7649:
7643:
7641:
7632:
7631:
7629:
7628:
7623:
7618:
7613:
7608:
7603:
7597:
7595:
7593:Multiplication
7589:
7588:
7586:
7585:
7580:
7578:Trial division
7575:
7570:
7565:
7563:Rational sieve
7560:
7553:
7548:
7543:
7535:
7527:
7522:
7517:
7512:
7507:
7501:
7499:
7493:
7492:
7490:
7489:
7484:
7479:
7474:
7469:
7467:Sieve of Atkin
7463:
7461:
7455:
7454:
7452:
7451:
7446:
7441:
7436:
7429:
7422:
7415:
7408:
7403:
7398:
7393:
7391:Elliptic curve
7388:
7383:
7378:
7372:
7370:
7364:
7363:
7355:
7353:
7352:
7345:
7338:
7330:
7323:
7322:
7314:
7300:
7284:Minsky, Marvin
7280:
7259:
7257:
7256:External links
7254:
7251:
7250:
7232:
7214:
7196:
7178:
7160:
7142:
7124:
7106:
7088:
7070:
7052:
7049:on 2023-05-11.
7023:
7020:on 2012-03-06.
7003:
7002:
7000:
6997:
6994:
6993:
6980:
6964:
6952:
6951:
6949:
6946:
6945:
6944:
6937:
6934:
6931:
6930:
6927:
6922:
6916:
6915:
6912:
6907:
6901:
6900:
6897:
6892:
6886:
6885:
6882:
6877:
6871:
6870:
6867:
6858:
6852:
6851:
6848:
6843:
6837:
6836:
6833:
6828:
6822:
6821:
6818:
6813:
6807:
6806:
6803:
6798:
6792:
6791:
6788:
6783:
6777:
6776:
6773:
6764:
6758:
6757:
6754:
6751:
6737:
6734:
5888:
5872:
5868:
5864:
5861:
5858:
5855:
5835:
5815:
5795:
5760:
5757:
5350:
5345:natural number
5323:If working in
5320:
5317:
5304:
5301:
5279:
5261:
5258:
5245:
5242:
5239:
5236:
5233:
5230:
5227:
5224:
5221:
5201:
5198:
5193:
5189:
5185:
5180:
5176:
5155:
5152:
5149:
5146:
5143:
5138:
5134:
5130:
5104:
5078:
5073:
5070:
5067:
5064:
5060:
5056:
5053:
5050:
5045:
5041:
5037:
5034:
5030:
5026:
5021:
5017:
5001:std::bit_width
4972:
4969:
4966:
4963:
4960:
4957:
4954:
4951:
4948:
4945:
4942:
4939:
4936:
4934:
4932:
4929:
4926:
4923:
4920:
4917:
4914:
4911:
4908:
4905:
4902:
4899:
4896:
4893:
4890:
4887:
4884:
4882:
4866:
4863:
4793:// Bound check
4638:
4635:
4632:
4619:
4616:
4613:
4608:
4603:
4583:
4578:
4573:
4553:
4550:
4547:
4527:
4524:
4521:
4501:
4496:
4491:
4467:
4462:
4457:
4434:
4429:
4425:
4421:
4418:
4415:
4410:
4407:
4404:
4400:
4396:
4376:
4371:
4367:
4363:
4360:
4357:
4352:
4349:
4346:
4342:
4338:
4316:
4311:
4308:
4303:
4299:
4295:
4292:
4289:
4284:
4279:
4257:
4253:
4230:
4226:
4205:
4200:
4197:
4194:
4190:
4186:
4183:
4178:
4175:
4172:
4168:
4164:
4161:
4156:
4152:
4148:
4145:
4140:
4136:
4115:
4110:
4105:
4102:
4099:
4094:
4090:
4086:
4064:
4059:
4054:
4050:
4027:
4024:
4021:
4017:
4013:
4008:
4004:
3983:
3980:
3977:
3955:
3950:
3945:
3941:
3917:
3912:
3907:
3885:
3881:
3876:
3868:
3864:
3860:
3855:
3850:
3846:
3841:
3834:
3831:
3825:
3821:
3817:
3812:
3807:
3800:
3796:
3792:
3787:
3783:
3778:
3774:
3769:
3762:
3759:
3753:
3730:
3726:
3722:
3717:
3713:
3708:
3705:
3702:
3697:
3693:
3688:
3685:
3682:
3679:
3675:
3671:
3666:
3661:
3654:
3650:
3646:
3641:
3637:
3632:
3628:
3623:
3616:
3613:
3607:
3603:
3598:
3595:
3592:
3588:
3576:floating point
3555:
3550:
3545:
3536:For computing
3533:
3530:
3517:
3514:
3511:
3508:
3505:
3479:
3475:
3454:
3449:
3445:
3441:
3421:
3395:
3381:
3378:
3358:
3353:
3348:
3345:
3342:
3337:
3334:
3331:
3327:
3323:
3303:
3300:
3296:
3290:
3286:
3282:
3277:
3274:
3271:
3267:
3262:
3241:
3238:
3235:
3223:
3220:
3207:
3204:
3201:
3179:
3151:
3146:
3142:
3138:
3113:
3110:
3105:
3101:
3096:
3093:
3090:
3087:
3083:
3079:
3071:
3067:
3063:
3058:
3053:
3049:
3044:
3037:
3034:
3029:
3024:
3021:
3018:
3014:
2993:
2990:
2987:
2984:
2979:
2975:
2959:Heron's method
2946:
2943:
2940:
2937:
2934:
2912:
2898:
2895:
2878:
2852:
2849:
2846:
2843:
2840:
2837:
2834:
2831:
2828:
2825:
2822:
2819:
2816:
2813:
2810:
2807:
2804:
2801:
2798:
2795:
2792:
2789:
2786:
2783:
2780:
2777:
2774:
2771:
2768:
2765:
2762:
2759:
2756:
2753:
2750:
2747:
2744:
2742:
2740:
2737:
2734:
2731:
2728:
2725:
2722:
2719:
2716:
2713:
2710:
2707:
2704:
2701:
2698:
2695:
2692:
2689:
2686:
2683:
2680:
2677:
2674:
2671:
2668:
2665:
2662:
2659:
2656:
2653:
2650:
2647:
2644:
2641:
2638:
2635:
2632:
2629:
2626:
2623:
2620:
2617:
2614:
2611:
2608:
2605:
2602:
2599:
2596:
2593:
2591:
2589:
2586:
2583:
2580:
2577:
2574:
2571:
2568:
2565:
2562:
2559:
2556:
2553:
2550:
2547:
2544:
2541:
2538:
2535:
2532:
2529:
2526:
2523:
2520:
2517:
2514:
2511:
2508:
2505:
2502:
2499:
2496:
2493:
2490:
2487:
2484:
2481:
2478:
2475:
2472:
2469:
2466:
2463:
2460:
2457:
2454:
2451:
2448:
2445:
2443:
2441:
2421:
2418:
2415:
2412:
2409:
2389:
2386:
2383:
2380:
2377:
2152:
2131:
2128:
2123:
2119:
2098:
2083:
2080:
2025:// (a + 1) ^ 2
1897:
1884:
1879:
1874:
1871:
1868:
1864:
1860:
1857:
1854:
1849:
1845:
1841:
1838:
1835:
1832:
1829:
1826:
1821:
1817:
1813:
1808:
1804:
1800:
1797:
1794:
1791:
1779:
1776:
1663:
1661:
1528:
1526:
1525:
1520:
1517:
1504:
1501:
1496:
1492:
1483:
1480:
1475:
1471:
1450:
1447:
1444:
1439:
1434:
1431:
1428:
1425:
1422:
1419:
1416:
1393:
1389:
1386:
1383:
1378:
1374:
1370:
1367:
1364:
1361:
1358:
1355:
1352:
1347:
1343:
1339:
1336:
1333:
1330:
1325:
1320:
1300:
1281:
1278:
1236:"%d"
1099:
1083:
1061:
1058:
1055:
1052:
1049:
1026:
1023:
1020:
1017:
1014:
994:
982:at each pass.
971:
951:
931:
928:
925:
922:
919:
897:
866:
862:
839:
836:
831:
803:
800:
798:
796:
793:
790:
787:
782:
777:
774:
771:
764:
760:
756:
753:
748:
745:
742:
739:
736:
733:
731:
728:
725:
723:
721:
718:
715:
712:
707:
702:
699:
696:
689:
685:
681:
678:
673:
670:
667:
664:
661:
658:
656:
653:
650:
647:
642:
637:
634:
631:
624:
620:
616:
613:
608:
605:
602:
599:
596:
593:
591:
588:
585:
582:
577:
572:
569:
566:
559:
555:
551:
548:
543:
540:
537:
534:
531:
528:
526:
523:
520:
517:
512:
507:
504:
501:
494:
490:
486:
483:
478:
475:
472:
469:
466:
463:
461:
441:
438:
435:
409:
402:
398:
394:
391:
386:
366:
343:
321:
296:
291:
286:
272:perfect square
259:
250:on each input
234:
205:
185:
173:
170:
158:
155:
152:
149:
146:
143:
140:
135:
130:
127:
124:
121:
118:
115:
112:
90:
87:
82:
77:
74:
71:
68:
65:
62:
59:
15:
13:
10:
9:
6:
4:
3:
2:
7918:
7907:
7904:
7902:
7901:Number theory
7899:
7897:
7894:
7893:
7891:
7875:
7872:
7871:
7868:
7862:
7859:
7857:
7854:
7852:
7849:
7847:
7844:
7841:
7837:
7833:
7830:
7828:
7825:
7823:
7820:
7818:
7815:
7813:
7810:
7809:
7807:
7803:
7797:
7794:
7792:
7789:
7787:
7784:
7782:
7781:Pocklington's
7779:
7777:
7774:
7773:
7771:
7769:
7765:
7759:
7756:
7754:
7751:
7749:
7746:
7744:
7741:
7740:
7738:
7736:
7732:
7726:
7723:
7721:
7718:
7716:
7713:
7711:
7708:
7706:
7703:
7701:
7698:
7697:
7695:
7693:
7689:
7683:
7680:
7678:
7675:
7673:
7670:
7668:
7665:
7663:
7660:
7658:
7655:
7653:
7650:
7648:
7645:
7644:
7642:
7640:
7637:
7633:
7627:
7624:
7622:
7619:
7617:
7614:
7612:
7609:
7607:
7604:
7602:
7599:
7598:
7596:
7594:
7590:
7584:
7581:
7579:
7576:
7574:
7571:
7569:
7566:
7564:
7561:
7559:
7558:
7554:
7552:
7549:
7547:
7544:
7542:
7540:
7536:
7534:
7532:
7528:
7526:
7525:Pollard's rho
7523:
7521:
7518:
7516:
7513:
7511:
7508:
7506:
7503:
7502:
7500:
7498:
7494:
7488:
7485:
7483:
7480:
7478:
7475:
7473:
7470:
7468:
7465:
7464:
7462:
7460:
7456:
7450:
7447:
7445:
7442:
7440:
7437:
7435:
7434:
7430:
7428:
7427:
7423:
7421:
7420:
7416:
7414:
7413:
7409:
7407:
7404:
7402:
7399:
7397:
7394:
7392:
7389:
7387:
7384:
7382:
7379:
7377:
7374:
7373:
7371:
7369:
7365:
7361:
7358:
7351:
7346:
7344:
7339:
7337:
7332:
7331:
7328:
7319:
7315:
7311:
7307:
7303:
7301:0-13-165563-9
7297:
7292:
7291:
7285:
7281:
7277:
7273:
7266:
7261:
7260:
7255:
7246:
7242:
7236:
7233:
7228:
7224:
7218:
7215:
7210:
7206:
7200:
7197:
7192:
7188:
7182:
7179:
7174:
7170:
7164:
7161:
7156:
7152:
7146:
7143:
7138:
7134:
7128:
7125:
7120:
7116:
7110:
7107:
7102:
7098:
7092:
7089:
7084:
7080:
7074:
7071:
7066:
7062:
7056:
7053:
7045:
7041:
7034:
7027:
7024:
7019:
7015:
7008:
7005:
6998:
6984:
6981:
6978:
6977:Jarvis (2006)
6968:
6965:
6962:
6957:
6954:
6947:
6943:
6940:
6939:
6935:
6928:
6923:
6921:
6918:
6917:
6913:
6908:
6906:
6903:
6902:
6898:
6893:
6891:
6888:
6887:
6883:
6878:
6876:
6873:
6872:
6868:
6859:
6857:
6854:
6853:
6849:
6846:math.isqrt(n)
6844:
6842:
6839:
6838:
6834:
6829:
6827:
6824:
6823:
6819:
6814:
6812:
6809:
6808:
6804:
6801:Math.isqrt(n)
6799:
6797:
6794:
6793:
6789:
6784:
6782:
6779:
6778:
6774:
6765:
6763:
6760:
6759:
6755:
6752:
6749:
6748:
6745:
6743:
6735:
6241:leading_zeros
5886:
5870:
5866:
5862:
5859:
5856:
5853:
5833:
5813:
5793:
5780:
5776:
5774:
5770:
5766:
5758:
5756:
5754:
5348:
5346:
5342:
5326:
5318:
5316:
5302:
5299:
5277:
5267:
5259:
5257:
5243:
5237:
5231:
5225:
5219:
5199:
5196:
5191:
5187:
5183:
5178:
5174:
5153:
5150:
5144:
5141:
5136:
5132:
5102:
5092:
5076:
5071:
5068:
5062:
5058:
5051:
5048:
5043:
5039:
5028:
5024:
5019:
5015:
5006:
4998:
4994:
4989:
4970:
4964:
4958:
4952:
4946:
4940:
4935:
4927:
4921:
4915:
4909:
4903:
4897:
4891:
4885:
4864:
4633:
4631:
4617:
4614:
4606:
4576:
4551:
4548:
4545:
4525:
4522:
4519:
4494:
4481:
4460:
4446:
4427:
4423:
4416:
4408:
4405:
4402:
4398:
4369:
4365:
4358:
4350:
4347:
4344:
4340:
4314:
4309:
4301:
4297:
4290:
4282:
4255:
4251:
4228:
4224:
4198:
4195:
4192:
4188:
4181:
4176:
4173:
4170:
4166:
4162:
4154:
4150:
4143:
4138:
4134:
4108:
4100:
4092:
4088:
4062:
4057:
4052:
4048:
4025:
4022:
4019:
4015:
4011:
4006:
4002:
3981:
3978:
3975:
3953:
3948:
3943:
3939:
3929:
3910:
3896:
3883:
3879:
3874:
3866:
3862:
3858:
3853:
3848:
3844:
3839:
3832:
3829:
3823:
3819:
3815:
3810:
3805:
3798:
3794:
3790:
3785:
3781:
3776:
3772:
3767:
3760:
3757:
3751:
3741:
3728:
3720:
3715:
3711:
3706:
3703:
3700:
3695:
3691:
3686:
3683:
3680:
3677:
3673:
3669:
3664:
3659:
3652:
3648:
3644:
3639:
3635:
3630:
3626:
3621:
3614:
3611:
3605:
3601:
3596:
3593:
3590:
3586:
3577:
3573:
3569:
3548:
3531:
3529:
3512:
3506:
3503:
3495:
3477:
3473:
3447:
3443:
3419:
3411:
3393:
3379:
3377:
3375:
3370:
3351:
3343:
3335:
3332:
3329:
3325:
3301:
3298:
3288:
3284:
3280:
3275:
3272:
3269:
3265:
3239:
3236:
3233:
3221:
3219:
3199:
3177:
3167:
3166:quadratically
3164:
3144:
3140:
3129:
3124:
3111:
3108:
3103:
3099:
3094:
3091:
3088:
3085:
3081:
3077:
3069:
3065:
3061:
3056:
3051:
3047:
3042:
3035:
3032:
3027:
3022:
3019:
3016:
3012:
2991:
2988:
2985:
2982:
2977:
2973:
2964:
2960:
2941:
2935:
2932:
2910:
2894:
2876:
2867:
2847:
2844:
2841:
2829:
2826:
2823:
2811:
2808:
2805:
2793:
2790:
2787:
2775:
2772:
2769:
2757:
2754:
2751:
2743:
2732:
2729:
2726:
2714:
2711:
2708:
2696:
2693:
2690:
2678:
2675:
2672:
2660:
2657:
2654:
2642:
2639:
2636:
2624:
2621:
2618:
2606:
2603:
2600:
2592:
2581:
2578:
2575:
2563:
2560:
2557:
2545:
2542:
2539:
2527:
2524:
2521:
2509:
2506:
2503:
2491:
2488:
2485:
2473:
2470:
2467:
2455:
2452:
2449:
2444:
2416:
2413:
2410:
2384:
2378:
2375:
2366:
2365:
2150:
2148:
2147:binary search
2143:
2129:
2126:
2121:
2117:
2096:
2088:
2087:Linear search
2081:
1895:
1882:
1877:
1872:
1869:
1866:
1862:
1858:
1855:
1852:
1847:
1843:
1839:
1836:
1833:
1830:
1827:
1824:
1819:
1815:
1811:
1806:
1798:
1795:
1792:
1777:
1524:
1518:
1516:
1502:
1499:
1494:
1490:
1481:
1478:
1473:
1469:
1448:
1445:
1437:
1429:
1423:
1417:
1414:
1407:For example,
1405:
1387:
1384:
1381:
1376:
1368:
1365:
1362:
1356:
1353:
1350:
1345:
1341:
1337:
1334:
1331:
1323:
1298:
1291:
1287:
1279:
1277:
1275:
1097:
1081:
1056:
1050:
1047:
1038:
1021:
1015:
1012:
992:
983:
969:
949:
926:
920:
917:
895:
884:
864:
860:
850:
837:
834:
829:
818:
801:
799:
791:
788:
780:
772:
762:
758:
754:
751:
743:
740:
737:
734:
726:
724:
716:
713:
705:
697:
687:
683:
679:
676:
668:
665:
662:
659:
651:
648:
640:
632:
622:
618:
614:
611:
603:
600:
597:
594:
586:
583:
575:
567:
557:
553:
549:
546:
538:
535:
532:
529:
521:
518:
510:
502:
492:
488:
484:
481:
473:
470:
467:
464:
439:
436:
433:
425:
421:
400:
396:
392:
389:
364:
355:
341:
319:
309:
289:
275:
273:
257:
249:
232:
222:
217:
203:
183:
171:
169:
156:
153:
147:
141:
133:
125:
119:
113:
110:
103:For example,
101:
88:
80:
72:
66:
60:
57:
45:
41:
38:which is the
30:
27:(isqrt) of a
26:
22:
21:number theory
7873:
7826:
7555:
7538:
7530:
7449:MillerâRabin
7431:
7424:
7417:
7412:LucasâLehmer
7410:
7289:
7275:
7271:
7244:
7235:
7226:
7217:
7208:
7199:
7190:
7181:
7172:
7163:
7154:
7145:
7136:
7127:
7118:
7109:
7100:
7091:
7082:
7073:
7064:
7055:
7044:the original
7026:
7018:the original
7007:
6983:
6967:
6956:
6739:
6637:wrapping_add
6583:QUARTER_BITS
6556:QUARTER_BITS
6502:QUARTER_BITS
6400:QUARTER_BITS
6382:QUARTER_BITS
5966:QUARTER_BITS
5781:
5777:
5765:big-integers
5762:
5749:
5430:integer_sqrt
5355:integer_sqrt
5322:
5263:
5093:bigger than
5091:power of two
4990:
4868:
4447:
3930:
3897:
3742:
3567:
3535:
3383:
3371:
3225:
3125:
2900:
2868:
2367:
2363:
2362:
2144:
2085:
1781:
1522:
1406:
1285:
1283:
1264:
1039:
984:
962:by a factor
885:
851:
819:
423:
422:
377:and compute
356:
307:
276:
247:
218:
175:
102:
24:
18:
7705:Pollard rho
7662:Goldschmidt
7396:Pocklington
7386:BaillieâPSW
6781:Common Lisp
6753:Example use
6475:denominator
6454:denominator
6409:denominator
4995:or for the
4480:fixed point
1107:sqrtForever
1048:sqrtForever
993:sqrtForever
424:For example
357:Choose any
248:run forever
44:square root
7890:Categories
7817:Cornacchia
7812:Chakravala
7360:algorithms
7310:0131655639
7278:: 119â122.
6999:References
6925:isqrt($ n)
5775:are used.
5730:large_cand
5706:large_cand
5700:large_cand
5673:large_cand
5505:large_cand
5493:small_cand
5478:large_cand
5472:large_cand
5460:small_cand
5454:large_cand
5424:small_cand
4997:bit-length
4270:, one has
3410:irrational
2957:is to use
7791:Berlekamp
7748:Euclidean
7636:Euclidean
7616:ToomâCook
7611:Karatsuba
6786:(isqrt n)
6469:numerator
6448:numerator
6358:numerator
6286:HALF_BITS
6259:<<=
6014:HALF_BITS
5937:HALF_BITS
5863:−
5846:), where
5341:recursive
5300:≤
5241:→
5235:→
5229:→
5223:→
5148:⌋
5142:
5129:⌊
5066:⌋
5049:
5033:⌊
4968:→
4962:→
4956:→
4950:→
4944:→
4938:→
4925:→
4919:→
4913:→
4907:→
4901:→
4895:→
4889:→
4730:// Update
4612:⌋
4602:⌊
4582:⌋
4572:⌊
4500:⌋
4490:⌊
4466:⌋
4456:⌊
4448:However,
4433:⌋
4420:⌊
4417:≥
4414:⌋
4395:⌊
4375:⌋
4362:⌊
4359:≥
4356:⌋
4337:⌊
4310:≤
4307:⌋
4294:⌊
4291:≤
4288:⌋
4278:⌊
4204:⌋
4185:⌊
4182:≥
4160:⌋
4147:⌊
4144:≥
4114:⌋
4104:⌊
4101:≥
4098:⌋
4085:⌊
3979:≥
3949:≥
3916:⌋
3906:⌊
3721:∈
3681:≥
3554:⌋
3544:⌊
3507:
3412:for many
3384:Although
3357:⌋
3347:⌊
3341:⌋
3322:⌊
3281:−
3206:∞
3203:→
3163:converges
3089:≥
2983:−
2936:
2836:→
2818:→
2800:→
2782:→
2764:→
2746:→
2721:→
2703:→
2685:→
2667:→
2649:→
2631:→
2613:→
2595:→
2570:→
2552:→
2534:→
2516:→
2498:→
2480:→
2462:→
2432:sequence
2379:
1863:∑
1500:≯
1443:⌋
1433:⌊
1418:
1388:∈
1351:≤
1329:⌋
1319:⌊
1051:
1016:
921:
802:⋮
792:141421356
786:⌋
776:⌊
770:⌋
755:×
747:⌊
727:⋮
711:⌋
701:⌊
695:⌋
680:×
672:⌊
646:⌋
636:⌊
630:⌋
615:×
607:⌊
581:⌋
571:⌊
565:⌋
550:×
542:⌊
516:⌋
506:⌊
500:⌋
485:×
477:⌊
426:(setting
408:⌋
393:×
385:⌊
295:⌋
285:⌊
151:⌋
145:⌊
139:⌋
129:⌊
114:
86:⌋
76:⌊
61:
7758:Lehmer's
7652:Chunking
7639:division
7568:Fermat's
6936:See also
6899:Unknown
6895:isqrt(n)
6890:SageMath
6869:Unknown
6835:Unknown
6831:isqrt(n)
6816:isqrt(n)
6790:Unknown
6775:Unknown
6718:>>
6706:>>
6619:overflow
6580:<<
6553:<<
6538:overflow
6499:<<
6430:<<
6397:>>
6379:<<
6283:>>
6011:<<
5983:>>
5954:>>
5715:>>
5667:<<
5604:>>
5448:<<
5439:>>
5337:>>
5333:<<
4733:unsigned
4706:unsigned
4655:unsigned
4649:int_sqrt
4643:unsigned
3880:⌋
3824:⌊
3816:⌋
3806:⌋
3786:⌊
3752:⌊
3670:⌋
3660:⌋
3640:⌊
3606:⌊
3314:ensures
3128:sequence
2889:) needs
2214:unsigned
2202:unsigned
2184:unsigned
2169:unsigned
2157:unsigned
1968:unsigned
1950:unsigned
1932:unsigned
1917:unsigned
1905:unsigned
1701:unsigned
1683:unsigned
1671:unsigned
1566:unsigned
1548:unsigned
1536:unsigned
1461:because
1128:unsigned
1113:unsigned
7874:Italics
7796:Kunerth
7776:Cipolla
7657:Fourier
7626:FĂŒrer's
7520:Euler's
7510:Dixon's
7433:PĂ©pin's
6796:Crystal
6496:s_prime
6418:s_prime
6367:r_prime
6334:r_prime
6328:s_prime
5119:2000000
4886:1000000
4871:2000000
2893:steps.
2474:1000000
2456:2000001
2385:2000000
1267:isqrt()
706:2000000
42:to the
7856:Schoof
7743:Binary
7647:Binary
7583:Shor's
7401:Fermat
7308:
7298:
6989:000...
6905:Scheme
6884:2.5.0
6856:Racket
6841:Python
6762:Chapel
6697:return
6096:return
5914:->
5745:result
5742:return
5724:result
5682:result
5664:result
5658:result
5634:result
5574:return
5541:assert
5502:return
5490:return
5415:return
5382:assert
5325:base 2
4904:125004
4898:250002
4892:500001
4850:return
4694:return
3994:, and
2528:125000
2510:250000
2492:500000
2349:return
2109:where
2067:return
1761:return
1647:return
1273:sqrt()
1242:result
1230:printf
1212:result
1164:result
1152:printf
1134:result
23:, the
7677:Short
7406:Lucas
7268:(PDF)
7047:(PDF)
7040:Inria
7036:(PDF)
6948:Notes
6826:Maple
6811:Julia
6740:Some
6571:&
6313:&
6247:&
6204:const
6035:<=
5992:const
5963:const
5934:const
5733:shift
5718:shift
5709:<=
5649:>=
5646:shift
5643:while
5622:shift
5607:shift
5595:while
5586:shift
5547:>=
5532:->
5388:>=
5373:->
5244:1414.
5005:C++20
4922:15666
4916:31270
4910:62509
4775:while
4685:<=
3504:isqrt
3494:field
2933:isqrt
2582:15625
2564:31250
2546:62500
2376:isqrt
2310:<=
2238:while
2163:isqrt
1995:<=
1986:while
1911:isqrt
1719:while
1677:isqrt
1620:<=
1584:while
1542:isqrt
1415:isqrt
1288:of a
1218:isqrt
1173:while
1140:isqrt
1040:Then
1013:isqrt
918:isqrt
641:20000
111:isqrt
58:isqrt
7672:Long
7606:Long
7306:OCLC
7296:ISBN
6929:8.5
6914:RRS
6875:Ruby
6850:3.8
6820:0.3
6805:1.2
6595:))).
6129:else
5980:BITS
5951:BITS
5771:and
5565:<
5496:else
5481:>
5406:<
5347:is:
5238:1414
5232:1417
5226:1512
5220:2048
5200:2048
4971:1414
4965:1414
4959:1422
4953:1579
4947:2282
4941:4074
4928:7896
4784:<
4594:and
4329:and
4163:>
4126:and
4058:>
4040:for
4012:>
3968:for
3701:>
3299:<
3126:The
3109:>
2925:and
2891:1414
2848:1415
2842:1414
2830:1416
2824:1414
2812:1418
2806:1414
2794:1418
2788:1410
2776:1418
2770:1403
2758:1433
2752:1403
2733:1464
2727:1403
2715:1464
2709:1342
2697:1464
2691:1220
2679:1464
2661:1953
2643:1953
2625:3906
2607:7812
2331:else
2127:>
1734:>
1479:>
1357:<
1284:The
1179:true
1104:void
717:1414
223:of)
196:and
176:Let
7836:LLL
7682:SRT
7541:+ 1
7533:â 1
7381:APR
7376:AKS
6973:100
6920:Tcl
6676:let
6529:mut
6523:let
6511:u64
6484:mut
6481:let
6460:let
6439:let
6424:u64
6406:let
6373:u64
6355:let
6322:let
6301:let
6295:u32
6268:let
6226:let
6211:u32
6120:u64
6108:u64
6090:u32
6057:let
6048:u64
6042:MAX
6038:u32
5999:u64
5976:u64
5970:u32
5947:u64
5941:u32
5925:u64
5919:u64
5909:u64
5902:mut
5535:int
5526:int
5511:def
5376:int
5367:int
5352:def
5133:log
5040:log
5003:in
4736:int
4709:int
4658:int
4646:int
3408:is
3218:.
3192:as
3168:to
2673:976
2655:976
2217:int
2205:int
2187:int
2172:int
2160:int
1971:int
1953:int
1935:int
1920:int
1908:int
1704:int
1686:int
1674:int
1569:int
1551:int
1539:int
1203:100
1131:int
1116:int
970:100
861:100
759:100
684:100
652:141
619:100
576:200
554:100
489:100
452:):
397:100
46:of
19:In
7892::
7840:KZ
7838:;
7304:.
7276:37
7274:.
7270:.
7243:.
7225:.
7207:.
7189:.
7171:.
7153:.
7135:.
7117:.
7099:.
7081:.
7063:.
6724:);
6664:-=
6658:);
6616:if
6613:);
6574:((
6568:lo
6547:((
6508:as
6421:as
6403:);
6394:lo
6370:as
6364:((
6352:);
6349:hi
6304:lo
6292:as
6271:hi
6244:()
6209::
6195://
6177://
6165://
6147://
6123:);
6117:as
6105:as
6093:);
6087:as
6045:as
6040:::
6029:if
5997::
5978:::
5968::
5949:::
5939::
5907::
5893:fn
5885::
5736:-=
5697:if
5625:+=
5613:!=
5559:if
5469:if
5400:if
5192:11
5166:,
5154:20
5121:,
4853:x0
4832:x0
4820:x0
4811:x1
4805:x1
4799:x0
4787:x0
4781:x1
4760:x0
4748:x0
4739:x1
4712:x0
4676:if
4445:.
3112:0.
2295:if
2247:!=
2142:.
1883:2.
1587:((
1515:.
1503:27
1482:27
1438:27
1424:27
1276:.
1251:);
1248:10
1227:);
1167:);
1149:);
1096:.
587:14
420:.
354:.
274:.
157:5.
134:27
120:27
50:,
7842:)
7834:(
7539:p
7531:p
7349:e
7342:t
7335:v
7320:.
7312:.
7247:.
7229:.
7211:.
7193:.
7175:.
7157:.
7139:.
7121:.
7103:.
7085:.
7067:.
6991:.
6730:}
6727:}
6715:r
6712:,
6703:s
6700:(
6694:;
6691:2
6688:/
6682:=
6673:}
6670:;
6667:1
6661:s
6655:1
6652:-
6649:s
6646:*
6643:2
6640:(
6634:.
6631:r
6628:=
6625:r
6622:{
6610:q
6607:*
6604:q
6601:(
6592:1
6589:-
6586:)
6577:1
6565:(
6562:|
6559:)
6550:u
6544:=
6541:)
6535:,
6532:r
6526:(
6520:;
6517:q
6514:+
6505:)
6493:(
6490:=
6487:s
6478:;
6472:%
6466:=
6463:u
6457:;
6451:/
6445:=
6442:q
6436:;
6433:1
6427:)
6415:(
6412:=
6391:(
6388:|
6385:)
6376:)
6361:=
6346:(
6340:=
6337:)
6331:,
6325:(
6319:;
6310:n
6307:=
6298:;
6289:)
6280:n
6277:(
6274:=
6265:;
6256:n
6253:;
6238:.
6235:n
6232:=
6223:;
6220:1
6217:!
6214:=
6132:{
6126:}
6114:r
6111:,
6102:s
6099:(
6084:n
6081:(
6075:=
6072:)
6069:r
6066:,
6063:s
6060:(
6051:{
6032:n
6026:;
6023:1
6020:-
6017:)
6008:1
6005:(
6002:=
5989:;
5986:2
5973:=
5960:;
5957:1
5944:=
5931:{
5928:)
5922:,
5916:(
5912:)
5905:n
5899:(
5871:2
5867:s
5860:n
5857:=
5854:r
5834:r
5814:s
5794:n
5739:2
5727:=
5721::
5712:n
5703:*
5691:)
5688:1
5685:+
5679:(
5676:=
5670:1
5661:=
5655::
5652:0
5640:0
5637:=
5628:2
5619::
5616:0
5610:)
5601:n
5598:(
5592:2
5589:=
5577:n
5571::
5568:2
5562:n
5553:,
5550:0
5544:n
5538::
5529:)
5523::
5520:n
5517:(
5499::
5487::
5484:n
5475:*
5466:1
5463:+
5457:=
5451:1
5445:)
5442:2
5436:n
5433:(
5427:=
5418:n
5412::
5409:2
5403:n
5394:,
5391:0
5385:n
5379::
5370:)
5364::
5361:n
5358:(
5329:*
5303:n
5278:n
5197:=
5188:2
5184:=
5179:0
5175:x
5151:=
5145:n
5137:2
5103:n
5077:,
5072:1
5069:+
5063:2
5059:/
5055:)
5052:n
5044:2
5036:(
5029:2
5025:=
5020:0
5016:x
4859:}
4856:;
4847:}
4844:;
4841:2
4838:/
4835:)
4829:/
4826:s
4823:+
4817:(
4814:=
4808:;
4802:=
4796:{
4790:)
4778:(
4772:;
4769:2
4766:/
4763:)
4757:/
4754:s
4751:+
4745:(
4742:=
4727:;
4724:2
4721:/
4718:s
4715:=
4700:;
4697:s
4691:)
4688:1
4682:s
4679:(
4667:{
4664:)
4661:s
4652:(
4618:1
4615:+
4607:n
4577:n
4552:1
4549:+
4546:n
4526:1
4523:+
4520:n
4495:n
4461:n
4428:k
4424:x
4409:1
4406:+
4403:k
4399:x
4370:s
4366:x
4351:1
4348:+
4345:s
4341:x
4315:n
4302:s
4298:x
4283:n
4256:s
4252:x
4229:s
4225:x
4199:1
4196:+
4193:k
4189:x
4177:1
4174:+
4171:k
4167:x
4155:k
4151:x
4139:k
4135:x
4109:n
4093:k
4089:x
4063:n
4053:k
4049:x
4026:1
4023:+
4020:k
4016:x
4007:k
4003:x
3982:1
3976:k
3954:n
3944:k
3940:x
3911:n
3884:,
3875:)
3867:k
3863:x
3859:n
3854:+
3849:k
3845:x
3840:(
3833:2
3830:1
3820:=
3811:)
3799:k
3795:x
3791:n
3782:+
3777:k
3773:x
3768:(
3761:2
3758:1
3729:.
3725:Z
3716:0
3712:x
3707:,
3704:0
3696:0
3692:x
3687:,
3684:0
3678:k
3674:,
3665:)
3653:k
3649:x
3645:n
3636:+
3631:k
3627:x
3622:(
3615:2
3612:1
3602:=
3597:1
3594:+
3591:k
3587:x
3568:n
3549:n
3516:)
3513:n
3510:(
3478:0
3474:x
3453:}
3448:k
3444:x
3440:{
3420:n
3394:n
3352:n
3344:=
3336:1
3333:+
3330:k
3326:x
3302:c
3295:|
3289:k
3285:x
3276:1
3273:+
3270:k
3266:x
3261:|
3240:1
3237:=
3234:c
3200:k
3178:n
3150:}
3145:k
3141:x
3137:{
3104:0
3100:x
3095:,
3092:0
3086:k
3082:,
3078:)
3070:k
3066:x
3062:n
3057:+
3052:k
3048:x
3043:(
3036:2
3033:1
3028:=
3023:1
3020:+
3017:k
3013:x
2992:0
2989:=
2986:n
2978:2
2974:x
2945:)
2942:n
2939:(
2911:n
2877:0
2851:]
2845:,
2839:[
2833:]
2827:,
2821:[
2815:]
2809:,
2803:[
2797:]
2791:,
2785:[
2779:]
2773:,
2767:[
2761:]
2755:,
2749:[
2736:]
2730:,
2724:[
2718:]
2712:,
2706:[
2700:]
2694:,
2688:[
2682:]
2676:,
2670:[
2664:]
2658:,
2652:[
2646:]
2640:,
2637:0
2634:[
2628:]
2622:,
2619:0
2616:[
2610:]
2604:,
2601:0
2598:[
2585:]
2579:,
2576:0
2573:[
2567:]
2561:,
2558:0
2555:[
2549:]
2543:,
2540:0
2537:[
2531:]
2525:,
2522:0
2519:[
2513:]
2507:,
2504:0
2501:[
2495:]
2489:,
2486:0
2483:[
2477:]
2471:,
2468:0
2465:[
2459:]
2453:,
2450:0
2447:[
2420:]
2417:R
2414:,
2411:L
2408:[
2388:)
2382:(
2358:}
2355:;
2352:L
2346:}
2343:;
2340:M
2337:=
2334:R
2328:;
2325:M
2322:=
2319:L
2316:)
2313:y
2307:M
2304:*
2301:M
2298:(
2292:;
2289:2
2286:/
2283:)
2280:R
2277:+
2274:L
2271:(
2268:=
2265:M
2262:{
2259:)
2256:1
2253:-
2250:R
2244:L
2241:(
2235:;
2232:1
2229:+
2226:y
2223:=
2220:R
2211:;
2208:M
2199:;
2196:0
2193:=
2190:L
2181:{
2178:)
2175:y
2166:(
2130:y
2122:2
2118:x
2097:x
2076:}
2073:;
2070:L
2064:}
2061:;
2058:1
2055:+
2052:L
2049:=
2046:L
2043:;
2040:2
2037:+
2034:d
2031:=
2028:d
2022:;
2019:d
2016:+
2013:a
2010:=
2007:a
2004:{
2001:)
1998:y
1992:a
1989:(
1983:;
1980:3
1977:=
1974:d
1965:;
1962:1
1959:=
1956:a
1947:;
1944:0
1941:=
1938:L
1929:{
1926:)
1923:y
1914:(
1878:L
1873:1
1870:=
1867:i
1859:+
1856:1
1853:+
1848:2
1844:L
1840:=
1837:1
1834:+
1831:L
1828:2
1825:+
1820:2
1816:L
1812:=
1807:2
1803:)
1799:1
1796:+
1793:L
1790:(
1770:}
1767:;
1764:R
1758:;
1755:1
1752:-
1749:R
1746:=
1743:R
1740:)
1737:y
1731:R
1728:*
1725:R
1722:(
1716:;
1713:y
1710:=
1707:R
1695:{
1692:)
1689:y
1680:(
1656:}
1653:;
1650:L
1644:;
1641:1
1638:+
1635:L
1632:=
1629:L
1626:)
1623:y
1617:)
1614:1
1611:+
1608:L
1605:(
1602:*
1599:)
1596:1
1593:+
1590:L
1581:;
1578:0
1575:=
1572:L
1560:{
1557:)
1554:y
1545:(
1495:2
1491:5
1474:2
1470:6
1449:5
1446:=
1430:=
1427:)
1421:(
1392:N
1385:x
1382:,
1377:2
1373:)
1369:1
1366:+
1363:x
1360:(
1354:y
1346:2
1342:x
1338::
1335:x
1332:=
1324:y
1299:y
1260:}
1257:}
1245:%
1239:,
1233:(
1224:y
1221:(
1215:=
1206:;
1200:*
1197:y
1194:=
1191:y
1188:{
1182:)
1176:(
1161:,
1155:(
1146:y
1143:(
1137:=
1125:{
1122:)
1119:y
1110:(
1082:y
1060:)
1057:y
1054:(
1025:)
1022:y
1019:(
950:y
930:)
927:y
924:(
896:y
881:k
865:k
835:=
830:2
789:=
773:=
763:8
752:2
744::
741:8
738:=
735:k
714:=
698:=
688:3
677:2
669::
666:3
663:=
660:k
649:=
633:=
623:2
612:2
604::
601:2
598:=
595:k
584:=
568:=
558:1
547:2
539::
536:1
533:=
530:k
522:1
519:=
511:2
503:=
493:0
482:2
474::
471:0
468:=
465:k
440:2
437:=
434:y
401:k
390:y
365:k
342:k
320:y
290:y
258:y
233:y
204:k
184:y
154:=
142:=
126:=
123:)
117:(
89:.
81:n
73:=
70:)
67:n
64:(
48:n
36:m
32:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.