# question on square root exercise (4.4.1) of ScalaByExample Classic List Threaded 6 messages Reply | Threaded
Open this post in threaded view
|

## question on square root exercise (4.4.1) of ScalaByExample

 ```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

 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_problemsalso consult: http://www.scala-lang.org/api/current/scala/math/package.htmland (here, ulp is explained): http://download.oracle.com/javase/6/docs/api/java/lang/Math.htmlin 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

 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.pdfCheers, 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

 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 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

 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

 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. > > > > >