4 ms·

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 yo

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.

HPsquared 3y ago
And this is one of those "embarrassingly parallel" tasks.
- sublinear 3y ago
  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!
- deleted 3y ago
  [deleted]
maxcoder4 3y ago
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.
- __s 3y ago
  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/2011007dec2616d1a24d3de6dd7cad93478711dd/src/rs/src/aieval.rs#L17 https://github.com/serprex/openEtG/blob/2011007dec2616d1a24d... Tho I could probably save binary size more by importing Math.sqrt from JS
  - smcameron 3y ago
    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/N1xhe5n1rFoJ https://groups.google.com/g/comp.lang.c/c/IpwKbw0MAxw/m/N1xh...
atq2119 3y ago
And you would iterate through that sequence? That's exponential time in the bit length of the input...
- sublinear 3y ago
  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.
  - klyrs 3y ago
    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.
tomatocracy 3y ago
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.

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.

HPsquared 3y ago

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

sublinear 3y ago
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!
deleted 3y ago
[deleted]

maxcoder4 3y ago

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.

__s 3y ago
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/2011007dec2616d1a24d3de6dd7cad93478711dd/src/rs/src/aieval.rs#L17 https://github.com/serprex/openEtG/blob/2011007dec2616d1a24d... Tho I could probably save binary size more by importing Math.sqrt from JS
- smcameron 3y ago
  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/N1xhe5n1rFoJ https://groups.google.com/g/comp.lang.c/c/IpwKbw0MAxw/m/N1xh...

atq2119 3y ago

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

sublinear 3y ago
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.
- klyrs 3y ago
  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.

tomatocracy 3y ago

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.