Author mark.dickinson
Recipients facundobatista, gvanrossum, jyasskin, mark.dickinson, ncoghlan, rhettinger
Date 2008-02-19.17:03:29
SpamBayes Score 0.0334175
Marked as misclassified No
Message-id <1203440610.93.0.334609785991.issue1682@psf.upfronthosting.co.za>
In-reply-to
Content
> 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
History
Date User Action Args
2008-02-19 17:03:31mark.dickinsonsetspambayes_score: 0.0334175 -> 0.0334175
recipients: + mark.dickinson, gvanrossum, rhettinger, facundobatista, ncoghlan, jyasskin
2008-02-19 17:03:30mark.dickinsonsetspambayes_score: 0.0334175 -> 0.0334175
messageid: <1203440610.93.0.334609785991.issue1682@psf.upfronthosting.co.za>
2008-02-19 17:03:30mark.dickinsonlinkissue1682 messages
2008-02-19 17:03:29mark.dickinsoncreate