Talk:Sequence of non-squares: Difference between revisions

Content added Content deleted

Inline

Revision as of 13:30, 24 August 2008

I chose this as a way to show how easy it is to investigate functions in a programming language. --Paddy3118 08:42, 24 August 2008 (UTC)

Stability, Accuracy

The formula need to be investigated for numeric stability. Calculation of sqrt is inexact, it need to be shown that for all n in question, floor(1/2 + sqrt(n)) yields the exact result. A minimal requirement for this (though insufficient, I guess) is that sqrt has an error below 0.5. Note that the addition following to squaring will normalize for big n. Also conversion of those to floating point becomes quickly inexact when 32-bit floats are used. --Dmitry-kazakov 09:51, 24 August 2008 (UTC)

I suggest they choose/use the precision that gives correct results over the stated range, or reduce the range to suit the precision they have and add a comment. I think its true that most languages on Rosetta supporting floating point also support more than 32 bit FP values. --Paddy3118 11:28, 24 August 2008 (UTC)

Maybe it would be better to require an implementation not to use floating-point at all. I mean that m=floor(1/2 + sqrt(n)) should be solved iteratively using, say Newton method, in integers. That would guaranty that rounding error do not mangle the result. The case arises when sqrt(n) lands into the interval m.49999..m.50001. This is instable if the precision of floating-point numbers is 0.0001, because one cannot decide whether the floor of + 0.5 were m or m+1. Mathematically, for any given precision of floating-point numbers, there exist an infinite number of n, such that sqrt(n) is in the interval like above. There exist algorithms for integer sqrt(n) defined as the integer lower bound of real sqrt(n). One could modify them for 0.5+sqrt(n), that would be the cleanest way.

I have just noticed that there is a typo error in the task name: "sequance" instead of "sequence". --Dmitry-kazakov 13:30, 24 August 2008 (UTC)

Zero

I thought we were in the realm of Number Theory where Wikipedia states they don't include zero as a natural number, so went with the term Natural Number, but the term Positive Integer might be more exact. --Paddy3118 11:36, 24 August 2008 (UTC)

@@ Line 4: / Line 4: @@
 :I suggest they choose/use the precision that gives correct results over the stated range, or reduce the range to suit the precision they have and add a comment. I think its true that most languages on Rosetta supporting floating point also support more than 32 bit FP values. --[[User:Paddy3118|Paddy3118]] 11:28, 24 August 2008 (UTC)
+::Maybe it would be better to require an implementation not to use floating-point at all. I mean that m=floor(1/2 + sqrt(n)) should be solved iteratively using, say Newton method, in integers. That would guaranty that rounding error do not mangle the result. The case arises when sqrt(n) lands into the interval m.49999..m.50001. This is instable if the precision of floating-point numbers is 0.0001, because one cannot decide whether the floor of + 0.5 were m or m+1. Mathematically, for any given precision of floating-point numbers, there exist an infinite number of n, such that sqrt(n) is in the interval like above. There exist algorithms for integer sqrt(n) defined as the integer lower bound of real sqrt(n). One could modify them for 0.5+sqrt(n), that would be the cleanest way.
+::I have just noticed that there is a typo error in the task name: "sequance" instead of "sequence". --[[User:Dmitry-kazakov|Dmitry-kazakov]] 13:30, 24 August 2008 (UTC)
 == Zero ==