Author mark.dickinson
Recipients facundobatista, gvanrossum, jyasskin, mark.dickinson, ncoghlan, rhettinger
Date 2008-02-22.01:02:52
SpamBayes Score 0.174662
Marked as misclassified No
Message-id <1203642178.48.0.287035349797.issue1682@psf.upfronthosting.co.za>
In-reply-to
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.174662
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>
2008-02-22 01:02:56mark.dickinsonlinkissue1682 messages
2008-02-22 01:02:53mark.dickinsoncreate