News for hackers. Stuff that matters.
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.