Isqrt (integer square root) of X
Sometimes a function is needed to find the integer square root of X, where X can be a real non─negative number.
Often X is actually a non─negative integer.
For the purposes of this task, X can be an integer or a real number, but if it simplifies things in your computer programming language, assume it's an integer.
One of the most common uses of Isqrt is in the division of an integer by all factors (or
primes) up to the
√ X of that
integer, either to find the factors of that integer, or to determine primality.
An alternative method for finding the Isqrt of a number is to
calculate: floor( sqrt(X) )
- where sqrt is the square root function for non─negative real numbers, and
- where floor is the floor function for real numbers.
If the hardware supports the computation of (real) square roots, the above method might be a faster method for
small numbers that don't have very many significant (decimal) digits.
However, floating point arithmetic is limited in the number of (binary or decimal) digits that it can support.
- Pseudo─code using quadratic residue
For this task, the integer square root of a non─negative number will be computed using a version of quadratic residue, which has the advantage that no floating point calculations are used, only integer arithmetic. Furthermore, the divisions and multiplication can be performed by bit shifting.
The disadvantage is the limitation of the size of the largest integer that a particular computer programming language can support.
Pseudo─code of a procedure for finding the integer square root of X:
/*═══════find Isqrt(x)══════*/
/*all variables are integers*/
q ◄── 1 /*initialize Q to unity. */
/*find a power of 4 that */
/*is greater than X. */
perform while q <= x /*perform while Q <= X. */
q ◄── q * 4 /*multiply Q by four. */
end /*perform*/
/*Q is now greater than X.*/
z ◄── x /*set Z to the value of X.*/
r ◄── 0 /*initialize R to zero. */
perform while q > 1 /*perform while Q > unity. */
q ◄── q ÷ 4 /*integer divide by four. */
t ◄── z - r - q /*compute value of T. */
r ◄── r ÷ 2 /*integer divide by two. */
if t >= 0 then do /*if T is >= zero then···*/
z ◄── t /* set Z to value of T. */
r ◄── r + q /* compute new value of R.*/
end
end /*perform*/
/*R is now the Isqrt(X). */
Another version for the (above) 1st perform is:
perform until q > X /*perform until Q > X. */
q ◄── q * 4 /*multiply Q by four. */
end /*perform*/
Integer square roots of some values:
Isqrt( 0) is 0 Isqrt(60) is 7 Isqrt( 99) is 9 Isqrt( 1) is 1 Isqrt(61) is 7 Isqrt(100) is 10 Isqrt( 2) is 1 Isqrt(62) is 7 Isqrt(102) is 10 Isqrt( 3) is 1 Isqrt(63) is 7 Isqrt( 4) is 2 Isqrt(64) is 8 Isqet(120) is 10 Isqrt( 5) is 2 Isqrt(65) is 8 Isqrt(121) is 11 Isqrt( 6) is 2 Isqrt(66) is 8 Isqrt(122) is 11 Isqrt( 7) is 2 Isqrt(67) is 8 Isqrt( 8) is 2 Isqrt(68) is 8 Isqrt(143) is 11 Isqrt( 9) is 3 Isqrt(69) is 8 Isqrt(144) is 12 Isqrt(10) is 3 Isqrt(70) is 8 Isqrt(145) is 12
- Task
Compute and show all output here (on this page) for:
- the
Isqrtof the integers from 0 ───► 65 (inclusive), shown in a horizontal format. - the
Isqrtof the powers from 71 ───► 773 (inclusive), shown in a vertical format. - use commas in the displaying of larger numbers.
- the
You can show more numbers for the 2nd requirement if the displays fits on one screen on Rosetta Code.
If your computer programming language only supports smaller integers, show what you can.
- Related tasks
Factor
The isqrt word is a straightforward translation of the pseudocode from the task description using lexical variables.
<lang factor>USING: formatting io kernel locals math math.functions math.ranges prettyprint sequences tools.memory.private ;
- isqrt ( x -- n )
1 :> q!
[ q x > ] [ q 4 * q! ] until
x 0 :> ( z! r! )
[ q 1 > ] [
q 4 /i q!
z r - q - :> t!
r -1 shift r!
t 0 >= [
t z!
r q + r!
] when
] while
r ;
"Integer square root for numbers 0 to 65 (inclusive):" print 66 <iota> [ bl ] [ isqrt pprint ] interleave nl nl
- align ( str str str -- ) "%2s%85s%44s\n" printf ;
- show ( n -- ) dup 7 swap ^ dup isqrt [ commas ] tri@ align ;
"x" "7^x" "isqrt(7^x)" align "-" "---" "----------" align 1 73 2 <range> [ show ] each</lang>
- Output:
Integer square root for numbers 0 to 65 (inclusive): 0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 x 7^x isqrt(7^x) - --- ---------- 1 7 2 3 343 18 5 16,807 129 7 823,543 907 9 40,353,607 6,352 11 1,977,326,743 44,467 13 96,889,010,407 311,269 15 4,747,561,509,943 2,178,889 17 232,630,513,987,207 15,252,229 19 11,398,895,185,373,143 106,765,608 21 558,545,864,083,284,007 747,359,260 23 27,368,747,340,080,916,343 5,231,514,822 25 1,341,068,619,663,964,900,807 36,620,603,758 27 65,712,362,363,534,280,139,543 256,344,226,312 29 3,219,905,755,813,179,726,837,607 1,794,409,584,184 31 157,775,382,034,845,806,615,042,743 12,560,867,089,291 33 7,730,993,719,707,444,524,137,094,407 87,926,069,625,040 35 378,818,692,265,664,781,682,717,625,943 615,482,487,375,282 37 18,562,115,921,017,574,302,453,163,671,207 4,308,377,411,626,977 39 909,543,680,129,861,140,820,205,019,889,143 30,158,641,881,388,842 41 44,567,640,326,363,195,900,190,045,974,568,007 211,110,493,169,721,897 43 2,183,814,375,991,796,599,109,312,252,753,832,343 1,477,773,452,188,053,281 45 107,006,904,423,598,033,356,356,300,384,937,784,807 10,344,414,165,316,372,973 47 5,243,338,316,756,303,634,461,458,718,861,951,455,543 72,410,899,157,214,610,812 49 256,923,577,521,058,878,088,611,477,224,235,621,321,607 506,876,294,100,502,275,687 51 12,589,255,298,531,885,026,341,962,383,987,545,444,758,743 3,548,134,058,703,515,929,815 53 616,873,509,628,062,366,290,756,156,815,389,726,793,178,407 24,836,938,410,924,611,508,707 55 30,226,801,971,775,055,948,247,051,683,954,096,612,865,741,943 173,858,568,876,472,280,560,953 57 1,481,113,296,616,977,741,464,105,532,513,750,734,030,421,355,207 1,217,009,982,135,305,963,926,677 59 72,574,551,534,231,909,331,741,171,093,173,785,967,490,646,405,143 8,519,069,874,947,141,747,486,745 61 3,556,153,025,177,363,557,255,317,383,565,515,512,407,041,673,852,007 59,633,489,124,629,992,232,407,216 63 174,251,498,233,690,814,305,510,551,794,710,260,107,945,042,018,748,343 417,434,423,872,409,945,626,850,517 65 8,538,323,413,450,849,900,970,017,037,940,802,745,289,307,058,918,668,807 2,922,040,967,106,869,619,387,953,625 67 418,377,847,259,091,645,147,530,834,859,099,334,519,176,045,887,014,771,543 20,454,286,769,748,087,335,715,675,381 69 20,500,514,515,695,490,612,229,010,908,095,867,391,439,626,248,463,723,805,607 143,180,007,388,236,611,350,009,727,669 71 1,004,525,211,269,079,039,999,221,534,496,697,502,180,541,686,174,722,466,474,743 1,002,260,051,717,656,279,450,068,093,686 73 49,221,735,352,184,872,959,961,855,190,338,177,606,846,542,622,561,400,857,262,407 7,015,820,362,023,593,956,150,476,655,802
Go
Go's big.Int type already has a built-in integer square root function but, as the point of this task appears to be to compute it using a particular algorithm, we re-code it from the pseudo-code given in the task description. <lang go>package main
import (
"fmt" "log" "math/big"
)
var zero = big.NewInt(0) var one = big.NewInt(1) var seven = big.NewInt(7)
func isqrt(x *big.Int) *big.Int {
if x.Cmp(zero) < 0 {
log.Fatal("Argument cannot be negative.")
}
q := big.NewInt(1)
for q.Cmp(x) <= 0 {
q.Lsh(q, 2)
}
z := new(big.Int).Set(x)
r := big.NewInt(0)
for q.Cmp(one) > 0 {
q.Rsh(q, 2)
t := new(big.Int)
t.Add(t, z)
t.Sub(t, r)
t.Sub(t, q)
r.Rsh(r, 1)
if t.Cmp(zero) >= 0 {
z.Set(t)
r.Add(r, q)
}
}
return r
}
func commatize(s string) string {
le := len(s)
for i := le - 3; i >= 1; i -= 3 {
s = s[0:i] + "," + s[i:]
}
return s
}
func main() {
fmt.Println("The integer square roots of integers from 0 to 65 are:")
for i := int64(0); i <= 65; i++ {
fmt.Printf("%d ", isqrt(big.NewInt(i)))
}
fmt.Println()
fmt.Println("\nThe integer square roots of powers of 7 from 7^1 up to 7^73 are:\n")
fmt.Println("power 7 ^ power integer square root")
fmt.Println("----- --------------------------------------------------------------------------------- -----------------------------------------")
pow7 := big.NewInt(7)
for i := 1; i <= 73; i++ {
fmt.Printf("%2d %84s %41s\n", i, commatize(pow7.String()), commatize(isqrt(pow7).String()))
pow7.Mul(pow7, seven)
}
}</lang>
- Output:
The integer square roots of integers from 0 to 65 are: 0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 The integer square roots of powers of 7 from 7^1 up to 7^73 are: power 7 ^ power integer square root ----- --------------------------------------------------------------------------------- ----------------------------------------- 1 7 2 2 49 7 3 343 18 4 2,401 49 5 16,807 129 6 117,649 343 7 823,543 907 8 5,764,801 2,401 9 40,353,607 6,352 10 282,475,249 16,807 11 1,977,326,743 44,467 12 13,841,287,201 117,649 13 96,889,010,407 311,269 14 678,223,072,849 823,543 15 4,747,561,509,943 2,178,889 16 33,232,930,569,601 5,764,801 17 232,630,513,987,207 15,252,229 18 1,628,413,597,910,449 40,353,607 19 11,398,895,185,373,143 106,765,608 20 79,792,266,297,612,001 282,475,249 21 558,545,864,083,284,007 747,359,260 22 3,909,821,048,582,988,049 1,977,326,743 23 27,368,747,340,080,916,343 5,231,514,822 24 191,581,231,380,566,414,401 13,841,287,201 25 1,341,068,619,663,964,900,807 36,620,603,758 26 9,387,480,337,647,754,305,649 96,889,010,407 27 65,712,362,363,534,280,139,543 256,344,226,312 28 459,986,536,544,739,960,976,801 678,223,072,849 29 3,219,905,755,813,179,726,837,607 1,794,409,584,184 30 22,539,340,290,692,258,087,863,249 4,747,561,509,943 31 157,775,382,034,845,806,615,042,743 12,560,867,089,291 32 1,104,427,674,243,920,646,305,299,201 33,232,930,569,601 33 7,730,993,719,707,444,524,137,094,407 87,926,069,625,040 34 54,116,956,037,952,111,668,959,660,849 232,630,513,987,207 35 378,818,692,265,664,781,682,717,625,943 615,482,487,375,282 36 2,651,730,845,859,653,471,779,023,381,601 1,628,413,597,910,449 37 18,562,115,921,017,574,302,453,163,671,207 4,308,377,411,626,977 38 129,934,811,447,123,020,117,172,145,698,449 11,398,895,185,373,143 39 909,543,680,129,861,140,820,205,019,889,143 30,158,641,881,388,842 40 6,366,805,760,909,027,985,741,435,139,224,001 79,792,266,297,612,001 41 44,567,640,326,363,195,900,190,045,974,568,007 211,110,493,169,721,897 42 311,973,482,284,542,371,301,330,321,821,976,049 558,545,864,083,284,007 43 2,183,814,375,991,796,599,109,312,252,753,832,343 1,477,773,452,188,053,281 44 15,286,700,631,942,576,193,765,185,769,276,826,401 3,909,821,048,582,988,049 45 107,006,904,423,598,033,356,356,300,384,937,784,807 10,344,414,165,316,372,973 46 749,048,330,965,186,233,494,494,102,694,564,493,649 27,368,747,340,080,916,343 47 5,243,338,316,756,303,634,461,458,718,861,951,455,543 72,410,899,157,214,610,812 48 36,703,368,217,294,125,441,230,211,032,033,660,188,801 191,581,231,380,566,414,401 49 256,923,577,521,058,878,088,611,477,224,235,621,321,607 506,876,294,100,502,275,687 50 1,798,465,042,647,412,146,620,280,340,569,649,349,251,249 1,341,068,619,663,964,900,807 51 12,589,255,298,531,885,026,341,962,383,987,545,444,758,743 3,548,134,058,703,515,929,815 52 88,124,787,089,723,195,184,393,736,687,912,818,113,311,201 9,387,480,337,647,754,305,649 53 616,873,509,628,062,366,290,756,156,815,389,726,793,178,407 24,836,938,410,924,611,508,707 54 4,318,114,567,396,436,564,035,293,097,707,728,087,552,248,849 65,712,362,363,534,280,139,543 55 30,226,801,971,775,055,948,247,051,683,954,096,612,865,741,943 173,858,568,876,472,280,560,953 56 211,587,613,802,425,391,637,729,361,787,678,676,290,060,193,601 459,986,536,544,739,960,976,801 57 1,481,113,296,616,977,741,464,105,532,513,750,734,030,421,355,207 1,217,009,982,135,305,963,926,677 58 10,367,793,076,318,844,190,248,738,727,596,255,138,212,949,486,449 3,219,905,755,813,179,726,837,607 59 72,574,551,534,231,909,331,741,171,093,173,785,967,490,646,405,143 8,519,069,874,947,141,747,486,745 60 508,021,860,739,623,365,322,188,197,652,216,501,772,434,524,836,001 22,539,340,290,692,258,087,863,249 61 3,556,153,025,177,363,557,255,317,383,565,515,512,407,041,673,852,007 59,633,489,124,629,992,232,407,216 62 24,893,071,176,241,544,900,787,221,684,958,608,586,849,291,716,964,049 157,775,382,034,845,806,615,042,743 63 174,251,498,233,690,814,305,510,551,794,710,260,107,945,042,018,748,343 417,434,423,872,409,945,626,850,517 64 1,219,760,487,635,835,700,138,573,862,562,971,820,755,615,294,131,238,401 1,104,427,674,243,920,646,305,299,201 65 8,538,323,413,450,849,900,970,017,037,940,802,745,289,307,058,918,668,807 2,922,040,967,106,869,619,387,953,625 66 59,768,263,894,155,949,306,790,119,265,585,619,217,025,149,412,430,681,649 7,730,993,719,707,444,524,137,094,407 67 418,377,847,259,091,645,147,530,834,859,099,334,519,176,045,887,014,771,543 20,454,286,769,748,087,335,715,675,381 68 2,928,644,930,813,641,516,032,715,844,013,695,341,634,232,321,209,103,400,801 54,116,956,037,952,111,668,959,660,849 69 20,500,514,515,695,490,612,229,010,908,095,867,391,439,626,248,463,723,805,607 143,180,007,388,236,611,350,009,727,669 70 143,503,601,609,868,434,285,603,076,356,671,071,740,077,383,739,246,066,639,249 378,818,692,265,664,781,682,717,625,943 71 1,004,525,211,269,079,039,999,221,534,496,697,502,180,541,686,174,722,466,474,743 1,002,260,051,717,656,279,450,068,093,686 72 7,031,676,478,883,553,279,994,550,741,476,882,515,263,791,803,223,057,265,323,201 2,651,730,845,859,653,471,779,023,381,601 73 49,221,735,352,184,872,959,961,855,190,338,177,606,846,542,622,561,400,857,262,407 7,015,820,362,023,593,956,150,476,655,802
Phix
See also Integer_roots#Phix for a simpler and shorter example using the mpz_root() routine. <lang Phix>include mpfr.e
function isqrt(mpz x)
if mpz_cmp_si(x,0)<0 then
crash("Argument cannot be negative.")
end if
mpz q = mpz_init(1),
r = mpz_init(0),
t = mpz_init(0),
z = mpz_init_set(x)
while mpz_cmp(q,x)<= 0 do
mpz_mul_si(q,q,4)
end while
while mpz_cmp_si(q,1)>0 do
if mpz_fdiv_q_ui(q, q, 4)!=0 then ?9/0 end if
mpz_sub(t,z,r)
mpz_sub(t,t,q)
if mpz_fdiv_q_ui(r, r, 2)!=0 then ?9/0 end if
if mpz_cmp_si(t,0) >= 0 then
mpz_set(z,t)
mpz_add(r,r,q)
end if
end while
-- return r
return shorten(mpz_get_str(r,10,true))
end function
printf(1,"The integer square roots of integers from 0 to 65 are:\n") for i=0 to 65 do
printf(1,"%s ", {isqrt(mpz_init(i))})
end for printf(1,"\n\npower 7 ^ power integer square root\n") printf(1,"----- --------------------------------------------------------- ----------------------------------------------------------\n") mpz pow7 = mpz_init(7) for i=1 to 9000 do
if i<10
or (i<100 and remainder(i,10)=0)
or (i<1000 and remainder(i,100)=0)
or remainder(i,1000)=0 then
printf(1,"%4d %58s %60s\n", {i, shorten(mpz_get_str(pow7,10,true)),isqrt(pow7)})
end if
mpz_mul_si(pow7,pow7,7)
end for</lang>
- Output:
The integer square roots of integers from 0 to 65 are: 0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 power 7 ^ power integer square root ----- --------------------------------------------------------- ---------------------------------------------------------- 1 7 2 2 49 7 3 343 18 4 2,401 49 5 16,807 129 6 117,649 343 7 823,543 907 8 5,764,801 2,401 9 40,353,607 6,352 10 282,475,249 16,807 20 79,792,266,297,612,001 282,475,249 30 22,539,340,290,692,258,087,863,249 4,747,561,509,943 40 6,366,805,760,909,027,985,741,435,139,224,001 79,792,266,297,612,001 50 1,798,465,042,647,41...,569,649,349,251,249 (43 digits) 1,341,068,619,663,964,900,807 60 508,021,860,739,623,...,772,434,524,836,001 (51 digits) 22,539,340,290,692,258,087,863,249 70 143,503,601,609,868,...,739,246,066,639,249 (60 digits) 378,818,692,265,664,781,682,717,625,943 80 40,536,215,597,144,3...,746,192,454,448,001 (68 digits) 6,366,805,760,909,027,985,741,435,139,224,001 90 11,450,477,594,321,0...,372,120,240,027,249 (77 digits) 107,006,904,423,598,033,356,356,300,384,937,784,807 100 3,234,476,509,624,75...,459,636,928,060,001 (85 digits) 1,798,465,042,647,41...,569,649,349,251,249 (43 digits) 200 10,461,838,291,314,3...,534,637,456,120,001 (170 digits) 3,234,476,509,624,75...,459,636,928,060,001 (85 digits) 300 33,838,570,200,749,1...,841,001,584,180,001 (254 digits) 5,817,092,933,824,34...,721,127,496,191,249 (127 digits) 400 109,450,060,433,611,...,994,729,312,240,001 (339 digits) 10,461,838,291,314,3...,534,637,456,120,001 (170 digits) 500 354,013,649,449,525,...,611,820,640,300,001 (423 digits) 18,815,250,448,759,0...,761,742,043,131,249 (212 digits) 600 1,145,048,833,231,02...,308,275,568,360,001 (508 digits) 33,838,570,200,749,1...,841,001,584,180,001 (254 digits) 700 3,703,633,553,458,98...,700,094,096,420,001 (592 digits) 60,857,485,599,217,6...,075,492,990,071,249 (296 digits) 800 11,979,315,728,921,1...,403,276,224,480,001 (677 digits) 109,450,060,433,611,...,994,729,312,240,001 (339 digits) 900 38,746,815,326,573,9...,033,821,952,540,001 (761 digits) 196,842,107,605,496,...,046,380,337,011,249 (381 digits) 1000 125,325,663,996,571,...,207,731,280,600,001 (846 digits) 354,013,649,449,525,...,611,820,640,300,001 (423 digits) 2000 15,706,522,056,181,6...,351,822,561,200,001 (1,691 digits) 125,325,663,996,571,...,207,731,280,600,001 (846 digits) 3000 1,968,430,305,767,76...,432,273,841,800,001 (2,536 digits) 44,366,995,681,111,4...,787,731,920,900,001 (1,268 digits) 4000 246,694,835,101,319,...,449,085,122,400,001 (3,381 digits) 15,706,522,056,181,6...,351,822,561,200,001 (1,691 digits) 5000 30,917,194,013,597,6...,402,256,403,000,001 (4,226 digits) 5,560,323,193,268,32...,900,003,201,500,001 (2,113 digits) 6000 3,874,717,868,664,96...,291,787,683,600,001 (5,071 digits) 1,968,430,305,767,76...,432,273,841,800,001 (2,536 digits) 7000 485,601,589,689,818,...,117,678,964,200,001 (5,916 digits) 696,851,196,231,891,...,948,634,482,100,001 (2,958 digits) 8000 60,858,341,665,667,3...,879,930,244,800,001 (6,761 digits) 246,694,835,101,319,...,449,085,122,400,001 (3,381 digits) 9000 7,627,112,078,979,99...,578,541,525,400,001 (7,606 digits) 87,333,338,874,567,2...,933,625,762,700,001 (3,803 digits)
(Note that pre-0.8.2 the "(NNN digits)" count includes commas)
Raku
Since there is already the task Integer roots that covers exactly this operation, with the caveat that it will calculate any nth root (including 2) not just square roots, we'll refer you to that.
See the Integer roots Raku entry.
REXX
A fair amount of code was included so that the output aligns correctly. <lang rexx>/*REXX program computes and displays the Isqrt (integer square root) of some integers.*/ numeric digits 200 /*insure 'nuff decimal digs for results*/ parse arg range power base . /*obtain optional arguments from the CL*/ if range== | range=="," then range= 0..65 /*Not specified? Then use the default.*/ if power== | power=="," then power= 1..73 /* " " " " " " */ if base == | base =="," then base = 7 /* " " " " " " */ parse var range rLO '..' rHI; if rHI== then rHI= rLO /*handle a range? */ parse var power pLO '..' pHI; if pHI== then pHI= pLO /* " " " */ $=
do j=rLO to rHI while rHI>0 /*compute Isqrt for a range of integers*/
$= $ commas( Isqrt(j) ) /*append the Isqrt to a list for output*/
end /*j*/
$= strip($) /*elide the leading blank in the list. */ say center(' Isqrt for numbers: ' rLO " ──► " rHI' ', length($), "─") say strip($) /*$ has a leading blank for 1st number*/ say z= base ** pHI /*compute max. exponentiation product.*/ Lp= max(30, length( commas( z) ) ) /*length of " " " */ Lr= max(20, length( commas( Isqrt(z) ) ) ) /* " " " " " Isqrt of above.*/ say 'index' center(base"**index", Lp) center('Isqrt', Lr) /*show a title.*/ say '─────' copies("─", Lp) copies('─', Lr) /* " " header*/
do j=pLO to pHI by 2 while pHI>0; x= base ** j
say center(j, 5) right( commas(x), Lp) right( commas( Isqrt(x) ), Lr)
end /*j*/ /* [↑] show a bunch of powers & Isqrt.*/
exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg _; do jc=length(_)-3 to 1 by -3; _=insert(',', _, jc); end; return _ /*──────────────────────────────────────────────────────────────────────────────────────*/ Isqrt: procedure; parse arg x /*obtain the only passed argument X. */
x= x % 1 /*convert possible real X to an integer*/ /* ◄■■■■■■■ optional. */
q= 1 /*initialize the Q variable to unity.*/
do until q>x /*find a Q that is greater than X. */
q= q * 4 /*multiply Q by four. */
end /*until*/
r= 0 /*R: will be the integer sqrt of X. */
do while q>1 /*keep processing while Q is > than 1*/
q= q % 4 /*divide Q by four (no remainder). */
t= x - r - q /*compute a temporary variable. */
r= r % 2 /*divide R by two (no remainder). */
if t >= 0 then do /*if T is non─negative ... */
x= t /*recompute the value of X */
r= r + q /* " " " " R */
end
end /*while*/
return r /*return the integer square root of X. */</lang>
- output when using the default inputs:
───────────────────────────────────────────────── Isqrt for numbers: 0 ──► 65 ────────────────────────────────────────────────── 0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 index 7**index Isqrt ───── ────────────────────────────────────────────────────────────────────────────────── ───────────────────────────────────────── 1 7 2 3 343 18 5 16,807 129 7 823,543 907 9 40,353,607 6,352 11 1,977,326,743 44,467 13 96,889,010,407 311,269 15 4,747,561,509,943 2,178,889 17 232,630,513,987,207 15,252,229 19 11,398,895,185,373,143 106,765,608 21 558,545,864,083,284,007 747,359,260 23 27,368,747,340,080,916,343 5,231,514,822 25 1,341,068,619,663,964,900,807 36,620,603,758 27 65,712,362,363,534,280,139,543 256,344,226,312 29 3,219,905,755,813,179,726,837,607 1,794,409,584,184 31 157,775,382,034,845,806,615,042,743 12,560,867,089,291 33 7,730,993,719,707,444,524,137,094,407 87,926,069,625,040 35 378,818,692,265,664,781,682,717,625,943 615,482,487,375,282 37 18,562,115,921,017,574,302,453,163,671,207 4,308,377,411,626,977 39 909,543,680,129,861,140,820,205,019,889,143 30,158,641,881,388,842 41 44,567,640,326,363,195,900,190,045,974,568,007 211,110,493,169,721,897 43 2,183,814,375,991,796,599,109,312,252,753,832,343 1,477,773,452,188,053,281 45 107,006,904,423,598,033,356,356,300,384,937,784,807 10,344,414,165,316,372,973 47 5,243,338,316,756,303,634,461,458,718,861,951,455,543 72,410,899,157,214,610,812 49 256,923,577,521,058,878,088,611,477,224,235,621,321,607 506,876,294,100,502,275,687 51 12,589,255,298,531,885,026,341,962,383,987,545,444,758,743 3,548,134,058,703,515,929,815 53 616,873,509,628,062,366,290,756,156,815,389,726,793,178,407 24,836,938,410,924,611,508,707 55 30,226,801,971,775,055,948,247,051,683,954,096,612,865,741,943 173,858,568,876,472,280,560,953 57 1,481,113,296,616,977,741,464,105,532,513,750,734,030,421,355,207 1,217,009,982,135,305,963,926,677 59 72,574,551,534,231,909,331,741,171,093,173,785,967,490,646,405,143 8,519,069,874,947,141,747,486,745 61 3,556,153,025,177,363,557,255,317,383,565,515,512,407,041,673,852,007 59,633,489,124,629,992,232,407,216 63 174,251,498,233,690,814,305,510,551,794,710,260,107,945,042,018,748,343 417,434,423,872,409,945,626,850,517 65 8,538,323,413,450,849,900,970,017,037,940,802,745,289,307,058,918,668,807 2,922,040,967,106,869,619,387,953,625 67 418,377,847,259,091,645,147,530,834,859,099,334,519,176,045,887,014,771,543 20,454,286,769,748,087,335,715,675,381 69 20,500,514,515,695,490,612,229,010,908,095,867,391,439,626,248,463,723,805,607 143,180,007,388,236,611,350,009,727,669 71 1,004,525,211,269,079,039,999,221,534,496,697,502,180,541,686,174,722,466,474,743 1,002,260,051,717,656,279,450,068,093,686 73 49,221,735,352,184,872,959,961,855,190,338,177,606,846,542,622,561,400,857,262,407 7,015,820,362,023,593,956,150,476,655,802
Wren
<lang ecmascript>import "/big" for BigInt import "/fmt" for Fmt
var isqrt = Fn.new { |x|
if (!(x is BigInt && x >= BigInt.zero)) {
Fiber.abort("Argument must be a non-negative big integer.")
}
var q = BigInt.one
while (q <= x) q = q * 4
var z = x
var r = BigInt.zero
while (q > BigInt.one) {
q = q >> 2
var t = z - r - q
r = r >> 1
if (t >= 0) {
z = t
r = r + q
}
}
return r
}
System.print("The integer square roots of integers from 0 to 65 are:") for (i in 0..65) System.write("%(isqrt.call(BigInt.new(i))) ") System.print()
System.print("\nThe integer square roots of powers of 7 from 7^1 up to 7^73 are:\n") System.print("power 7 ^ power integer square root") System.print("----- --------------------------------------------------------------------------------- -----------------------------------------") var seven = BigInt.new(7) var pow7 = seven.copy() for (i in 1..73) {
Fmt.print("$2d $,84s $,41s", i, pow7, isqrt.call(pow7))
pow7 = pow7 * seven
}</lang>
- Output:
The integer square roots of integers from 0 to 65 are: 0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 The integer square roots of powers of 7 from 7^1 up to 7^73 are: power 7 ^ power integer square root ----- --------------------------------------------------------------------------------- ----------------------------------------- 1 7 2 2 49 7 3 343 18 4 2,401 49 5 16,807 129 6 117,649 343 7 823,543 907 8 5,764,801 2,401 9 40,353,607 6,352 10 282,475,249 16,807 11 1,977,326,743 44,467 12 13,841,287,201 117,649 13 96,889,010,407 311,269 14 678,223,072,849 823,543 15 4,747,561,509,943 2,178,889 16 33,232,930,569,601 5,764,801 17 232,630,513,987,207 15,252,229 18 1,628,413,597,910,449 40,353,607 19 11,398,895,185,373,143 106,765,608 20 79,792,266,297,612,001 282,475,249 21 558,545,864,083,284,007 747,359,260 22 3,909,821,048,582,988,049 1,977,326,743 23 27,368,747,340,080,916,343 5,231,514,822 24 191,581,231,380,566,414,401 13,841,287,201 25 1,341,068,619,663,964,900,807 36,620,603,758 26 9,387,480,337,647,754,305,649 96,889,010,407 27 65,712,362,363,534,280,139,543 256,344,226,312 28 459,986,536,544,739,960,976,801 678,223,072,849 29 3,219,905,755,813,179,726,837,607 1,794,409,584,184 30 22,539,340,290,692,258,087,863,249 4,747,561,509,943 31 157,775,382,034,845,806,615,042,743 12,560,867,089,291 32 1,104,427,674,243,920,646,305,299,201 33,232,930,569,601 33 7,730,993,719,707,444,524,137,094,407 87,926,069,625,040 34 54,116,956,037,952,111,668,959,660,849 232,630,513,987,207 35 378,818,692,265,664,781,682,717,625,943 615,482,487,375,282 36 2,651,730,845,859,653,471,779,023,381,601 1,628,413,597,910,449 37 18,562,115,921,017,574,302,453,163,671,207 4,308,377,411,626,977 38 129,934,811,447,123,020,117,172,145,698,449 11,398,895,185,373,143 39 909,543,680,129,861,140,820,205,019,889,143 30,158,641,881,388,842 40 6,366,805,760,909,027,985,741,435,139,224,001 79,792,266,297,612,001 41 44,567,640,326,363,195,900,190,045,974,568,007 211,110,493,169,721,897 42 311,973,482,284,542,371,301,330,321,821,976,049 558,545,864,083,284,007 43 2,183,814,375,991,796,599,109,312,252,753,832,343 1,477,773,452,188,053,281 44 15,286,700,631,942,576,193,765,185,769,276,826,401 3,909,821,048,582,988,049 45 107,006,904,423,598,033,356,356,300,384,937,784,807 10,344,414,165,316,372,973 46 749,048,330,965,186,233,494,494,102,694,564,493,649 27,368,747,340,080,916,343 47 5,243,338,316,756,303,634,461,458,718,861,951,455,543 72,410,899,157,214,610,812 48 36,703,368,217,294,125,441,230,211,032,033,660,188,801 191,581,231,380,566,414,401 49 256,923,577,521,058,878,088,611,477,224,235,621,321,607 506,876,294,100,502,275,687 50 1,798,465,042,647,412,146,620,280,340,569,649,349,251,249 1,341,068,619,663,964,900,807 51 12,589,255,298,531,885,026,341,962,383,987,545,444,758,743 3,548,134,058,703,515,929,815 52 88,124,787,089,723,195,184,393,736,687,912,818,113,311,201 9,387,480,337,647,754,305,649 53 616,873,509,628,062,366,290,756,156,815,389,726,793,178,407 24,836,938,410,924,611,508,707 54 4,318,114,567,396,436,564,035,293,097,707,728,087,552,248,849 65,712,362,363,534,280,139,543 55 30,226,801,971,775,055,948,247,051,683,954,096,612,865,741,943 173,858,568,876,472,280,560,953 56 211,587,613,802,425,391,637,729,361,787,678,676,290,060,193,601 459,986,536,544,739,960,976,801 57 1,481,113,296,616,977,741,464,105,532,513,750,734,030,421,355,207 1,217,009,982,135,305,963,926,677 58 10,367,793,076,318,844,190,248,738,727,596,255,138,212,949,486,449 3,219,905,755,813,179,726,837,607 59 72,574,551,534,231,909,331,741,171,093,173,785,967,490,646,405,143 8,519,069,874,947,141,747,486,745 60 508,021,860,739,623,365,322,188,197,652,216,501,772,434,524,836,001 22,539,340,290,692,258,087,863,249 61 3,556,153,025,177,363,557,255,317,383,565,515,512,407,041,673,852,007 59,633,489,124,629,992,232,407,216 62 24,893,071,176,241,544,900,787,221,684,958,608,586,849,291,716,964,049 157,775,382,034,845,806,615,042,743 63 174,251,498,233,690,814,305,510,551,794,710,260,107,945,042,018,748,343 417,434,423,872,409,945,626,850,517 64 1,219,760,487,635,835,700,138,573,862,562,971,820,755,615,294,131,238,401 1,104,427,674,243,920,646,305,299,201 65 8,538,323,413,450,849,900,970,017,037,940,802,745,289,307,058,918,668,807 2,922,040,967,106,869,619,387,953,625 66 59,768,263,894,155,949,306,790,119,265,585,619,217,025,149,412,430,681,649 7,730,993,719,707,444,524,137,094,407 67 418,377,847,259,091,645,147,530,834,859,099,334,519,176,045,887,014,771,543 20,454,286,769,748,087,335,715,675,381 68 2,928,644,930,813,641,516,032,715,844,013,695,341,634,232,321,209,103,400,801 54,116,956,037,952,111,668,959,660,849 69 20,500,514,515,695,490,612,229,010,908,095,867,391,439,626,248,463,723,805,607 143,180,007,388,236,611,350,009,727,669 70 143,503,601,609,868,434,285,603,076,356,671,071,740,077,383,739,246,066,639,249 378,818,692,265,664,781,682,717,625,943 71 1,004,525,211,269,079,039,999,221,534,496,697,502,180,541,686,174,722,466,474,743 1,002,260,051,717,656,279,450,068,093,686 72 7,031,676,478,883,553,279,994,550,741,476,882,515,263,791,803,223,057,265,323,201 2,651,730,845,859,653,471,779,023,381,601 73 49,221,735,352,184,872,959,961,855,190,338,177,606,846,542,622,561,400,857,262,407 7,015,820,362,023,593,956,150,476,655,802