Talk:Shifting nth-root algorithm

From Wikipedia, the free encyclopedia

[edit] Useless?

so it follows that this algorithm is completely useless, as it is always outperformed by much simpler binary search, and has the same memory complexity.

Yet it is even mentioned in some dictionaries... could it be that the pencil and paper time complexity is different, compared to a binary search? 82.139.85.33 20:50, 20 August 2006 (UTC)

It can be faster on pencil and paper than binary search because it goes one digit at a time, so the size of the numbers involved is smaller, so it's easier for limited human short-term memory. -Andrea Persephone 22:29, 21 August 2006 (UTC)

Also, there are some problematic assumptions. In computers small products and additions have more like O(1) computation time thanks to them being implemented with optimized HW rather than a digit/bit at a time. (And very large products are better than O(n²) as well). --Jake 18:16, 24 October 2006 (UTC)