Content deleted Content added
→ctz version: Replied |
|||
Line 327:
: Totally agreed, went ahead and [[WP:BOLD]]ly {{Diff|Binary GCD algorithm|597834943|597831576|deleted}} this section. Count trailing zeros has more to do with compilers using the instruction as part of the platform optimization, rather than with a C++ implementation which may or may not end up using that instruction. — [[User:Dsimic|Dsimic]] ([[User talk:Dsimic#nobold|talk]] | [[Special:Contributions/Dsimic|contribs]]) 17:44, 2 March 2014 (UTC)
*'''Keep'''. The article confuses the notion of an algorithm with the bit-bumming aspects of programming. Using machine arithmetic types (<code>int</code>) to illustrate the algorithm is one thing, but it should not be taken so literally. The algorithm and not the programming is the important thing. The cycles in a hardware divide instruction are not interesting. The availability of an x86 instruction to count zeros is also uninteresting. GCD on arbitrary-precision numbers (bignums) is a different story; think million-digit numbers. Binary GCD can be done with shifts and adds -- operations that are linear in the number of bits. Division is not. It may be that bignum packages use binary GCD for that reason. CTZ applied to the last digit of a bignum would offer a reasonable speed optimization (and one could use a lookup table to implement CTZ). I think there's value. [[User:Glrx|Glrx]] ([[User talk:Glrx|talk]]) 23:27, 2 March 2014 (UTC)
| |||