Talk:Sequence of non-squares: Difference between revisions
→Stability, Accuracy: Algorithm without floating point
(→Stability, Accuracy: Algorithm without floating point) |
|||
Line 10:
:::Whoops! I have [http://www.rosettacode.org/wiki/User_talk:Spoon! asked]. --[[User:Paddy3118|Paddy3118]] 13:56, 24 August 2008 (UTC)
: The best way to avoid numerical instability is of course to remain integer all the time. My thoughts to this:
: Let's assume that k is the largest integer so that k^2 <= n. Then it's obvious that sqrt(n) = k + x, where 0 <= x < 1.
: Therefore:
:* floor(1/2 + sqrt(n)) = k if x < 1/2, i.e. n < (k + 1/2)^2 = k^2 + k + 1/4. Since n and k are integers, this simplifies to n <= k^2 + k = k(k+1).
:* floor(1/2 + sqrt(n)) = k+1 otherwise.
: Maintaining k is quite simple: Since our n grows one by one, we just have to increment k as soon as n==(k+1)^2. Looking again at it, one sees that this can be further optimized: Since we need k+1 as soon as we are larger than k(k+1), we can just use that condition (which we would have to check anyway) for incrementing k. Therefore the algorithm would go like this (untested)
<pre>
n := 1, k := 1
proposition_is_right := true
while (n <= 1000000)
result := n + k
if (result is square)
proposition_is_right := false
n := n + 1
if (n > k*(k+1))
k := k + 1
</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)
== Zero ==
| |||