bignum

62-bit packed arithmetic algorithms test skeleton

Below are the sources of the provisional implementation algorithm for natural big integer number addition and multiplication. I'll do division and signed arithmetic when I get a chance to, probably september.

The current algorithms for large integer arithmetic in Java appear to be those used for the same purposes in languages like C and FORTRAN; this one is tailored more specifically to the architecture of the JVM.

BigNum.java: Skeletal implementation of 62 bit packed BigNum.
numerics.java Simple benchmark test against BigInteger

BigNum is in the kin.lang.math package, so you need to make a new folder hierarchy when you download it. numerics.java is the test stub and in the default package.

I have tested on a 1.42 GHz G4, with the following results being typical:

Multiplication: Testing time to calculate 7^(2^16), averaged over 16 tests.
BigInteger took 328312.50 micros
BigNum took 178812.50 micros
BigNum was 45.5% faster than BigInteger
Addition: Testing time to calculate 2^(65536), averaged over 16 tests.
BigInteger took 1614937.50 micros
BigNum took 976687.50 micros
BigNum was 39.5% faster than BigInteger

If you could test on other JVMs, particularly if you have a 64-bit JVM, please do so and let me know at pete@cafemosaic.co.uk, giving a pair of typical results and your configuration.

Cheers.

Pete Kirkham

2003-08-13.
(kin:home)