Tuesday, November 2, 2010

Greatest Common Divisor as a F# Function

I wrote some F# code that allows you to find the Greatest Common Divisor of two numbers. Nothing revolutionary. I tried to use recursion exclusively. I find it fun to avoid using loops in F#.


Here the functions:



let ABSOLUTE x =
        if x < 0 
        then (-x) 
        else x
;;
let MIN a b =
        if a < b
        then a
        else b
;;
let MAX a b =
        if a > b
        then a
        else b
;;
let MIN_ABS a b =
        let mutable x = a
        let mutable y = b
        if x < 0 then x <- (-x)
        if y < 0 then y <- (-y)
        if x < y
        then x
        else y
;;
let MAX_ABS a b =
        let mutable x = ABSOLUTE a
        let mutable y = ABSOLUTE b
        if x > y
        then x
        else y
;;
let rec GCD a b =
        let min = MIN_ABS a b
        let max = MAX_ABS a b
        if ( min = 0 )
        then if (max = 0)
                 then 1
                 else max
        else let leMod = max % min
             if leMod = 0
             then min
             else GCD min leMod
;;
Using the UnitTest tool that I posted in previous blog posts, I wrote some small tests for this.
let uGCD = UnitTest();
let a = 1071
let b = 462
let leGCD = GCD a b;;
uGCD.AssertIntEquals (leGCD, 21);;
let a = 0
let b = 1
let leGCD = GCD a b;;
uGCD.AssertIntEquals (leGCD, 1);;
let a = 0
let b = 0
let leGCD = GCD a b;;
uGCD.AssertIntEquals( leGCD, 1);;
let a = -1071
let b = 462
let leGCD = GCD a b;;
uGCD.AssertIntEquals (leGCD, 21);;
uGCD.Print();;
and the output would look like:

No comments:

Post a Comment