View Full Version : Is the Euclidean Algorithm actually the fastest for reducing fractions?

MorphingDragon

Oct 19, 2010, 04:29 AM

Is the Euclidean Algorithm actually the fastest for reducing fractions and related integer relations? I've seen some SE books use some strange functions but I was under the impression the the EA was the fastest.

---

And no, I didn't enter that contest I made a post about a 2 weeks ago. I decided my time would be spent better studying for my exams.

gnasher729

Oct 19, 2010, 07:52 AM

Is the Euclidean Algorithm actually the fastest for reducing fractions and related integer relations? I've seen some SE books use some strange functions but I was under the impression the the EA was the fastest.

As long as you make the right decision whether to divide or subtract. (For example 314 / 271: Subtract. 1000000000000 / 3: Divide).

jared_kipe

Oct 19, 2010, 11:41 AM

The great thing about the Euclidean algorithm is that it is very easy conceptually and can be implemented super fast in practically any language.

That and it is great because of its wide uses. I've used Euclidean algorithm in table form to:

*find Greatest common divisor / test relative primeness

*solve for base case of diophantine equations

*invert numbers in modular systems..

probably more I'm not thinking of. (all in TI-BASIC btw)

Is it the fastest method of finding GCD? Maybe not, I'm sure there have been some extraordinarily clever methods developed in the hundreds of years since Euclid, but it is usually "fast enough".

chown33

Oct 19, 2010, 12:08 PM

http://en.wikipedia.org/wiki/Euclidean_algorithm#Algorithmic_efficiency

Subheading: Efficiency of alternative methods

http://en.wikipedia.org/wiki/Binary_GCD_algorithm

jared_kipe

Oct 19, 2010, 12:28 PM

http://en.wikipedia.org/wiki/Euclidean_algorithm#Algorithmic_efficiency

Subheading: Efficiency of alternative methods

http://en.wikipedia.org/wiki/Binary_GCD_algorithm

Yay for progress eh? Making O(n^2) into O(n * (log(n))^2 * log(log(n))) over a couple hundred years.