Talk:Binary GCD algorithm: Difference between revisions

Revision as of 21:19, 1 January 2007

Latest revision as of 19:40, 10 July 2024

(87 intermediate revisions by 29 users not shown)

Line 1:

{{User:MiszaBot/config

== unsigned integers ==

| algo = old(365d)

| archive = Talk:Binary GCD algorithm/Archive %(counter)d

| counter = 1

| minthreadsleft = 0

}}

{{Talk header}}

{{WikiProject banner shell|class=Start|

{{WikiProject Computing|importance=Mid}}

{{WikiProject Computer science|importance=Mid}}

{{WikiProject Mathematics|importance=Mid}}

}}

== The Implementation section was wrong ==

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. [[User:134.102.210.237|134.102.210.237]] 11:54, 31 March 2006 (UTC)

<tt>gcd(i32::MAX, i32::MIN + 1)</tt> gave the result 1. Since the two inputs are negatives of each other and both are far away from one, the result should be one or the other. <tt>gcd(i32::MIN, i32::MAX)</tt> even crashes the program because of integer overflow. You '''cannot''' use unsigned integer algorithms on signed integers without knowing what's going on. The code didn't even compile without syntax warnings.

== ARM implementation ==

Because people will use algorithms found on Wikipedia, I have removed that algorithm. I will attempt to rewrite it correctly. &mdash; [[User:Chai T. Rex|Chai T. Rex]] ([[User talk:Chai T. Rex|talk]]) 11:54, 12 July 2023 (UTC)

The ARM implementation lacks the initial u = 0 test. The code also does not appear to make good use of the conditional instruction set, so I have some optimizations to suggest:

:I have rewritten the algorithm to be correct and hidden the explanatory comment on how it avoids some branches, as it no longer applies. Improvements to the algorithm can be tested with [https://play.rust-lang.org/?edition=2021&gist=d571ddc17eddc9f504ef9f1732924d5c the linked program]. &mdash; [[User:Chai T. Rex|Chai T. Rex]] ([[User talk:Chai T. Rex|talk]]) 15:55, 12 July 2023 (UTC)

== remove_twos_loop optimization ==

:Yes, the implementation I originally wrote (then adapted for greater legibility) specifically took in ''u64'' (unsigned) integers. That was changed in [[Special:Diff/1154862632|rev. 1154862632]], which introduced less-legible and incorrect code as you found out.

:The revision's summary was “the previous code doesn't work, return 0 all the time” which is incorrect (see tests in [https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=056b42ed4b2292e1a4aadd79a8cecc78 playground]).

'''gcd:'''

:Given that, I'm going to revert the changes to the implementation section: correctly handling signed integers introduces complexity which IMO takes away from the didactic & illustrative purpose of an example implementation.

@ Arguments arrive in registers r0 and r1

:I'll add a note explaining this, and how to express signed-integers GCD in terms of unsigned GCD. [[User:Nicoonoclaste|nicoo]] ([[User talk:Nicoonoclaste|talk]]) 12:16, 4 February 2024 (UTC)

mov r3, #0 @ Initialize r3, the power of 2 in the result

::PS: Sorry for the huuuge delay in reaction: I apparently missed all the watched-pages notifications due to the UI changes. [[User:Nicoonoclaste|nicoo]] ([[User talk:Nicoonoclaste|talk]]) 12:19, 4 February 2024 (UTC)

orr r12, r0, r1 @ r12 = (r0 | r1)

tst r12, #1 @ Test least significant bit of (r0 | r1)

bne gcd_loop @ If nonzero, either r0 or r1 are odd, jump into middle of next loop

'''remove_twos_loop:'''

mov r0, r0, lsr #1 @ Shift r0 right, dividing it by 2

mov r1, r1, lsr #1 @ Shift r1 right, dividing it by 2

add r3, r3, #1 @ Increment r3

tst r0, #1 @ Check least significant bit of r0

bne gcd_loop @ If nonzero, r0 is odd, jump into middle of next loop

tst r1, #1 @ Check least significant bit of r1

beq remove_twos_loop @ If zero, r0 and r1 still even, keep looping

=== optimization 1 ===

'''gcd:'''

@ Arguments arrive in registers r0 and r1

mov r3, #0 @ Initialize r3, the power of 2 in the result

orr r12, r0, r1 @ r12 = (r0 | r1)

'''remove_twos_loop:'''

tst r12, #1 @ Test least significant bit of (r0 | r1)

moveq r0, r0, lsr #1 @ Shift r0 right, dividing it by 2

moveq r1, r1, lsr #1 @ Shift r1 right, dividing it by 2

moveq r12, r12, lsr #1 @ Shift r12 right, dividing it by 2

beq remove_twos_loop @ If zero, r0 and r1 still even, keep looping

=== optimization 2 ===

'''gcd:'''

@ Arguments arrive in registers r0 and r1

mov r3, #0 @ Initialize r3, the power of 2 in the result

'''remove_twos_loop:'''

tst r0, #1 @ Test least significant bit of r0

tsteq r1, #1 @ Test least significant bit of r1

moveq r0, r0, lsr #1 @ Shift r0 right, dividing it by 2

moveq r1, r1, lsr #1 @ Shift r1 right, dividing it by 2

beq remove_twos_loop @ If zero, r0 and r1 still even, keep looping

== 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. [[User:Deco|Deco]] 19:50, 31 October 2005 (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. [[User:Qwertyus|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. --[[User:Quuxplusone|Quuxplusone]] 21:18, 1 January 2007 (UTC)