-2
\$\begingroup\$

Write the shortest iterative function to find gcd of two numbers (assume 32 bit numbers).

Rules:

  • Arithmetic, Comparison and Logical Operators are not allowed (except equality comparison (a==b) operator).
  • Function should work for both positive and negative numbers
  • No inbuilt functions allowed.
  • All bitwise operators allowed.
\$\endgroup\$
  • \$\begingroup\$ What is allowed in the loop head? Only zero-test? \$\endgroup\$ – John Dvorak Oct 19 '13 at 6:21
  • \$\begingroup\$ @JanDvorak Can be anything, but within the limit of the rules \$\endgroup\$ – Coding man Oct 19 '13 at 6:27
  • \$\begingroup\$ ok, does equality test count as comparison, or do we have to do a poor-man's XOR followed by a zero-check? \$\endgroup\$ – John Dvorak Oct 19 '13 at 6:39
  • \$\begingroup\$ @JanDvorak No comparison operator allowed. You can use your second idea. \$\endgroup\$ – Coding man Oct 19 '13 at 6:44
  • 1
    \$\begingroup\$ @JanDvorak Unfortunately XOR is also not allowed and has to be replaced by (a|b)&!(a&b). Together with no comparisons allowed this seems rather arbitrary to me and disqualifies lots of languages. Not interesting. \$\endgroup\$ – Howard Oct 19 '13 at 9:01
5
\$\begingroup\$

Python - 196 bytes

def A(a,b):
 while b:a,b=a&~b|~a&b,(a&b)<<1
 return a
def G(a,b,i=0):
 if a>>31:a=A(~a,1)
 if b>>31:b=A(~b,1)
 while~a&b|a&~b:c,d=~a&1,~b&1;i=A(i,c&d);a,b=[b,a>>c,A(a,b),b>>d][c|d::2]
 return a<<i

Sample usage:

from random import randint
for i in range(10):
  a = randint(-2147483647,2147483647)
  b = randint(-2147483647,2147483647)
  print 'gcd(%d, %d) = %d'%(a, b, G(a,b))

Sample output:

gcd(-36916085, -1872111029) = 1
gcd(1355889652, 1816917540) = 188
gcd(-366482295, 1612196424) = 9
gcd(836632083, -1156302534) = 3
gcd(1223074731, -1299765354) = 123
gcd(-1154829176, 522085100) = 4
gcd(-1673024403, 1589241938) = 1
gcd(-1871498822, -1089342630) = 2
gcd(1653429392, 2095617430) = 2
gcd(1525670601, -1985869899) = 39

Implementation Notes

  • A -> a function which adds two integers.
  • a&~b|~a&b -> a^b
  • if a>>31 -> if a<0
  • a=A(~a,1) -> a=-a (taken together, if a>>31:a=A(~a,1) -> a=abs(a))
  • ~a&1 -> a%2==0 a.k.a. a is even.

The function G begins by removing powers of 2 from both a and b (and shifting the result if both are even). When both a and b are odd, it continues on with a=b, b=(a+b)/2. This works because gcd(a, b) = gcd(a, a+b), and a+b is necessarily even. This would terminate noticeably sooner using a comparison and a subtraction (subtracting the smaller value from the larger), but neither are available.

\$\endgroup\$
  • \$\begingroup\$ great!!, first to answer \$\endgroup\$ – Coding man Oct 19 '13 at 9:15
  • 1
    \$\begingroup\$ you are using recursion, please do it iteratively.. \$\endgroup\$ – Coding man Oct 19 '13 at 9:32
  • 1
    \$\begingroup\$ please, verify if the description was ambiguous "Write the shortest iterative function to find gcd of two numbers". If ambiguous, recursion will be fine and I will update the question else you have to update the code :P \$\endgroup\$ – Coding man Oct 19 '13 at 9:49
  • 1
    \$\begingroup\$ I apologize. I must have skipped over the word 'iterative' while reading the description. \$\endgroup\$ – primo Oct 19 '13 at 10:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.