# Fast Integer Square Roots of known perfect squares?

A bit of a generic question perhaps - say I have a list of non-negative integers and I know each are perfect squares - what is a fast way of finding their square roots? I have very long lists (millions of elements) and the numbers range from say 0 to 100,000 or so? The inbuilt Sqrt[] function is not particularly fast.

• This might be relevant mathematica.stackexchange.com/q/165041/9469 Jan 23 at 12:34
• Thanks. I actually saw that but though faster it still seemed quite slow. Jan 23 at 13:13

Use a lookup table:

m = 1000;
n = 1000000;
ClearAll[f];
f = AssociationThread[Range[0, m]^2, Range[0, m]];
a = RandomInteger[{0, 1000}, n]^2;

b = Lookup[f, a]; // RepeatedTiming // First
Max[Abs[a - b^2]]


0.115421

0

Using a sparse vector seem to be a bit more efficient:

sv = SparseArray[Partition[Range[0, m]^2 + 1, 1] -> Range[0, m]];
b = sv[[a + 1]]; // RepeatedTiming
Max[Abs[a - b^2]]


0.0387735

0

If the maximum square is not too large, a plain array can also serve as lookup table (but is basically a waste of space):

v = Normal[sv];
b = v[[a + 1]]; // RepeatedTiming // First
Max[Abs[a - b^2]]


0.00675104

0

Or (apparently much faster) convert to doubles and round afterwards:

b = Round[Sqrt[N[a]]]; // RepeatedTiming // First
Max[Abs[a - b^2]]


0.00246308

0

The last variant is probably the best as it is the least memory bound one. It leverages that square roots of doubles are implemented in hardware nowadays.

• Yeah, I thought about a lookup table but was too lazy on a Sunday morning to code it up. I know - that's beyond lazy. Jan 23 at 12:54
• Thanks for that last one especially - something like that was crossing my mind but on thinking about it I didn't pursue it. I doubt that can be much improved upon. The reason this came up is I was trying to do PowersRepresentations faster using IntegerPartitions - which is far faster but the output gives me the squares of the numbers and I need their square roots. Jan 23 at 13:13
• You're welcome! Jan 23 at 13:23