
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.scalalang.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.220446049250313E16 math.ulp(10d) > 1.7763568394002505E15 math.ulp(100d) > 1.4210854715202004E14 math.ulp(1000d) > 1.1368683772161603E13 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 nontermination for very large ones (why?). > Design a different version of isGoodEnough which does not have these problems. > > > > > 
Hi,
See also the paper "What Every Computer Scientist Should Know About FloatingPoint Arithmetic" (1991) Reprinted by Sun: http://dlc.sun.com/pdf/8007895/8007895.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.scalalang.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.220446049250313E16 > math.ulp(10d) > 1.7763568394002505E15 > math.ulp(100d) > 1.4210854715202004E14 > math.ulp(1000d) > 1.1368683772161603E13 > > 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 nontermination 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)670948676 http://hsyl20.fr 
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, 
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. 
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 nontermination for very large ones (why?). > Design a different version of isGoodEnough which does not have these > problems. > > > > > 
Free forum by Nabble  Scala Resume Examples  Edit this page 