Talk:Binary GCD algorithm/Archive 1
 | This is an archive of past discussions about Binary GCD algorithm. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page. |
| Archive 1 |
gcd_loop optimization
gcd_loop: @ Loop finding gcd of r0, r1 not both even
tst r0, #1 @ Check least significant bit of r0
moveq r0, r0, lsr #1 @ If r0 is even, shift r0 right, dividing it by 2, and...
beq gcd_loop_continue @ ... continue to next iteration of loop.
tst r1, #1 @ Check least significant bit of r1
moveq r1, r1, lsr #1 @ If r1 is even, shift it right by 1 and...
beq gcd_loop_continue @ ... continue to next iteration of loop.
cmp r0, r1 @ Compare r0 to r1
subcs r2, r0, r1 @ If r0 >= r1, take r0 minus r1, and...
movcs r0, r2, lsr #1 @ ... shift it right and put it in r0.
subcc r2, r1, r0 @ If r0 < r1, take r1 minus r0, and...
movcc r1, r2, lsr #1 @ ... shift it right and put it in r1.
gcd_loop_continue:
cmp r0, #0 @ Has r0 dropped to zero?
bne gcd_loop @ If not, iterate
mov r0, r1, asl r3 @ Put r1 << r3 in the result register
bx lr @ Return to caller
optimization
gcd_loop: @ Loop finding gcd of r0, r1 not both even
tst r0, #1 @ Check least significant bit of r0
moveq r0, r0, lsr #1 @ If r0 is even, shift r0 right, dividing it by 2, and...
beq gcd_loop @ ... continue to next iteration of loop.
gcd_loop_2: @ Loop finding gcd of r0, r1
tst r1, #1 @ Check least significant bit of r1
moveq r1, r1, lsr #1 @ If r1 is even, shift it right by 1 and...
beq gcd_loop_2 @ ... continue to next iteration of loop.
cmp r0, r1 @ Compare r0 to r1
subcc r2, r1, r0 @ If r0 < r1, take r1 minus r0, and...
movcc r1, r2, lsr #1 @ ... shift it right and put it in r1.
bcc gcd_loop_2 @ ... continue to next iteration of loop (r0 is still odd).
sub r2, r0, r1 @ If r0 >= r1, take r0 minus r1, and...
movs r0, r2, lsr #1 @ ... shift it right and put it in r0.
bne gcd_loop @ Has r0 dropped to zero? If not, iterate
mov r0, r1, asl r3 @ Put r1 << r3 in the result register
bx lr @ Return to caller
- Sounds good to me. The point of this code sample is just to illustrate how efficient binary GCD is on a real machine. Feel free to plug in the most optimized version you can imagine. Deco 19:50, 31 October 2005 (UTC)
unsigned integers
If don't see, why the algorithm is restricted to unsigned integers. As far as I can see it works equally on negative numbers. Even more the algorithm would be simplified because no v>=u comparison is necessary. 134.102.210.237 11:54, 31 March 2006 (UTC)
Implementation in assembly
Thanks Balabiot for pointing out the incorrect result (always zero) when u=0 or v=0. I have fixed the code to return the sum of the inputs when either or both are zero. The code now matches the output of the Euclidean algorithm.
I have reverted movne/movne to movs/movnes to ensure that r0 and r1 are both nonzero on entry to check_two_r0. (The previous code hung e.g. with u=0, v=3.)
I didn't understand why the case where u and v are powers of two needed fixing, could you please elaborate? -- Regregex (talk) 17:02, 10 October 2008 (UTC)
- I don't remember, probably I just screwed up. :-) Balabiot (talk) 17:03, 23 October 2008 (UTC)
GCD in hardware
The comparison of the Binary GCD with GCD implemented by hardware division lead me to the question, how fast GCD could be when implemented as hardware instruction. I assume it must be as fast or slow as one division. HenningThielemann (talk) 20:33, 2 October 2009 (UTC)
gcd(0,0)
gcd(x,y) is the integer, that is divided by all common divisors of x and y. Thus gcd(0,0)=0, because the common divisors of 0 and 0 are all natural numbers, and these are also divisors of 0. HenningThielemann (talk) 20:22, 2 October 2009 (UTC)
- A quality source would be needed to confirm this. Cursory examination of the literature shows that, indeed, gcd(0,0) is typically not defined. (See, for instance, Niven, Montgomery, Zuckerman, "Introduction to the theory of numbers".) 71.182.236.76 (talk) 20:55, 31 October 2009 (UTC)
Implementations
I've removed the ML implementation, because it teaches more about ML than about the algorithm. I have my doubts about the value of the assembly version, but I can't really assess it as I can't read it. IMHO, the C implementation is important because it exemplifies the use of bitwise operations for efficiency. Qwertyus 22:31, 13 April 2006 (UTC)
- I think you did the right thing. I just restored the C and ARM implementations after User:Arvindn blanked them, for these reasons: IMHO, C isn't important for showing bitwise operations; it should be obvious that you'd use bitwise ops where appropriate. But the C implementation is easier to read than the English algorithm at the moment, so it needs to stay at least until there's an appropriate substitute (pseudocode? Knuth-style algorithm description?). IMHO, the ARM implementation is really enlightening, because it shows the real size and speed benefit of the algorithm in a way that no higher-level language's compiler even approaches. (In particular, it totally stomps the C implementation.) Without some hand-optimized assembly implementation, the advantage of binary GCD over Euclid is not obvious, IMHO. --Quuxplusone 21:18, 1 January 2007 (UTC)
The following pseudocode describes the algoritm probably best:
Input: Positive integers u and v
Output: gcd(u,v)
Note: division and multiplication by 2 can in many languages most efficiently be done by bitshifting.
START
s:=1
while even(u) and even(v) do
u:=u/2;v:=v/2;s:=s*2;
while even(u) do u:=u/2
while even(v) do v:=v/2
while u<>v do
begin
if u>v then
begin
u:=u-v
while even(u) do u:=u/2
end
else
begin
v:=v-u
while even(v) do v:=v/2
end
end
return(u*s)
END
Hkleinnl (talk) 20:07, 12 August 2010 (UTC)
Why (u | v) & 1 == 0 is the correct test
Regarding edits by 94.43.147.234 (talk): Step 2 states:
If u and v are both even, then gcd(u, v) = 2·gcd(u/2, v/2), because 2 is a common divisor.
Therefore, before u and v may both be halved and shift incremented, the LSB of u must be zero, and the LSB of v must be zero. The test (in line 12 of the C code fragment) would look like this (avoiding the short-circuit operators for simplicity):
for (shift = 0; (u & 1) == 0 & (v & 1) == 0; ++shift) {
This is an expression of the form , which by de Morgan's laws can be rewritten as . In other words, Halve u and v and increment shift if the following is false: that u is odd and/or v is odd. Notice the Boolean negation ! inserted at the front:
for (shift = 0; !((u & 1) == 1 | (v & 1) == 1); ++shift) {
As the only non-zero result of x & 1 is 1, the equalities disappear:
for (shift = 0; !((u & 1) | (v & 1)); ++shift) {
& is distributive over | so the two & 1 operations can be combined:
for (shift = 0; !(((u) | (v)) & 1); ++shift) {
Comparing with zero is equivalent to the Boolean negation. After removing redundant parentheses we obtain the test as originally written:
for (shift = 0; ((u | v) & 1) == 0; ++shift) {
As a further test, the code fragment as it stood (comprising ((u & v) & 1) == 0) was compiled, and gcd(1,2) was called. As u and v have no two bits set in the same column, the test never became false and the code hung in a loop between lines 12–15. u | v also corresponds to the ARM code (ORRS) which has been tested. – Regregex (talk) 16:28, 11 July 2011 (UTC)
bug in wikipedia underlying framework?
It appears that there are two pages:
a) http://en.wikipedia.org/wiki/Binary_gcd
(last modified: "4 January 2012 at 17:09.")
trying to edit that page will take you to:
http://en.wikipedia.org/w/index.php?title=Binary_GCD_algorithm&action=edit
b) http://en.wikipedia.org/wiki/Binary_GCD_algorithm
(last modified: "12 January 2012 at 15:34.")
trying to edit that page will take you to:
http://en.wikipedia.org/w/index.php?title=Binary_GCD_algorithm&action=edit
However, a) and b) appear different as a) does not reflects changes to b).
By manually modifying the "edit" URL from a) to:
http://en.wikipedia.org/w/index.php?title=Binary_gcd&action=edit
It appears that a) is just "#REDIRECTBinary GCD algorithm"
However, it does not seems to work.
I hope this helps (I could not find a "report a bug" thing so I'm posting here) — Preceding unsigned comment added by 78.31.46.6 (talk) 16:16, 12 January 2012 (UTC)
- Binary gcd is a redirect to Binary GCD algorithm. That link is intentional; anybody looking for the first is redirected to the article at the second. There is no need to edit Binary gcd. Glrx (talk) 18:58, 13 January 2012 (UTC)
Assembly code
I have once again reverted the addition of assembly code to this article.[1] It is the duty of the person trying to insert material to garner consensus; see WP:BRD.
The material is inappropriate for the article. It is irrelevant for order statistics because it deals with a fixed size number. GCD for 32-bit or 64-bit numbers is O(1). The issue for algorithms is behavior for very large numbers (e.g., arbitrary precision).
The assembly code is also too detailed for this article. Algorithms should be given in psuedo code. Higher level languages can also be used. ARM assembly is just too distant.
The code wants to be kept because the branch predication article referred to it; branch prediction is an irrelevant technique when subtracting 1000 digit numbers. The branch predication article should contain its own examples.
Glrx (talk) 22:43, 11 February 2014 (UTC)
- The sample code was present for some considerable time before you removed it. Therefore the onus was on you to start the discussion and garner consensus to remove it. Several different editors have replaced it but you have repeatedly removed it. So as not to perpetuate an edit war I have refrained from reverting your edit, but you might like to self-revert until the matter is settled here. 81.136.202.93 (talk) 16:45, 18 February 2014 (UTC)
- There's a discussion on the table. I've given reasons why the material is inappropriate for this article. You are silent on that issue. Why do you think the unsourced ARM assembly code is necessary for this article about binary GCD? Glrx (talk) 22:19, 18 February 2014 (UTC)
- I support removal of the assembly code for these reasons: (1) It is an obvious violation of WP:NOR. (2) It is a violation of WP:WEIGHT, since the number of people who care about such details is miniscule. (3) Wikipedia is not a programming manual, especially not a programming manual for assembly hobbyists. McKay (talk) 04:24, 19 February 2014 (UTC)
- I agree that the ARM assembler example was overbearing on this page. Someone not using his real name (talk) 14:19, 2 March 2014 (UTC)