-3
\$\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\$
8
  • \$\begingroup\$ What is allowed in the loop head? Only zero-test? \$\endgroup\$ Oct 19, 2013 at 6:21
  • \$\begingroup\$ @JanDvorak Can be anything, but within the limit of the rules \$\endgroup\$
    – Coding man
    Oct 19, 2013 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\$ Oct 19, 2013 at 6:39
  • \$\begingroup\$ @JanDvorak No comparison operator allowed. You can use your second idea. \$\endgroup\$
    – Coding man
    Oct 19, 2013 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, 2013 at 9:01

1 Answer 1

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\$
4
  • \$\begingroup\$ great!!, first to answer \$\endgroup\$
    – Coding man
    Oct 19, 2013 at 9:15
  • 1
    \$\begingroup\$ you are using recursion, please do it iteratively.. \$\endgroup\$
    – Coding man
    Oct 19, 2013 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, 2013 at 9:49
  • 1
    \$\begingroup\$ I apologize. I must have skipped over the word 'iterative' while reading the description. \$\endgroup\$
    – primo
    Oct 19, 2013 at 10:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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