karatsuba_multiplication.sf

#!/usr/bin/ruby

# A simple implementation of the Karatsuba multiplication.

# See also:
#   https://en.wikipedia.org/wiki/Karatsuba_algorithm

func karatsuba_multiplication(x, y, n=8) {
    if (n <= 1) {
        x * y
    }
    else {
        var m = (n.is_even ? (n >> 1) : ((n >> 1) + 1))

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

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

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

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