Karatsuba Multiplication Count

Problem

Return the number of scalar multiplications used by the Karatsuba recurrence on a power-of-two size n.

The recurrence is T(1) = 1 and T(n) = 3 * T(n / 2), so the count is 3 ** log2(n). Return 0 for a non-positive or non-power-of-two input.

Hint

Splitting into halves and reusing three products gives a 3-way branching recurrence.

case 1

in: [1]

expected: 1

case 2

in: [2]

expected: 3

case 3

in: [4]

expected: 9

case 4

in: [8]

expected: 27

case 5

in: [0]

expected: 0

Starter codePython

def karatsuba_multiplications(n):
    # Your code here
    pass

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