www.delorie.com/gnu/docs/kawa/kawa-tour_5.html search
Kawa: Compiling Scheme to Java

 [ < ] [ > ] [ << ] [ Up ] [ >> ] [Top] [Contents] [Index] [ ? ]

## 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.

 [ < ] [ > ] [ << ] [ Up ] [ >> ] [Top] [Contents] [Index] [ ? ]

 webmaster   donations   bookstore delorie software   privacy Copyright © 2003   by The Free Software Foundation Updated Jun 2003