Binary GCD Step Count

Problem

Count iterations of the binary (Stein) GCD loop for positive a and b.

First cancel common factors of two, then repeatedly halve an even operand or replace the larger odd pair a, b with (a - b) / 2 until they are equal, counting each loop iteration. Return 0 when either input is non-positive.

Hint

Subtract and halve keeps both operands odd, shrinking them geometrically.

Test cases

case 1

in: [12,8]

expected: 2

case 2

in: [48,18]

expected: 4

case 3

in: [17,5]

expected: 4

case 4

in: [1,1]

expected: 0

case 5

in: [270,192]

expected: 10

Starter codePython

def binary_gcd_steps(a, b):
    # Your code here
    pass

5 test cases · run your code against them in the editor