Re:Did any processor implement an integer square root instru...
by treprinum on Sunday April 07, 2024 @08:20AM
(#39960252)
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.
[ Parent
| on HN ]
Re:Did any processor implement an integer square root instru...
by maxcoder4 on Sunday April 07, 2024 @09:03AM
(#39960485)
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.
Re:Did any processor implement an integer square root instru...
by __s on Sunday April 07, 2024 @09:46AM
(#39960744)
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
Re:Did any processor implement an integer square root instru...
by smcameron on Sunday April 07, 2024 @03:26PM
(#39963103)
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...
Re:Did any processor implement an integer square root instru...
by tomatocracy on Sunday April 07, 2024 @11:07AM
(#39961253)
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.
Re:Did any processor implement an integer square root instru...
by atq2119 on Sunday April 07, 2024 @09:39AM
(#39960695)
And you would iterate through that sequence? That's exponential time in the bit length of the input...
Re:Did any processor implement an integer square root instru...
by sublinear on Sunday April 07, 2024 @09:57AM
(#39960801)
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.
Re:Did any processor implement an integer square root instru...
by klyrs on Sunday April 07, 2024 @01:32PM
(#39962276)
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.
Re:Did any processor implement an integer square root instru...
by HPsquared on Sunday April 07, 2024 @08:31AM
(#39960312)
And this is one of those "embarrassingly parallel" tasks.
Re:Did any processor implement an integer square root instru...
by sublinear on Sunday April 07, 2024 @10:16AM
(#39960922)
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!