# Re: fraction reducing funtion

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

1. ### Sam HoldenGuest

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

2. ### Buster CopleyGuest

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

3. ### Sam HoldenGuest

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