Karatsuba multiplication optimization un Golang

Question

I have been playing with Go for a few weeks now and I am implemented a version of Karatsuba's multiplication (http://en.wikipedia.org/wiki/Karatsuba_algorithm#Pseudo_Code_Implementation):

package karatsuba

import (
    "math"
    "math/big"
)

func k_multiply(a, b *big.Int) *big.Int {
    if a.Cmp(big.NewInt(10)) < 1 || b.Cmp(big.NewInt(10)) < 1 {
        return mul(a, b)
    }

    m := _pivot(a, b)

    leftA, rightA := _split(a, uint(m))
    leftB, rightB := _split(b, uint(m))

    z0 := k_multiply(leftA, leftB)
    z1 := k_multiply(rightA, rightB)
    z2 := k_multiply(add(leftA, rightA), add(leftB, rightB))
    z2 = sub(z2, add(z0, z1))

    temp0 := mul(z0, big.NewInt(int64(math.Pow(10.0, 2.0*float64(m)))))
    temp1 := mul(z2, big.NewInt(int64(math.Pow(10.0, float64(m)))))
    temp2 := add(temp0, temp1)

    return add(temp2, z1)
}

func _split(a *big.Int, m uint) (left, right *big.Int) {
    denominator := big.NewInt(int64(math.Pow(10.0, float64(m))))

    left = big.NewInt(0).Div(a, denominator)
    right = sub(a, big.NewInt(0).Mul(left, denominator))

    return
}

func _pivot(a, b *big.Int) int {
    len_a := len(a.String())
    len_b := len(b.String())

    if len_a > len_b {
        return len_a/2 + len_a%2
    } else {
        return len_b/2 + len_b%2
    }
}

func add(a, b *big.Int) *big.Int {
    return big.NewInt(0).Add(a, b)
}

func mul(a, b *big.Int) *big.Int {
    return big.NewInt(0).Mul(a, b)
}

func sub(a, b *big.Int) *big.Int {
    return big.NewInt(0).Sub(a, b)
}

The algorithm works fine however I have several questions: - when I am computing temp0 and temp1, I am cheating as I am using mul to multiply my bigInt with powers of ten. Is there a better way to do this without doing extra recursive calls? - I have benchmark k_multiply against the big.Mul and the result were quite puzzling:

BenchmarkMultiply    5000000           490 ns/op
BenchmarkKaratsubaMultiply      5000        485348 ns/op

This raises 2 questions: is my implementation really bad and what can I do to make it better? and what algorithm does big.Mul uses?

Many thanks for your help, it is greatly appreciated

For the second question, just check the sources: http://golang.org/src/math/big/int.go?s=3342:3375#L142 and http://golang.org/src/math/big/nat.go They also use Karatsuba algorithm. Yet, they use it for really big numbers (see karatsubaThreshold), in other cases, simpler algorithm is used. — Grzegorz Żur, Jan 20 '15 at 08:32
look here http://stackoverflow.com/q/18465326/2521214 for ideas — Spektre, Jan 20 '15 at 10:36

Karatsuba multiplication optimization un Golang

0 Answers0