question on square root exercise (4.4.1) of ScalaByExample

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

question on square root exercise (4.4.1) of ScalaByExample

Tim Bosschaerts
I am trying to complete exercise 4.4.1 of the ScalaByExample pdf.
To solve the problem for small numbers, I would just increase the precision in the isGoodEnoug() function (e.g. 0.0000001 instead of 0.01)
But I don't see what the problem is with the large Number or how to fix it?

Anyone got an answer for this newbie question?



// Exercise

def
square(x: Double) = x*x

def abs(x: Double) = if (x>0) x else -x
def isGoodEnough(guess: Double, x: Double ) =
  abs(square(guess)-x) < 0.001

def improve(guess: Double, x: Double) =
  (guess + x/guess ) / 2
def sqrtIter(guess: Double, x: Double) : Double =
  if (isGoodEnough(guess, x) ) guess
  else sqrtIter(improve(guess,x) , x)
def sqrt(x: Double) = sqrtIter(1.0, x)

Exercise 4.4.1 The isGoodEnough test is not very precise for small numbers and might lead to non-termination for very large ones (why?).
Design a different version of isGoodEnough which does not have these problems.
 
Reply | Threaded
Open this post in threaded view
|

Re: question on square root exercise (4.4.1) of ScalaByExample

Andreas Flierl
Hi,

try this one:

def isGoodEnough2(guess: Double, x: Double) = abs(square(guess) - x) <= math.ulp(x)

you should study how floating point numbers work. this could help:
http://en.wikipedia.org/wiki/Floating_point#Accuracy_problems

also consult:
http://www.scala-lang.org/api/current/scala/math/package.html

and (here, ulp is explained):
http://download.oracle.com/javase/6/docs/api/java/lang/Math.html

in short:
the smallest distance between two representable floating point number increases as their value increases. scala.math.ulp(...) can help measure that.

e.g. this:
  math.ulp(1d)    -> 2.220446049250313E-16
  math.ulp(10d)   -> 1.7763568394002505E-15
  math.ulp(100d)  -> 1.4210854715202004E-14
  math.ulp(1000d) -> 1.1368683772161603E-13

hope this helped
Andreas

Am 22.09.2010 um 11:41 schrieb Tim Bosschaerts:

> I am trying to complete exercise 4.4.1 of the ScalaByExample pdf.
> To solve the problem for small numbers, I would just increase the precision in the isGoodEnoug() function (e.g. 0.0000001 instead of 0.01)
>
>
> But I don't see what the problem is with the large Number or how to fix it?
>
>
> Anyone got an answer for this newbie question?
>
>
>
> // Exercise
>
> def square(x: Double) = x*x
>
>
>
>
> def abs(x: Double) = if (x>0) x else -x
>
>
>
> def isGoodEnough(guess: Double, x: Double ) =
>
>   abs(square(guess)-x) < 0.001
>
>
> def improve(guess: Double, x: Double) =
>
>
>
>   (guess + x/guess ) / 2
>
> def sqrtIter(guess: Double, x: Double) : Double =
>
>
>
>   if (isGoodEnough(guess, x) ) guess
>
>   else sqrtIter(improve(guess,x) , x)
>
> def sqrt(x: Double) = sqrtIter(1.0, x)
>
>
> Exercise 4.4.1 The isGoodEnough test is not very precise for small numbers and might lead to non-termination for very large ones (why?).
> Design a different version of isGoodEnough which does not have these problems.
>
>
>
>  
>

Reply | Threaded
Open this post in threaded view
|

Re: question on square root exercise (4.4.1) of ScalaByExample

Sylvain HENRY-2
  Hi,
See also the paper "What Every Computer Scientist Should Know About
Floating-Point Arithmetic" (1991)
Reprinted by Sun: http://dlc.sun.com/pdf/800-7895/800-7895.pdf

Cheers,
Sylvain

Le 22/09/2010 13:48, Andreas Flierl a écrit :

> Hi,
>
> try this one:
>
> def isGoodEnough2(guess: Double, x: Double) = abs(square(guess) - x)<= math.ulp(x)
>
> you should study how floating point numbers work. this could help:
> http://en.wikipedia.org/wiki/Floating_point#Accuracy_problems
>
> also consult:
> http://www.scala-lang.org/api/current/scala/math/package.html
>
> and (here, ulp is explained):
> http://download.oracle.com/javase/6/docs/api/java/lang/Math.html
>
> in short:
> the smallest distance between two representable floating point number increases as their value increases. scala.math.ulp(...) can help measure that.
>
> e.g. this:
>    math.ulp(1d)    ->  2.220446049250313E-16
>    math.ulp(10d)   ->  1.7763568394002505E-15
>    math.ulp(100d)  ->  1.4210854715202004E-14
>    math.ulp(1000d) ->  1.1368683772161603E-13
>
> hope this helped
> Andreas
>
> Am 22.09.2010 um 11:41 schrieb Tim Bosschaerts:
>
>> I am trying to complete exercise 4.4.1 of the ScalaByExample pdf.
>> To solve the problem for small numbers, I would just increase the precision in the isGoodEnoug() function (e.g. 0.0000001 instead of 0.01)
>>
>>
>> But I don't see what the problem is with the large Number or how to fix it?
>>
>>
>> Anyone got an answer for this newbie question?
>>
>>
>>
>> // Exercise
>>
>> def square(x: Double) = x*x
>>
>>
>>
>>
>> def abs(x: Double) = if (x>0) x else -x
>>
>>
>>
>> def isGoodEnough(guess: Double, x: Double ) =
>>
>>    abs(square(guess)-x)<  0.001
>>
>>
>> def improve(guess: Double, x: Double) =
>>
>>
>>
>>    (guess + x/guess ) / 2
>>
>> def sqrtIter(guess: Double, x: Double) : Double =
>>
>>
>>
>>    if (isGoodEnough(guess, x) ) guess
>>
>>    else sqrtIter(improve(guess,x) , x)
>>
>> def sqrt(x: Double) = sqrtIter(1.0, x)
>>
>>
>> Exercise 4.4.1 The isGoodEnough test is not very precise for small numbers and might lead to non-termination for very large ones (why?).
>> Design a different version of isGoodEnough which does not have these problems.
>>
>>
>>
>>
>>


--
Sylvain HENRY
PhD Student INRIA/LaBRI RunTime Team
Tel: +33 (0)6-70-94-86-76
http://hsyl20.fr

Reply | Threaded
Open this post in threaded view
|

Re: question on square root exercise (4.4.1) of ScalaByExample

Piotr Tarsa
In reply to this post by Andreas Flierl
1 ulp is usually too low value for most approximations. Have you tried that code? I'm pretty sure it will settle in an infinite loop with such small error margin.

2010/9/22 Andreas Flierl <[hidden email]>
Hi,

try this one:

def isGoodEnough2(guess: Double, x: Double) = abs(square(guess) - x) <= math.ulp(x)

you should study how floating point numbers work. this could help:
http://en.wikipedia.org/wiki/Floating_point#Accuracy_problems

also consult:
http://www.scala-lang.org/api/current/scala/math/package.html

and (here, ulp is explained):
http://download.oracle.com/javase/6/docs/api/java/lang/Math.html

in short:
the smallest distance between two representable floating point number increases as their value increases. scala.math.ulp(...) can help measure that.

e.g. this:
 math.ulp(1d)    -> 2.220446049250313E-16
 math.ulp(10d)   -> 1.7763568394002505E-15
 math.ulp(100d)  -> 1.4210854715202004E-14
 math.ulp(1000d) -> 1.1368683772161603E-13

hope this helped
Andreas

Am 22.09.2010 um 11:41 schrieb Tim Bosschaerts:

> I am trying to complete exercise 4.4.1 of the ScalaByExample pdf.
> To solve the problem for small numbers, I would just increase the precision in the isGoodEnoug() function (e.g. 0.0000001 instead of 0.01)
>
>
> But I don't see what the problem is with the large Number or how to fix it?
>
>
> Anyone got an answer for this newbie question?
>
>
>
> // Exercise
>
> def square(x: Double) = x*x
>
>
>
>
> def abs(x: Double) = if (x>0) x else -x
>
>
>
> def isGoodEnough(guess: Double, x: Double ) =
>
>   abs(square(guess)-x) < 0.001
>
>
> def improve(guess: Double, x: Double) =
>
>
>
>   (guess + x/guess ) / 2
>
> def sqrtIter(guess: Double, x: Double) : Double =
>
>
>
>   if (isGoodEnough(guess, x) ) guess
>
>   else sqrtIter(improve(guess,x) , x)
>
> def sqrt(x: Double) = sqrtIter(1.0, x)
>
>
> Exercise 4.4.1 The isGoodEnough test is not very precise for small numbers and might lead to non-termination for very large ones (why?).
> Design a different version of isGoodEnough which does not have these problems.
>
>
>
>
>


Reply | Threaded
Open this post in threaded view
|

Re: question on square root exercise (4.4.1) of ScalaByExample

Andreas Flierl

Piotr Tarsa wrote:
> 1 ulp is usually too low value for most approximations. Have you tried that code? I'm pretty sure it will settle in an infinite loop with such small error margin.

Yep, I've tried that code, although I didn't test it extensively. Neither did I think his algorithm through, but if the approximation minimizes the error with every iteration, it should not be a problem.
Reply | Threaded
Open this post in threaded view
|

Re: question on square root exercise (4.4.1) of ScalaByExample

Ruediger Keller-2
In reply to this post by Tim Bosschaerts
Well currently you are testing for an absolute error. What you usually
want to do is test for a relative error, along these lines:

def isGoodEnough(guess: Double, x: Double ) = abs(square(guess) - x) /
abs(x) < 0.001

But beware of devide by zero and also you might need to adjust the
allowed margin of error (here 0.001).

Regards,
Ruediger


2010/9/22 Tim Bosschaerts <[hidden email]>:

> I am trying to complete exercise 4.4.1 of the ScalaByExample pdf.
> To solve the problem for small numbers, I would just increase the precision
> in the isGoodEnoug() function (e.g. 0.0000001 instead of 0.01)
>
>
> But I don't see what the problem is with the large Number or how to fix it?
>
> Anyone got an answer for this newbie question?
>
>
>
> // Exercise
>
> def square(x: Double) = x*x
>
>
> def abs(x: Double) = if (x>0) x else -x
>
>
> def isGoodEnough(guess: Double, x: Double ) =
>   abs(square(guess)-x) < 0.001
>
> def improve(guess: Double, x: Double) =
>
>   (guess + x/guess ) / 2
>
> def sqrtIter(guess: Double, x: Double) : Double =
>
>   if (isGoodEnough(guess, x) ) guess
>   else sqrtIter(improve(guess,x) , x)
>
> def sqrt(x: Double) = sqrtIter(1.0, x)
>
> Exercise 4.4.1 The isGoodEnough test is not very precise for small numbers
> and might lead to non-termination for very large ones (why?).
> Design a different version of isGoodEnough which does not have these
> problems.
>
>
>
>
>