Hacker News Reader

Comment by treprinum | Hacker News Reader

Can't you use the sequence 1 + 3 + 5 + ... + 2k + 1 to get the integer square root of any integer number? It's basically the k of the nearest lower number to your number in this sequence.

View on HN

Can you explain your idea? Your algorithm is correct by definition, but doing this naively would be very slow (even for 32bit number). At this point it would be much faster to just binsearch it.

For an example of binsearch algo, I recently dipped into this while switching some code from floats to fixed point arithmetic (reducing overall wasm blob size)

https://github.com/serprex/openEtG/blob/2011007dec2616d1a24d...

Tho I could probably save binary size more by importing Math.sqrt from JS

Recently, I had reason to dig around for a fixed point square root algorithm and found this: https://groups.google.com/g/comp.lang.c/c/IpwKbw0MAxw/m/N1xh...

Better might be to use the expansion (x+y)^2=x^2+2xy+y^2 along with the observation that in any base, the square root of a 2n-digit number is at most n digits, as in the common method for calculating a square root "by hand" with pen and paper. If you did this 8 bits at a time then you only need a lookup table for roots of 8bit numbers.

And you would iterate through that sequence? That's exponential time in the bit length of the input...

It's sqrt(n) - 1 additions for the n you're trying to get the integer square root of. Memoization would make it constant time for any lesser n than the greatest n you've done this for. For greater n it's sqrt(new_big_n - prev_big_n) - 1 more additions to memoize.

You're right this isn't practical, but fun to think about. Good refresher for those out of school for a while.

Subtle detail of complexity analysis: the input is of length log(n), so taking n^k steps for any positive number k is exponential time.

And this is one of those "embarrassingly parallel" tasks.

Yes. On a desert island we can have the whole village construct this table for newton-raphson guesses.

Combined with a cutting tool attached to a worm drive we will precisely count our turns (big radius crank for extra precision!) and begin manufacture of slide rules. Can never have too many scales and this is just one we shall etch into them!

Reply on news.ycombinator.com