hapint: Design, features, and algorithms


hapint.es is an arbitrary precision integer arithmetic library for ECMAScript (JavaScript, ActionScript, etc.) . Its maximum length of digits is honestly arbitrary: That is, run on an engine faithful to the ECMAScript specification, so far as memory space permits, there is no upper/lower bounds.

Many of multiple precsion integer arithmetic libraries have upper bounds much less than the memory limitation, due to their implementations. (But this restriction has no practical problem in many applications.)


hapint is designed to provide two kinds of interfaces. One is intended to be compatible with Java's java.math.BigInteger class (that is, compatible with Java's primitive integer arithmetic and methods in java.lang.Math ). This is called "BigInteger interface" in the documentation of hapint. Another is intended to be compatible with ECMAScript's primitve numeric operations. This is called "arith interface" in the documentation. There are some differences between the two. One of salient points is that the numeric values in ECMAScript includes "negative zero".

hapint uses the "signed magnitude" representation. A magnitude is represented by the singly linked list structure. That enables the arbitrary precision and negative zero. The lowest digit is first, the highest is last, in a linked list. Just like java.math.BigInteger, hapint object is designed to be immutable: Any operation on hapint objects does not alter its operands. But, note that operations do not always create an entirely new object as the result. Node objects in lists representing magnitudes are shared as far as possible. For example, in a case you add 1 to a large number, most objects representing higher digits will be shared between the large operand and the result. In short, singly linked lists save memory. On the other hand, in some engines, the performance may be declined in comparison to other implementations (e.g., implementation based on Array).

The current version of hapint implements four BigInteger classes. One of them is main, the other three is to be used internally in the main one, because hapint uses BigInteger objects to represent digits in a magnitude: So to speak, nested BigInteger. The internal BigInteger class for digits can be arbitrarily replaced by users through factory method. Classes in any other libraries can also be used if they implement the BigInteger interface. Of course, the perfomance of operations on hapint depends largely on the perfomance and bit length of the internal BigInteger objects.


In many operations on hapint, specifying optional arguments, users can switch the algorithm of the operation. While some operations may consist of two or more algorithms, LISP-style writing of arguments with ECMAScript array literals allows users to easily construct composite algorithms and optimize algorithmic parameters. The default algorithms and parameters also can be changed through factory method.

Listed below is not all famous algorithms implemented in hapint because this document and the source code are maintained separately.


Schoolbook multiplication
also known as paper-and-pencil multiplication.
Squaring algorithm
A. Menezes, P. van Oorschot, and S. Vanstone. 1996. Handbook of Applied Cryptography. Chapter 14
Karatsuba algorithm
Toom–Cook multiplication
Multiplication using FFT


Schoolbook division
also known as paper-and-pencil division.
Knuth's algorithm
3 types implemented
Divide and conquer division
Division using reciprocal by Newton-Raphson method
Restoring division

Greatest common divisor

Euclidean algorithm
Binary gcd algorithm
Extended Euclidean algorithm
Extended binary gcd algorithm


Left-to-right 2k-ary exponentiation
Left-to-right 2k-ary exponentiation with lazy precomputation
Left-to-right sliding window exponentiation
Left-to-right sliding window exponentiation with lazy precomputation

Modular arithmetic

Multiplicative inverse by the extended Euclidean algorithm
Multiplicative inverse by the extended binary gcd algorithm
Montgomery reduction
Montgomery multiplication and exponentiation.
Barrett reduction
Modified Barrett reduction
Exponentiation over even moduli using Chinese remainder theorem

Primality tests

Miller-Rabin primality test
Sieve of Eratosthenes
Lucas-Lehmer primality test
computed with Jacobi symbol
A. Menezes, P. van Oorschot, and S. Vanstone. 1996. Handbook of Applied Cryptography. Chapter 4

FFT multiplication

hapint implements multiplication using Fast Fourier Transform. The implementation of FFT requires random access to digits and floating-point computation. In ECMAScript, there is an upper limit on the length of Array, and primitive number is 64-bit binary format IEEE 754 value. So hapint's FFT multiplication has an application limit.

Let k the bit length per one digit. In the current implementation, The upper limit of the total number of digits of two operands is about 2 min( (26 - k) * 2 - 1, 31 ). The former limit is due to the precision of primitive floating-point numbers, the later is due to the maximum length of Array.

If FFT is not applicable, a fallback multiplication algorithm is applied. For this reason, in some cases, it can happen that less bit length is faster.

Instance caching

A caching mechanism in the internal BigInteger classes is implemented (but turned off as default). When cache works, for example, a hapint object consisting of one digit 1 and one hundred digits 0 uses just two internal BigInteger objects. Like this, in some cases, caching mechanism saves memory. But, the caching is implemented to improve performace in settings that bit length of a digit is relatively short.

Caching of the hapint object itself is not implemented because of decline in performance.

Iterable methods

Some methods pertaining to prime numbers spend much computational time. Most of prevalent ECMAScript engines run on single thread, practical users may need asynchronous execution of these methods. For this purpose, hapint supports interruptible variants of these methods. They are implemented by using 'yield', so-called "generator-iterators". If you utilize them, an engine supporting the features of ECMAScript 4 is required. If you don't have interests of them, ECMAScript 3 environments will adapt hapint library with recognizing 'yield' as external function name.