Back to Questions
3.1k
views6
comments
Newton-Raphson square root
f#functional

Hi,

Below is my implementation of the Newton-Raphson square root function from John Huges' "Why functional programming matters" ([link:www.cs.chalmers.se]) (pages 9, 10, 11)

1
2
3
4
5
6
7
8
9
10
11

let next N (x:float) = (x + N/x) / 2.0

let rec repeat f a = a :: (repeat f (f a))

let rec within (eps : float)  = function
    | a :: b :: rest when (abs (a - b)) <= eps -> second
    | x -> within eps (List.tail x)

let newton_square a0 eps N = within eps (repeat (next N) a0)

newton_square 16.0 0.001 16.0

this doesn't work, however. I kept getting StackOverflowException. I assume it has to do with the infinite list, but I don't know how to remedy this.

-k

.

If you want to do infinite lists with pattern matching, you should use the LazyList class in the PowerPack:

[link:fsharppowerpack.codeplex.com]

By on 5/8/2010 10:28 AM ()

Thank you. I looked into PowerPack's LazyList.. but this function returns an error..

1

let rec repeat f a = LazyList.cons(a, (repeat f (f a)))
1
2
3
4
5

 error FS0001: Type mismatch. Expecting a
    'a    
but given a
    LazyList<'b * 'a> -> LazyList<'b * 'a>    
The resulting type would be infinite when unifying ''a' and 'LazyList<'b * 'a> -> LazyList<'b * 'a>'

what should I do?

By on 5/8/2010 11:50 AM ()

This appears to work:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

 

open Microsoft.FSharp.Collections.LazyList 

let next N (x:float) = (x + N/x) / 2.0

let rec repeat f a = 
    LazyList.consDelayed a (fun() -> repeat f (f a))

let rec within (eps : float)  = function
    | LazyList.Cons(a, LazyList.Cons(b, rest)) when (abs (a - b)) <= eps -> b
    | x -> within eps (LazyList.tail x)

let newton_square a0 eps N = within eps (repeat (next N) a0)

printfn "%A" (newton_square 16.0 0.001 16.0)

Note that consDelayed prevents the immediate infinite recursion by wrapping a lambda thunk around the recursive call.

By on 5/8/2010 3:01 PM ()

Wow, Thanks a lot for letting me pick your brain, Brian (anagram!!). That was really helpful.

I chewed further and got another StackOverflow exception with the numerical integration... I'm not sure what is causing the trouble here...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

 
open Microsoft.FSharp.Collections.LazyList 

let rec within (eps : float)  = function
    | LazyList.Cons(a, LazyList.Cons(b, rest)) when (abs (a - b)) <= eps -> b
    | x -> within eps (LazyList.tail x)

let easyintegrate f a b = (f a + f b) * (b - a) / 2.0

let rec integrate f a b = 
    let mid = (a + b) / 2.0
    let addpair x = fst x + snd x
    LazyList.cons (easyintegrate f a b) (LazyList.map addpair (LazyList.zip (integrate f a mid) (integrate f mid b)))
let numerical_integration f a b eps = within eps (integrate f a b)

numerical_integration (fun x -> x**2.0 - 3.0 * x +  2.0) 1.0 5.0 0.001
By on 5/8/2010 5:57 PM ()

As before, change

LazyList.cons x y

to

LazyList.consDelayed x (fun () -> y)

By on 5/8/2010 11:49 PM ()

Thank you. It works wonder.

By on 5/9/2010 7:49 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper