Fast Integer Square Roots of known perfect squares?

Question

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.

Answer 1

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.