Talk:Sequence of non-squares: Difference between revisions
Content added Content deleted
(n - k*k > k) |
(→Stability, Accuracy: products can be completely eliminated; clarify task?) |
||
| Line 31: | Line 31: | ||
:: 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) |
:: 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) |
||
::: Well, using that (k+1)^2 = k^2 + 2k + 1, you can even completely eliminate all multiplications. However the stated goal of the task (see top of discussion page) was "to show how easy it is to investigate functions in a programming language." So while this algorithm is certainly a solution of the task (well, printing out some values is missing) avoiding the numeric problems, I'm not sure if it isn't against the idea of the task. Maybe a clarification of the task would be a good idea. --[[User:Ce|Ce]] 07:36, 3 September 2008 (UTC) |
|||
== Zero == |
== Zero == |
||