JavaScript and ActionScript performance for big integer multiplication

This blog post documents the speed measurement of various JavaScript and ActionScript (and other) implementations multiplying 2048-bit big integers. I needed big integer multiplication for the Diffie-Hellman key exchange in one of my projects.

Since neither JavaScript nor ActionScript has big integer support built in, I had to implement it. I represent a big integer as a JavaScript array of digits in base 32768, in the base To multiply two 2048-bit integers use Karatsuba multiplication, which does 3 multiplications with 1024-bit operand size. To multiply two 1024-bit integers, I use Karatsuba multiplication (again), which does 3 multiplications with 512-bit operand size. To multiply two 512-bit integers, I use traditional O(n^2) ``schoolbook'' multiplication. (The Karatsuba multiplication would have been slower for this size.) All JavaScript and ActionScript code is heavily optimized, constants are inlined, and functions are instantiated for different operand sizes.

I did at least 500 multiplications of 2048-bit operand size. Here is the average number of milliseconds needed for 1 multiplication in the various implementations on an Intel Core 2 Duo 1.5 GHz machine running 32-bit Unbuntu Hardy:

• 00.0156 ms: Python (C) 2.4 gmpy (mpz of libgmp)
  
• 00.0396 ms: Java 1.6.0_16 BigInteger
  
• 00.0516 ms: Ruby (C) 1.9.1 Bignum
  
• 00.0650 ms: Python (C) 2.4 long
  
• 01.3030 ms: JavaScript Google Chrome V8 1.1.1.4
  
• 02.1750 ms: ActionScript 3 for Flash Player 10
  
• 02.7120 ms: JavaScript Google Chrome V8 1.1.1.4 using BigInt.js' mult()
  
• 04.5150 ms: JavaScript Firefox 3.5 TraceMonkey from Mercurial on 2009-10-04
  
• 05.0400 ms: JavaScript Firefox 3.5.2 TraceMonkey
  
• 05.2860 ms: JavaScript Firefox 3.0.14 TraceMonkey (?) JavaScript
  
• 06.9050 ms: ActionScript 3 for Flash Player 9 on Flash Player 9
  
• 08.5320 ms: ActionScript 3 for Flash Player 9 on Flash Player 10
  
• 10.2900 ms: JavaScript SpiderMonkey command-line interpreter 1.7.0 2007-10-03

The speed tests were run on multiple 32 and 64-bit Debian and Ubuntu installations, and the ratios came out almost the same as above.

The JavaScript and ActionScript (and some other) sources are avaialble at http://code.google.com/p/pts-mini-gpl/source/browse/#svn/trunk/javascript-multiplication.

Conclusion: If you need big integer arithmetic in the browser, detect Java and use its BigInteger from JavaScript. Otherwise, if the browser is Google Chrome, then do it in JavaScript. Otherwise, if there is Flash Player 10, do it in ActionScript 3. Otherwise, use JavaScript (and suggest installation of Java or Flash to the user).