Re: fraction reducing funtion

Discussion in 'C++' started by Sam Holden, Aug 3, 2003.

  1. Sam Holden

    Sam Holden Guest

    On Sun, 03 Aug 2003 20:13:09 GMT, Luis <> wrote:
    > I am writing a fraction class which involves reducing fractions, and i can't
    > think of a way to do this. I know that i will have to check if 2% x is 0,
    > and do the same for 3, 5, and 7, but after this i don't know what to do. I
    > can only use variables, and functions, no arrays or any thing past this, can
    > any one help me out?


    Find the greatest common divisor of the numerator and denominator. Divide
    both by it.

    Euclid's algorithm from circa 300BC is the way math students learn it.
    Though there's a "binary" version published in 1967 (that's a long time
    between algorithm tweaks :) which replaces the divisions with right
    shifts.

    You can also factorise and remove the primes that appear in both
    the numerator and denominator, but that would be very inneficient.

    Search for "gcd algorithm" and you'll find numerous explanations,
    add "euclid" to avoid the polynomial ones.

    --
    Sam Holden
    Sam Holden, Aug 3, 2003
    #1
    1. Advertising

  2. Sam Holden wrote:
    ....
    > Search for "gcd algorithm" and you'll find numerous explanations,
    > add "euclid" to avoid the polynomial ones.


    Euclid's algorithm applies to polynomials too, I'm afraid. The ring
    of polynomials over any field is a Euclidean domain.

    Regards,
    Buster
    Buster Copley, Aug 4, 2003
    #2
    1. Advertising

  3. Sam Holden

    Sam Holden Guest

    On Mon, 04 Aug 2003 05:04:18 +0100, Buster Copley <> wrote:
    > Sam Holden wrote:
    > ...
    >> Search for "gcd algorithm" and you'll find numerous explanations,
    >> add "euclid" to avoid the polynomial ones.

    >
    > Euclid's algorithm applies to polynomials too, I'm afraid. The ring
    > of polynomials over any field is a Euclidean domain.


    Yes, but my quick experiment found that adding "euclid" moved a couple
    of good links, with nice psuedo code to the top of the pile, above
    the irrelevant (for this task) ones referencing polynomials.

    --
    Sam Holden
    Sam Holden, Aug 4, 2003
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Jam
    Replies:
    2
    Views:
    729
  2. Peter

    String Fraction to Number

    Peter, May 6, 2004, in forum: Java
    Replies:
    6
    Views:
    1,025
    Mason Bryant
    May 6, 2004
  3. Replies:
    4
    Views:
    381
    Guillaume
    Nov 20, 2005
  4. garyolsen

    Virtual Funtion Questions

    garyolsen, Dec 2, 2003, in forum: C++
    Replies:
    3
    Views:
    1,200
    jeffc
    Dec 2, 2003
  5. Lee Xuzhang
    Replies:
    5
    Views:
    324
    Kevin D. Quitt
    Jun 14, 2006
Loading...

Share This Page