Velocity Reviews > C++ > Re: fraction reducing funtion

# Re: fraction reducing funtion

Sam Holden
Guest
Posts: n/a

 08-03-2003
On Sun, 03 Aug 2003 20:13:09 GMT, Luis <(E-Mail Removed)> 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

Buster Copley
Guest
Posts: n/a

 08-04-2003
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

Sam Holden
Guest
Posts: n/a

 08-04-2003
On Mon, 04 Aug 2003 05:04:18 +0100, Buster Copley <(E-Mail Removed)> 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