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.

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

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

@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

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

Typical scenario for a Java program is when already warm after boot up and code already JIT compiled. Using Linux time program to calculate the period from the cold boot is not a real world scenario because JVM needs some time during initialization I mean before executing the code. You better add a time measurement code withing each example to bypass the effects of cold boot.