leonardo - February 3rd, 2009

Tags:	benchmark, java, programming, python
Subject:	Multiprecision integers
Time:	02:56 pm

Built-in Python multiprecision integers (long) are handy but they aren't know for their speed. If you want speed you usually go with GMPY (http://gmpy.sourceforge.net/ ). I was curious to see how much slower are such numbers compared to the BigInteger of a common JavaVM.

So I have compared the multiplication efficienty (I think mutiplications aren't done much efficiently in Python long) with a basic program:

// Java code
import java.math.BigInteger;
public class Fact {
    public static void main() {
        BigInteger n = BigInteger.ONE;
        for (int i = 1; i <= 20000; i++)
            n = n.multiply(BigInteger.valueOf(i));
    }
}


// Python code #1
def main():
    n = 1
    for i in xrange(1, 20000+1):
        n *= i
main()


// Python code #2
from gmpy import mpz
def main():
    n = mpz(1)
    for i in xrange(1, 20000+1):
        n *= i
main()


// Python code #3
from gmpy import mpz
import psyco
def main():
    n = mpz(1)
    for i in xrange(1, 20000+1):
        n *= i
psyco.bind(main)
main()


// Python code #4
from gmpy import fac
fac(20000)


// D + Tango
import tango.math.BigInt: BigInt;
void main() {
    BigInt n = "1";
    for (int i = 1; i <= 20_000; i++)
        n *= i;
}

Timings:
  Java:    15.59 s
  Python1:  4.51 s
  D:        4.20 s 
  Python2:  1.66 s
  Python3:  1.23 s  
  Python4:  0.31 s

Notes on the D code:
- At the end the number 'n' is represented in 32116 bytes.
- I'd like to initialize n with a normal integral value, and not a string: BigInt n = 1;
- To print n you have to use (on Tango) something like: Cout(n.toDecimalString).newline; this is ugl, it needs a toString() for simple purposes (plus other things for more complex purposes).

CPU used: Pentium III 500 MHz.

VM/compiler/libs used:
- Python 2.5.2
- GMPY V.1.02
- java version "1.6.0_10"
- LDC D compiler with V.0.9 (rev 877) based on DMD v1.039 and llvm 2.4, with Tango.

The results of Python1 vs Java have surprised me, is someone able to explain them?

comments: 7 comments or Leave a comment

February 3rd, 2009

Advertisement