Distribution of run times for Euclidean algorithm
The Endeavour 2025-04-27
Summary:
The worst case run time for the Euclidean algorithm occurs when you give the algorithm a pair of consecutive Fibonacci numbers. The algorithm takes n steps to compute the greatest common divisor of Fn+1 and Fn+2. The nth Fibonacci number is the nearest integer to φn/√5 where φ = (1 + √5)/2 is the golden ratio. […]
The post Distribution of run times for Euclidean algorithm first appeared on John D. Cook.