macOS Is the Euclidean Algorithm actually the fastest for reducing fractions?

[MorphingDragon]

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]

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]

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]

http://en.wikipedia.org/wiki/Euclidean_algorithm#Algorithmic_efficiency
Subheading: Efficiency of alternative methods

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

 

[jared_kipe]

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.