question on square root exercise (4.4.1) of ScalaByExample Classic List Threaded 6 messages 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.   ```
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. > > > >   >
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
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. > > > > >