#!/usr/bin/ruby

# A simple implementation of the Karatsuba multiplication,
# which was the first subquadratic-time algorithm ever invented.

func karatsuba_multiplication(x, y, n=8) {
    if (n <= 1) {
        x * y
    }
    else {
        var m = ceil(n/2)

        var (a, b) = divmod(x, ipow2(m))
        var (c, d) = divmod(y, ipow2(m))

        var e = karatsuba_multiplication(a, c, m)
        var f = karatsuba_multiplication(b, d, m)
        var g = karatsuba_multiplication(a - b, c - d, m)

        (ipow2(2*m) * e) + (ipow2(m) * (e + f - g)) + f
    }
}

say karatsuba_multiplication(122, 422)       # 122 * 422 = 51484

assert_eq(karatsuba_multiplication(122, 422), 51484)
assert_eq(karatsuba_multiplication(413, -921, 12), -380373)
assert_eq(karatsuba_multiplication(-132, 713, 9), -94116)
assert_eq(karatsuba_multiplication(-993, -375, 5), 372375)
