🚀 go-pugleaf

In article <2030@eagle.ukc.ac.uk> wabe@ukc.ac.uk (W.A.B.Evans) writes:
:In article <1992Oct26.153856.22341W@baron.edb.tih.no> tronds@edb.tih.no writes:
:>Euclid's algorithm for shortening fractions, wanted.... 
:>ya know 3/6 = 1/2... but I'm into BIG numbers here, so I need some algorithm
:>to speed things up!
:>
:	As long as the smaller of the two integers that form your quotient
:is not too large, a simple method would be to factorise that into its prime
:factors using a simple algorithm like "the sieve of Erastosthenes" (hope
 
This method is worse than hopeless.
 
All one need do is compute the GCD of the numerator and denominator. No
factoring is needed.


If the numbers are large, use the binary Euclidean algorithm. See Knuth
vol. 2, or Aho, Hopcroft, & Ullman's book on algorithms.
 
If the numbers are VERY large, you might need to use an FFT-based GCD
algorithm.

--
Bob Silverman
These are my opinions and not MITRE's.
Mitre Corporation, Bedford, MA 01730
"You can lead a horse's ass to knowledge, but you can't make him think"