Newton’s iterations is an algorithm for computing the square root of a number n. It also makes a nice “Hello World” program if you find yourself doing a lot of optimization. Here is how it looks in Haskell, Clojure and Scala
Haskell
1
2
3
4
5
6
7
8 update y x = 0.5 * ( x + y / x )
foo = ( iterate ( update 100 ) 1000 )
foobar = zip foo ( tail foo )
notconverged tol x = if ( abs ( a - b ) / abs ( b ) > tol ) then True else False
where
a = fst x
b = snd x
map ( \ x -> fst x ) $ takeWhile ( notconverged ( 0.000001 )) foobar
Clojure
1
2
3
4
5
6 ( use ' ( incanter core stats charts io ))
( defn sqroot [ y x ] ( * 0.5 ( + x ( / y x ))))
( def updater ( partial sqroot 16 ))
( defn converged? [ x ] ( > ( abs ( - ( first x ) ( last x ))) 0.0000001 ))
( map ( fn [ x ] ( first x )) ( take-while converged? ( partition 2 1 ( iterate updater 100 ))))
Scala
1
2
3
4
5
6
7
8
9
10
11
12
13
14 import breeze.numerics.abs
def UpdateCurry ( r : Double )( x : Double ) = 0.5 *( x + r / x )
val tolerance = 0.0000001
val desiredSQRoot = 16
val Update = UpdateCurry ( desiredSQRoot ) _
val iterates = Iterator . iterate ( 1.0 ) { x => Update ( x ) }
def ConvergedCurry ( tol : Double )( x : Seq [ Double ]) : Boolean = abs ( x ( 0 )- x ( 1 ))/ abs ( x ( 0 ))< tol
val Converged = ConvergedCurry ( tolerance ) _
val trace = iterates . sliding ( 2 ). takeWhile ( x => ! Converged ( x )). toList
Leave a Comment