Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 FloorSqrt

Source Notebook

Find the integer square root of a positive integer

Contributed by: Daniel Lichtblau

ResourceFunction["FloorSqrt"][n]

computes the floor-integer square root of positive integer n.

Details

The integer square root of a positive integer n is defined to be the floor of .
If s=ResourceFunction["FloorSqrt"][n] then s2<=n<(s+1)2.
It is often referred to as the isqrt function.

Examples

Basic Examples (2) 

Compute the floor of the square root for an integer:

In[1]:=
int = 293; fsq = ResourceFunction["FloorSqrt"][int]
Out[2]=

Check that it is correct:

In[3]:=
fsq^2 <= int < (fsq + 1)^2
Out[3]=

Properties and Relations (3) 

If n is a square then FloorSqrt[n]==Sqrt[n]:

In[4]:=
Table[Sqrt[j^2] == ResourceFunction["FloorSqrt"][j^2], {j, 10, 20}]
Out[4]=

For large n, FloorSqrt is typically much faster to compute than Sqrt:

In[5]:=
n = 10^1000000 - 3^2095903; t1 = First[AbsoluteTiming[sn1 = Floor[Sqrt[n]]]]; t2 = First[AbsoluteTiming[sn2 = ResourceFunction["FloorSqrt"][n]]]; {t1, t2, sn1 == sn2}
Out[6]=

Here is an asymptotically fast divide-and-conquer code based on Zimmermann's Karatsuba method:

In[7]:=
iSqrt[a_, baselen_ : 10] := Catch[Module[{quarterscale = Ceiling[RealExponent[a, 2.]/4], aUpper, aLower, sqrt, diff}, If[quarterscale < baselen, Throw[Floor[Sqrt[N[a, 2*baselen + 4]]]]]; aUpper = BitShiftRight[a, 2*quarterscale]; aLower = a - BitShiftLeft[aUpper, 2*quarterscale]; sqrt = BitShiftLeft[iSqrt[aUpper, baselen], quarterscale]; sqrt += Quotient[aLower, (2*sqrt)]; diff = a - sqrt^2; While[Abs[diff] >= 2 sqrt + 1 || diff < 0, sqrt += Quotient[diff, (2*sqrt)]; diff = a - sqrt^2;]; sqrt]]

Compare speed to FloorSqrt on a large input:

In[8]:=
n = 10^10000000 - 3^2095903; t1 = First[AbsoluteTiming[sn1 = ResourceFunction["FloorSqrt"][n]]]; t2 = First[AbsoluteTiming[sn2 = iSqrt[n]]]; {t1, t2, sn1 == sn2}
Out[9]=

Possible Issues (2) 

FloorSqrt only supports positive integers:

In[10]:=
ResourceFunction["FloorSqrt"][7.1]
Out[10]=

Use Floor to convert the input to an integer before using FloorSqrt:

In[11]:=
ResourceFunction["FloorSqrt"][Floor[7.1]]
Out[11]=

Requirements

Wolfram Language 13.0 (December 2021) or above

Version History

  • 1.0.0 – 12 June 2024

Source Metadata

  • Citation:

Related Resources

License Information