Mark Dickinson added the comment:
> 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
Added file: http://bugs.python.org/file9485/lehmer_gcd.py
__________________________________
Tracker <[EMAIL PROTECTED]>
<http://bugs.python.org/issue1682>
__________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe:
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
