Skip to content

Instantly share code, notes, and snippets.

@ArneBab
Forked from Smerity/Factors.java
Last active October 12, 2017 08:36
Show Gist options
  • Save ArneBab/eea6d1943c51dbddffe0fedd01b9a881 to your computer and use it in GitHub Desktop.
Save ArneBab/eea6d1943c51dbddffe0fedd01b9a881 to your computer and use it in GitHub Desktop.
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.
To execute the test yourself, just run
make
Results:
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
Results 2017-06:
+ go version
go version go1.8.3 linux/amd64
+ go build factors.go
+ ./factors
496968652506233122158689
real 0m2.377s
user 0m2.360s
sys 0m0.003s
+ gccgo --version
gccgo (Gentoo 6.3.0 p1.0) 6.3.0
Copyright (C) 2016 Free Software Foundation, Inc.
Dies ist freie Software; die Kopierbedingungen stehen in den Quellen. Es
gibt KEINE Garantie; auch nicht für MARKTGÄNGIGKEIT oder FÜR SPEZIELLE ZWECKE.
+ gccgo -O3 factors.go
+ ./a.out
496968652506233122158689
real 0m8.496s
user 0m8.630s
sys 0m0.293s
+ python2 --version
Python 2.7.12
+ python2 factors.py
496968652506233122158689
real 0m3.513s
user 0m3.047s
sys 0m0.000s
+ ./pypy --version
Python 2.7.13 (c925e73810367cd960a32592dd7f728f436c125c, Jun 08 2017, 19:14:08)
[PyPy 5.8.0 with GCC 6.3.0]
+ ./pypy factors.py
496968652506233122158689
real 0m1.732s
user 0m1.717s
sys 0m0.017s
+ java -version
java version "1.7.0_121"
OpenJDK Runtime Environment (IcedTea 2.6.8) (Gentoo icedtea-7.2.6.8)
OpenJDK 64-Bit Server VM (build 24.121-b00, mixed mode)
+ javac Factors.java
+ java Factors
496968652506233122158689
real 0m2.008s
user 0m1.970s
sys 0m0.147s
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
results.txt: test.sh factors.py Factors.java factors.go pypy
./$< > $@
# get pypy
pypy:
wget -O pypy.tar.bz2 https://bitbucket.org/squeaky/portable-pypy/downloads/pypy-5.8-linux_x86_64-portable.tar.bz2
tar xf pypy.tar.bz2
ln -sf pypy-5.8-linux_x86_64-portable/bin/pypy $@
#!/bin/bash
set -x
{ go version && go build factors.go && time ./factors; } 2>&1
{ gccgo --version && gccgo -O3 factors.go && time ./a.out; } 2>&1
{ python2 --version && time python2 factors.py; } 2>&1
{ ./pypy --version && time ./pypy factors.py; } 2>&1
{ java -version && javac Factors.java && time java Factors; } 2>&1
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment