6 deleted 2 characters in body
source | link

Python - 198196 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;a~b&1;i=A(i,bc&d);a,i=[bb=[b,a>>c,A(a,b),b>>d,i,A(i,c&d)][c|db>>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.

Python - 198 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;a,b,i=[b,a>>c,A(a,b),b>>d,i,A(i,c&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.

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.

5 deleted 4 characters in body
source | link

Python - 202198 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;a,b,i=(a>>c,b>>d,A(ii=[b,c&d))if c|d else(ba>>c,A(a,b),b>>d,i,A(i,c&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.

Python - 202 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;a,b,i=(a>>c,b>>d,A(i,c&d))if c|d else(b,A(a,b),i)
 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.

Python - 198 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;a,b,i=[b,a>>c,A(a,b),b>>d,i,A(i,c&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.

4 deleted 4 characters in body
source | link

Python - 206202 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:ac,d=~a&1,~b&1;a,b,i=(a>>(~a&1)a>>c,b>>(~b&1)b>>d,A(i,~a&~b&1c&d))if~a&1|~b&1elseif c|d else(b,A(a,b),i)
 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.

Python - 206 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:a,b,i=(a>>(~a&1),b>>(~b&1),A(i,~a&~b&1))if~a&1|~b&1else(b,A(a,b),i)
 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.

Python - 202 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;a,b,i=(a>>c,b>>d,A(i,c&d))if c|d else(b,A(a,b),i)
 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.

3 deleted 10 characters in body
source | link
2 added 144 characters in body
source | link
1
source | link