wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> beginner qn - algorithm to simplify a fraction
        
(Message started by: Valerfore on Aug 26^th, 2004, 1:15am)

Title: beginner qn - algorithm to simplify a fraction
Post by Valerfore on Aug 26^th, 2004, 1:15am

Hi all

I hope this question doesnt insult your intelligence :P
given a fraction, say 6/12, how do you simplify it to its simplest term, 1/2?

Im a beginner cs student so would appreciate your help!

Title: Re: beginner qn - algorithm to simplify a fraction
Post by towr on Aug 26^th, 2004, 1:33am

::[hide]divide both sides by their greatest common divisor
I think Euclid had a nice algorithm to find it..
[/hide]::

Title: Re: beginner qn - algorithm to simplify a fraction
Post by John_Gaughan on Sep 7^th, 2004, 8:13am

Can you find an algorithm that has a faster theta or omega time (not necessarily O()) than the one towr mentioned? There are algorithms that are faster in certain circumstances...