Anonymous user
Talk:Sequence of non-squares: Difference between revisions
n - k*k > k
(→Stability, Accuracy: Algorithm without floating point) |
(n - k*k > k) |
||
Line 29:
</pre>
: This doesn't use any floating point, and therefore isn't susceptible to rounding errors. Note that the largest number occuring in the calculation (namely k*(k+1)) isn't too much larger than n, so unless you get close to the upper end of your integer type range, you shouldn't get overflow. --[[User:Ce|Ce]] 15:33, 2 September 2008 (UTC)
:: You can rewrite it as n - k*k > k without risking integer overflow. Then k*k from the former step can be stored in order to reduce the number of multiplications down to O(sqrt(n)). So if this task is really about a sequence, i.e. n+floor(...) is not required to be programmed as a closed function, then this is looks like the most efficient solution. --[[User:Dmitry-kazakov|Dmitry-kazakov]] 17:47, 2 September 2008 (UTC)
== Zero ==
| |||