Friday, 13 September 2013

Conversion of a fraction to its lowest form

Doing this is really simple.
Consider a fraction represented as (numerator) / (denominator). To reduce it to its lowest form, divide both - numerator and denominator - by the GCD (Greatest Common Divisor) of the numerator and the denominator.

To find the GCD, Euclid's algorithm works really fast.

Here's the pseudo-code to find the GCD:

function gcd(a, b)
    while b ≠ 0
       t := b
       b := a mod t
       a := t
    return a