123456789101112131415161718192021222324252627 |
- #!/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
|