www.delorie.com/gnu/docs/kawa/kawa-tour_5.html

search

	Buy GNU books!

Kawa: Compiling Scheme to Java

1.4 Numbers

Scheme defines a "numerical tower" of numerical types: number, complex, real, rational, and integer. Kawa implements the full "tower" of Scheme number types, which are all sub-classes of the abstract class Quantity discussed in 1.6 Quantities.

class Complex extends Quantity { public abstract RealNum re (); public abstract RealNum im (); ... }

Complex is the class of abstract complex numbers. It has three subclasses: the abstract class RealNum of real numbers; the general class CComplex where the components are arbitrary RealNum fields; and the optimized DComplex where the components are represented by double fields.

class RealNum extends Complex { public final RealNum re () { return this; } public final RealNum im () { return IntNum.zero(); } public abstract boolean isNegative (); ... }

class DFloNum extends RealNum { double value; ... }

Concrete class for double-precision (64-bit) floating-point real numbers.

class RatNum extends RealNum { public abstract IntNum numerator(); public abstract IntNum denominator(); ... }

RatNum, the abstract class for exact rational numbers, has two sub-classes: IntFraction and IntNum.

class IntFraction extends RatNum { IntNum num; IntNum den; ... }

The IntFraction class implements fractions in the obvious way. Exact real infinities are identified with the fractions 1/0 and -1/0.

class IntNum extends RatNum { int ival; int[] words; ... }

The IntNum concrete class implements infinite-precision integers. The value is stored in the first ival elements of words, in 2's complement form (with the low-order bits in word[0]).

There are already many bignum packages, including a couple written in Java. What are the advantages of this one?

• A complete set of operations, including gcd and lcm; logical, bit, and shift operations; power by repeated squaring; all of the division modes from Common Lisp (floor, ceiling, truncate, and round); and exact conversion to double.

• Consistency and integration with a complete "numerical tower." Specifically, consistency and integration with "fixnum" (see below).

• Most bignum packages use a signed-magnitude representation, while Kawa uses 2's complement. This makes for easier integration with fixnums, and also makes it cheap to implement logical and bit-fiddling operations.

• Use of all 32 bits of each "big-digit" word, which is the "expected" space-efficient representation. More importantly, it is compatible with the mpn routines from the Gnu Multi-Precision library (gmp by T. Granlund). The mpn routines are low-level algorithms that work on unsigned pre-allocated bignums; they have been transcribed into Java in the MPN class. If better efficiency is desired, it is straight-forward to replace the MPN methods with native ones that call the highly-optimized mpn functions.

If the integer value fits within a signed 32-bit int, then it is stored in ival and words is null. This avoids the need for extra memory allocation for the words array, and also allows us to special-case the common case.

As a further optimization, the integers in the range -100 to 1024 are pre-allocated.