Class Decimal

java.lang.Object
   |
   +----Decimal

public class Decimal

extends Object

This file contains a number of Java routines for basic arithmetic operations on very large numbers. They deal with the natural numbers only, which is to say 0, 1, 2, etc. (I.e. no negative integers.) These are dealt with as arrays of decimal digits, indexed from the lowest order up. That is to say that (1) each number in the array must be between 0 and 9 (inclusive), and (2) the i-th number is the coefficient of the i-th power of 10. Thus the decimal number 1234 is the array {4, 3, 2, 1}.

These routines are all static, which means that calling them must use a preface Decimal and a dot . For example, to add a = 1234 and b = 5678 to obtain c you would write in your program

where a = {4,3,2,1}, b = {8,7,6,5}.

These routines form the basis of higher-level treatment of all integers (i.e. including negative ones as well), rational numbers, and real numbers of arbitrary precision. They are implemented in base 10 only for familiarity. This is of course not an efficient choice, but they still run acceptably fast, especially for use in the course for which they were designed. In this course, which was a second year course in real analysis, the ultimate goal was to reduce the abstraction of analysis by allowing relatively simple hands-on experience with serious convergence questions. The world of real numbers looks completely different from the everyday world when one can, say, compute in a few seconds the decimal expansion of e to several hundred digits. Perspectives change entirely. The definitions of convergence translate into immediate sensations of the passage of time. Questions with, normally, not much immediacy become visibly important - in this particular case, for example, being able to estimate n! with Stirling's theorem has an immediate point. The path to interesting results of analysis is much more attractive to people who would otherwise be repelled by the subject. In addition, one frequently finds oneself in the footsteps of the great mathematicians of earlier times, who were often possessed of extraordinary computational skills and used those skills to acquire their own intuition of analysis.

So in this course it certainly did not hurt at all to have slow convergence expressed concretely through slow algorithms. At any rate, it is an easy matter to modify these routines slightly to obtain much speedier programs, say in base 2³¹. This very class uses a static variable Base which can be reset to any other base no larger than about 2¹⁵ without any modification except to input and output (or, equivalently, conversion to and from base 10). For base 2³¹ the major additional changes would be (1) to use long integers to hold products, and (2) to manipulate bits and numbers modulo 2³²carefully in order to handle carrying and borrowing.

The standard reference is Volume II of Knuth's The art of Computer Programming.

Here is a sample program, . It finds the factorial of a number given on the command line. The first few lines read the argument as an integer, whose factorial is to be calculated. If the argument is missing or of the wrong form, an Exception is thrown in one case, and in both cases the program exits abruptly. Then the factorial routine just below is calculated, and in addition there is some code to perform some timing. I recall that this package consists entirely of static routines, which means that calls to procedures in this file are preceded by the word Decimal. (with point). The call to factorial is to a routine inside the file fact.java, and needs no prefix.

Decimal()

copy(int[])

Returns a copy of x.

divide(int, int[])

Calls the next one.

divide(int, int[], int)

Short division: returns remainder, replaces dvd by quotient.

divideInto(int, int[], int, int[])

Digit-by-digit short division.

divideInto(int[], int, int[], int)

Long division: returns the quotient, replaces dvd by remainder.

divideInto(int[], int[])

Calls the next one.

equals(int[], int[])

Tells whether all non-zero digits agree.

gcd(int[], int, int[], int)

This destroys its arguments.

gcd(int[], int[])

This destroys its arguments.

greaterThan(int[], int[])

greaterThanOrEquals(int[], int[])

lessThan(int[], int[])

All the inequalities start at the top and read down until digits disagree.

lessThanOrEquals(int[], int[])

mul(int, int[])

Calls the next one.

mul(int, int[], int)

Digit-by-digit short multiplication.

mul(int[], int, int[], int)

Digit-by-digit long multiplication.

mul(int[], int[])

Calls the next one.

mulBasePower(int[], int)

To multiply by powers of 10, just add zeroes at the right.

sub(int[], int, int[], int)

Digit-by-digit subtraction.

sub(int[], int[])

Calls the next one.

sum(int[], int, int[], int)

The digit-by-digit sum.

sum(int[], int[])

Calls the next one.

toArray(long)

Here, n must be non-negativen must be >= 0.

toArray(String)

Converts the string to an integr array.

toString(int[])

Converts an array of digits back to a String.

toString(int[], int)

Converts an array of digits back to a padded String of width w.

trueLength(int[])

Skips over high order zeroes.

twoThreeDiv(int[], int[])

This is the key technical routine in long division, where it is used to get the correct single digit quotient nearly always.

valueOf(String)

Convenient to use instead of Integer.parseInt(String).

 public Decimal()

 public static int[] mulBasePower(int x[],
                                  int n)

To multiply by powers of 10, just add zeroes at the right. In terms of arrays, this amounts to inserting zeroes at the low end of an array and shifting the rest up.

 public static int valueOf(String s)

Convenient to use instead of Integer.parseInt(String).

 public static boolean equals(int a[],
                              int b[])

Tells whether all non-zero digits agree.

 public static boolean lessThan(int a[],
                                int b[])

All the inequalities start at the top and read down until digits disagree.

 public static boolean lessThanOrEquals(int a[],
                                        int b[])

 public static boolean greaterThan(int a[],
                                   int b[])

 public static boolean greaterThanOrEquals(int a[],
                                           int b[])

 public static int trueLength(int x[])

Skips over high order zeroes.

 public static int[] toArray(String s) throws NumberFormatException

Converts the string to an integr array. In base 10 this just picks off the digits one by one. Throws an exception if not all decimal digits.

 public static int[] toArray(long n) throws ArithmeticException

Here, n must be non-negativen must be >= 0.

 public static String toString(int a[])

Converts an array of digits back to a String.

 public static String toString(int a[],
                               int w)

Converts an array of digits back to a padded String of width w.

 public static int[] copy(int x[])

Returns a copy of x. This is useful before calling routines like long division which modify arguments.

 public static int[] gcd(int a[],
                         int b[])

This destroys its arguments.

 public static int[] gcd(int a[],
                         int na,
                         int b[],
                         int nb)

This destroys its arguments.

 public static int[] sum(int x[],
                         int y[])

Calls the next one.

 public static int[] sum(int x[],
                         int nx,
                         int y[],
                         int ny)

The digit-by-digit sum. The integers are digit lengths.

 public static int[] sub(int x[],
                         int y[])

Calls the next one.

 public static int[] sub(int a[],
                         int na,
                         int b[],
                         int nb)

Digit-by-digit subtraction. Assumes a no smaller than b. The integers are digit lengths.

 public static int[] mul(int a,
                         int x[])

Calls the next one.

 public static int[] mul(int a,
                         int b[],
                         int nb)

Digit-by-digit short multiplication. The integers are digit lengths.

 public static int[] mul(int x[],
                         int y[])

Calls the next one.

 public static int[] mul(int a[],
                         int na,
                         int b[],
                         int nb)

Digit-by-digit long multiplication. The integers are digit lengths.

 public static int divide(int dvr,
                          int dvd[])

Calls the next one.

 public static int divideInto(int dvr,
                              int dvd[],
                              int ndvd,
                              int quot[])

Digit-by-digit short division. Returns the single digit remainder, stores the quotient in the last argument. The integers are digit lengths. The quotient is known to be large enough, of length ndvd or ndvd-1.

 public static int divide(int dvr,
                          int dvd[],
                          int ndvd)

Short division: returns remainder, replaces dvd by quotient.

 public static int twoThreeDiv(int dvr[],
                               int dvd[])

This is the key technical routine in long division, where it is used to get the correct single digit quotient nearly always.

 public static int[] divideInto(int dvr[],
                                int dvd[])

Calls the next one.

 public static int[] divideInto(int dvr[],
                                int ndvr,
                                int dvd[],
                                int ndvd) throws ArithmeticException

Long division: returns the quotient, replaces dvd by remainder. This is surprisingly complicated, and replaces the usual hit-or-miss learned (or not) in grammar school by a few clever tricks. The three main mathematical results upon which it is based are: (1) Doing short 2/1 division always over-estimates. (2) Scaling the divisor so as to have leading digit at least Base/2 insures that the trial quotient is no more than 3 too large. (3) Doing 3/2 division will give the correct answer nearly always.