Go vs GCCGO vs Java vs Python vs PyPy for naive factorisation

README

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

factors.go

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)
	}
}

Factors.java

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);
    }
  }
}

factors.py

# 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

Makefile

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 $@

test.sh

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