2
$\begingroup$

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.

$\endgroup$
2

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – 1729taxi
    Jan 23 at 12:54
  • $\begingroup$ 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. $\endgroup$
    – 1729taxi
    Jan 23 at 13:13
  • $\begingroup$ You're welcome! $\endgroup$ Jan 23 at 13:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.