Brendan Younger

Math visualizations

How many iterations does gcd(x, y) take?

Iterations of gcd(x, y) on the z-axis

A theorem of Lamé, Dixon, and Heilbronn states that the average number of iterations of the classical GCD function is

12 ln(2)π2ln(max(x,y))\frac{12~\mathrm{ln}(2)}{\pi^2} \mathrm{ln}(\mathrm{max}(x, y))

and the maximum is given by

⌈ln(N5)/ln((1+5)/2)⌉−2\lceil \mathrm{ln}(N \sqrt{5}) / \mathrm{ln}((1 + \sqrt{5}) / 2)\rceil - 2
  • Show maximumStair step upper bound
  • Show averageSmooth middle surface
  • Show iterationsSpiky surface in the middle