Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Go vs GCCGO vs Java vs Python vs PyPy for naive factorisation
GCCGo / Go slow "big" package discussion from some time ago
Back at that point, Go's 6g compiler had an implementation of the big package with assembler implementations that hadn't been ported to GCCGo.
https://groups.google.com/forum/?fromgroups=#!searchin/golang-nuts/Is$20Go$20%22big%22$20package$20slow?$20is$20Go$20slow?/golang-nuts/ChpHRdGU8ks/gyhBjheZmSEJ
Neither Java, PyPy, CPython, Go or GCCGo use GMP
CPython and PyPy can "cheat" on small integers as they use normal ints until big integers are required.
To make the comparison only over bigints, I've ensured all integers are > 64 bits.
smerity@pegasus:~/Coding/goxercise$ time go run factors.go
496968652506233122158689
real 0m3.503s
user 0m3.516s
sys 0m0.056s
smerity@pegasus:~/Coding/goxercise$ gccgo -O3 factors.go && time ./a.out
496968652506233122158689
real 0m8.453s
user 0m8.421s
sys 0m0.004s
smerity@pegasus:~/Coding/goxercise$ time python factors.py
496968652506233122158689
real 0m1.899s
user 0m1.880s
sys 0m0.012s
smerity@pegasus:~/Coding/goxercise$ time ~/Coding/Reference/pypy-2.0-beta1/bin/pypy factors.py
496968652506233122158689
real 0m1.169s
user 0m1.148s
sys 0m0.016s
smerity@pegasus:~/Coding/goxercise$ time java Factors
496968652506233122158689
real 0m1.614s
user 0m1.656s
sys 0m0.092s
package main
import (
"fmt"
"math/big"
)
func main() {
// 157 bit n = pq with p ~= 78 bits
n := big.NewInt(0)
n.SetString("273966616513101251352941655302036077733021013991", 10)
i := big.NewInt(0)
// Set i to be p - 10e6
i.SetString("496968652506233112158689", 10)
// Move temp big int out here so no possible GC thrashing
temp := big.NewInt(0)
// Avoid creating the new bigint each time
two := big.NewInt(2)
for {
// Check if the odd number is a divisor of n
temp.Mod(n, i)
if temp.Sign() == 0 {
fmt.Println(i)
break
}
i.Add(i, two)
}
}
import java.math.BigInteger;
class Factors {
public static void main (String [] args)
{
// 157 bit n = pq with p ~= 78 bits
BigInteger n = new BigInteger("273966616513101251352941655302036077733021013991");
// Set i to be p - 10e6
BigInteger i = new BigInteger("496968652506233112158689");
// Avoid creating a new bigint each time
BigInteger two = new BigInteger("2");
while (true) {
if (n.mod(i).equals(BigInteger.ZERO)) {
System.out.println(i);
break;
}
i = i.add(two);
}
}
}
# 157 bit n = pq with p ~= 78 bits
n = 273966616513101251352941655302036077733021013991
i = 496968652506233112158689 # prime minus 10e6
while True:
if n % i == 0:
print i
break
i += 2

mathewvp commented Sep 6, 2013

Are you calculating compile time along with runtime for go but only runtime for java?

jrwren commented Feb 17, 2015

@mathewvp

Compiling in go is very fast.

$ time go run factors.go
496968652506233122158689

real 0m4.917s
user 0m4.461s
sys 0m0.532s
$ go build factors.go
$ time ./factors
496968652506233122158689

real 0m4.178s
user 0m4.193s
sys 0m0.300s

ArneBab commented Jun 14, 2017

I just re-did the test and added a Makefile to make it easy to redo the check: https://gist.github.com/ArneBab/eea6d1943c51dbddffe0fedd01b9a881

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment