Re: [PATCH 1/1] GCD: add binary GCD algorithm

2014-08-22 Thread George Spelvin
> Otherwise I don't think we can justify the additional maintenance > cost/risk, sorry. This is am extremely self-contained and easy to test piece of code. Look at the history; the total edits to the function since the beginning of git in 2005 are: - A theoretical bug fix to handle zero arguments

Re: [PATCH 1/1] GCD: add binary GCD algorithm

2014-08-22 Thread Andrew Morton
On Fri, 15 Aug 2014 20:49:16 +0800 Zhaoxiu Zeng wrote: > Because some architectures (alpha, armv6, etc.) don't provide hardware > division, > the mod operation is slow! Binary GCD algorithm uses simple arithmetic > operations, > it replaces division with arithmetic shifts, comparisons, and subt

Re: [PATCH 1/1] GCD: add binary GCD algorithm

2014-08-15 Thread George Spelvin
Here's a variant using the even-odd speedup: (Feel free to add my S-o-b if you use it.) /* * This implements Brent & Kung's "even-odd" variant of the binary GCD * algorithm. (Often attributed to Stein, but as Knith has noted, appears * a first-century Chinese math text.) * * First, find the

Re: [PATCH 1/1] GCD: add binary GCD algorithm

2014-08-15 Thread Peter Zijlstra
On Fri, Aug 15, 2014 at 04:16:01PM -0400, George Spelvin wrote: > What I'd like is a better way to automatically configure "divide is > slow" from an architecture. So the usual thing and have arch/*/Kconfig select the fancy one if it doesn't have a hardware divide instruction. For instance: arch

Re: [PATCH 1/1] GCD: add binary GCD algorithm

2014-08-15 Thread George Spelvin
> So I looked at wikipedia (I wasn't aware of this algorithm, clever > though), and am still somewhat puzzled by your 'r'. > > What's 'wrong' with their iterative version, or what's better about your > 'r' stuff? I need to look more carefully, but it looks nifty. Basically, it's avoiding the usu

Re: [PATCH 1/1] GCD: add binary GCD algorithm

2014-08-15 Thread zhaoxiu.zeng
在 2014/8/15 21:58, Peter Zijlstra 写道: > On Fri, Aug 15, 2014 at 08:49:16PM +0800, Zhaoxiu Zeng wrote: >> Because some architectures (alpha, armv6, etc.) don't provide hardware >> division, >> the mod operation is slow! Binary GCD algorithm uses simple arithmetic >> operations, >> it replaces divi

Re: [PATCH 1/1] GCD: add binary GCD algorithm

2014-08-15 Thread Peter Zijlstra
On Fri, Aug 15, 2014 at 08:49:16PM +0800, Zhaoxiu Zeng wrote: > Because some architectures (alpha, armv6, etc.) don't provide hardware > division, > the mod operation is slow! Binary GCD algorithm uses simple arithmetic > operations, > it replaces division with arithmetic shifts, comparisons, and