This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author mark.dickinson facundobatista, gvanrossum, jyasskin, mark.dickinson, ncoghlan, rhettinger 2008-02-22.01:02:52 0.17466168 No <1203642178.48.0.287035349797.issue1682@psf.upfronthosting.co.za>
Content
```> Okay.  I'll stop now :)

So I lied.  In a spirit of enquiry, I implemented math.gcd, and wrote a
script (lehmer_gcd.py, attached) to produce some relative timings.  Here
are the results, on my MacBook Pro (OS X 10.5):

An explanation of the table:  I'm computing gcd(a, b) for randomly
chosen a and b with a_digits and b_digits decimal digits, respectively.
The times in the 5th and 6th columns are in seconds; the last column
gives the factor by which math.gcd is faster than the direct Euclidean
Python implementation.

Even for quite small a and b, math.gcd(a, b) is around 10 times faster
than its Python counterpart.  For large, roughly equal-sized, a and b,
the C version runs over 30 times faster.

The smallest difference occurs when the two arguments are very different
sizes;  then both versions of gcd essentially do one time-consuming
divmod, followed by a handful of tiny operations, so they take
essentially the same time.  For Fraction, the arguments will tend to be
around equal size for many applications:  this assumes that the actual
real number represented by the Fraction is within a sensible range, even
when the numerator and denominator have grown huge.

For random a and b, gcd(a, b) tends to be very small.  So for the last
few entries in the table, the gcds have been artifically inflated (by
calling gcd(g*a, g*b) for some largish g).

On to the results.

a_digits b_digits g_digits  ntrials   C_Lehmer  Py_Euclid     Factor
-------- -------- --------  -------   --------  ---------     ------
1        1        0   100000   0.066856   0.240867   3.602780
2        2        0   100000   0.070256   0.314639   4.478466
4        4        0   100000   0.075708   0.466596   6.163087
7        7        0   100000   0.082714   0.681443   8.238537
10       10        0    10000   0.022336   0.318501  14.259532
20       20        0    10000   0.045209   0.752662  16.648436
50       50        0    10000   0.128269   2.167890  16.901128
100      100        0     1000   0.028053   0.511769  18.242906
1000     1000        0     1000   0.709453  18.867336  26.594197
10000    10000        0      100   4.215795 148.597223  35.247736

Lopsided gcds
-------------
20      100        0      100   0.000889   0.007659   8.616953
100       20        0      100   0.000887   0.007665   8.642473
1000        3        0      100   0.000727   0.001387   1.908167
3     1000        0      100   0.000754   0.001457   1.932027
10000        1        0      100   0.004689   0.004948   1.055219
1    10000        0      100   0.004691   0.005038   1.073948
500      400        0      100   0.020289   0.388080  19.127665
400      500        0      100   0.020271   0.389301  19.204768

Large gcd
---------
10       10       10     1000   0.005235   0.043507   8.310880
20       20       20     1000   0.008505   0.095732  11.256167
100      100      100     1000   0.041734   0.812656  19.472284```
History
Date User Action Args
2008-02-22 01:02:59mark.dickinsonsetspambayes_score: 0.174662 -> 0.17466168
recipients: + mark.dickinson, gvanrossum, rhettinger, facundobatista, ncoghlan, jyasskin
2008-02-22 01:02:58mark.dickinsonsetspambayes_score: 0.174662 -> 0.174662
messageid: <1203642178.48.0.287035349797.issue1682@psf.upfronthosting.co.za>