Simple prime test is very slow with this library

[bekharsky]

Hi! It is a very stupid algorithm, but it runs a lot faster with standard math/big library than this gmp library.

    n := big.NewInt(0)
    n.SetString(s, 10)
    root := mathutil.SqrtBig(n)
    divider := big.NewInt(0)
    modulo := big.NewInt(0)
    quotient := big.NewInt(0)
    step := big.NewInt(1)

    var start uint64 = 2
    divider.SetUint64(start)

    c := root.Uint64()
    for i := start; i <= c; i++ {
        quotient.DivMod(n, divider, modulo)
        if modulo.Cmp(zero) == 0 {
            return false
        } else {
            divider.Add(divider, step)
        }
    }

If I change all "big" occurences to gmp, and mathutil library, of course, too, it will run much slower.

Sorry for bad English or stupid question

[ncw]

gmp beats math/big for large numbers. For small numbers math/big wins. That is mostly because each call into the gmp library involves calling into C which is relatively expensive.

The cut off depends exactly on what you are doing, but it is probably at >100 decimal digits. I haven't actually measured it though!

Hope that helps!

PS If you wan't to check primes use gmp.ProbablyPrime which is good for 1000s of digit primes.

[bekharsky]

I'm just learning concurrency in Go and trying to fully load all the processors :) I know about ProbablyPrime :)

In each gmp function we need to call do_init for each argument... So, in very long loops gmp become slower. Okay, in my case I need to use math/big :) Thanks!

[ncw]

I added some benchmarks to gmp to compare with math/big. Run with go test -run NONE -bench .

For addition, math/big is always a bit faster than gmp whereas for multiplication, beyond 100 digits gmp is faster and gets progressively faster as it is using better algorithms.

The numbers are number of digits added and multiplied. So BenchmarkGmpAdd10 adds 10 digit numbers together.

BenchmarkGmpAdd1    10000000           144 ns/op
BenchmarkGmpAdd10   20000000           145 ns/op
BenchmarkGmpAdd100  10000000           150 ns/op
BenchmarkGmpAdd1000 10000000           257 ns/op
BenchmarkGmpAdd10000     1000000          1123 ns/op
BenchmarkGmpAdd100000     200000         10669 ns/op
BenchmarkGmpAdd1000000     10000        195014 ns/op
BenchmarkGmpMul1    10000000           251 ns/op
BenchmarkGmpMul10   10000000           252 ns/op
BenchmarkGmpMul100   5000000           369 ns/op
BenchmarkGmpMul1000   500000          6518 ns/op
BenchmarkGmpMul10000       10000        217646 ns/op
BenchmarkGmpMul100000        500       5326706 ns/op
BenchmarkGmpMul1000000        20      83305668 ns/op

BenchmarkMathBigAdd1    50000000            70.3 ns/op
BenchmarkMathBigAdd10   50000000            71.2 ns/op
BenchmarkMathBigAdd100  20000000            80.5 ns/op
BenchmarkMathBigAdd1000 10000000           162 ns/op
BenchmarkMathBigAdd10000     1000000          1061 ns/op
BenchmarkMathBigAdd100000     200000         11318 ns/op
BenchmarkMathBigAdd1000000     10000        129713 ns/op
BenchmarkMathBigMul1    20000000            77.3 ns/op
BenchmarkMathBigMul10   20000000            77.5 ns/op
BenchmarkMathBigMul100   5000000           372 ns/op
BenchmarkMathBigMul1000   200000         12360 ns/op
BenchmarkMathBigMul10000        5000        530222 ns/op
BenchmarkMathBigMul100000        100      20408563 ns/op
BenchmarkMathBigMul1000000         2     798334297 ns/op