Mark Dickinson added the comment: > A C reimplementation of gcd probably makes little sense -- for large > numbers it is dominated by the cost of the arithmetic, and that will > remain the same.
That's true for a direct translation of the usual algorithm. But there's a variant due to Lehmer which reduces the number of multi- precision operations, and dramatically reduces the number of full- precision divmod operations---they're mostly replaced by n-limb-by-1- limb multiplications and full-precision additions. I'd expect at least a factor of 2 speedup from using this; possibly more. Of course it's impossible to tell without implementing it. I've attached a Python version; note that: * the operations to find x and y at the start of the outer while loop are simple lookups when written in C * the else branch is taken rarely: usually once at the beginning of any gcd() calculation, and then less than 1 time in 20000 on average during the reduction. * all the arithmetic in the inner while loop is done with numbers <= 2**15 in absolute value. Mark Added file: http://bugs.python.org/file9463/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
