Class Decimal
java.lang.Object

+Decimal
 public class Decimal
 extends Object
[ Math 220 main page ]
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 ith number is the coefficient of the ith 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
int[] c = Decimal.sum(a, b)
where a = {4,3,2,1}, b = {8,7,6,5}.
These routines form the basis of higherlevel
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
handson 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^{31}.
This very class uses a static variable Base
which can be reset to any other base no larger than about
2^{15} without any modification except to input and output
(or, equivalently, conversion to and from base 10).
For base 2^{31} the major additional
changes would be (1) to use long integers to
hold products, and (2) to manipulate bits and numbers
modulo 2^{32}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[])
 Digitbydigit 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 nonzero 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)
 Digitbydigit short multiplication.

mul(int[], int, int[], int)
 Digitbydigit 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)
 Digitbydigit subtraction.

sub(int[], int[])
 Calls the next one.

sum(int[], int, int[], int)
 The digitbydigit sum.

sum(int[], int[])
 Calls the next one.

toArray(long)
 Here, n must be nonnegativen 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).
Decimal
public Decimal()
mulBasePower
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.
valueOf
public static int valueOf(String s)
 Convenient to use instead of Integer.parseInt(String).
equals
public static boolean equals(int a[],
int b[])
 Tells whether all nonzero digits agree.
lessThan
public static boolean lessThan(int a[],
int b[])
 All the inequalities start at the top and read down until digits disagree.
lessThanOrEquals
public static boolean lessThanOrEquals(int a[],
int b[])
greaterThan
public static boolean greaterThan(int a[],
int b[])
greaterThanOrEquals
public static boolean greaterThanOrEquals(int a[],
int b[])
trueLength
public static int trueLength(int x[])
 Skips over high order zeroes.
toArray
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.
toArray
public static int[] toArray(long n) throws ArithmeticException
 Here, n must be nonnegativen must be >= 0.
toString
public static String toString(int a[])
 Converts an array of digits back to a String.
toString
public static String toString(int a[],
int w)
 Converts an array of digits back to a padded String of width w.
copy
public static int[] copy(int x[])
 Returns a copy of x. This is useful before calling routines
like long division which modify arguments.
gcd
public static int[] gcd(int a[],
int b[])
 This destroys its arguments.
gcd
public static int[] gcd(int a[],
int na,
int b[],
int nb)
 This destroys its arguments.
sum
public static int[] sum(int x[],
int y[])
 Calls the next one.
sum
public static int[] sum(int x[],
int nx,
int y[],
int ny)
 The digitbydigit sum. The integers are digit lengths.
sub
public static int[] sub(int x[],
int y[])
 Calls the next one.
sub
public static int[] sub(int a[],
int na,
int b[],
int nb)
 Digitbydigit subtraction. Assumes a no smaller than b.
The integers are digit lengths.
mul
public static int[] mul(int a,
int x[])
 Calls the next one.
mul
public static int[] mul(int a,
int b[],
int nb)
 Digitbydigit short multiplication.
The integers are digit lengths.
mul
public static int[] mul(int x[],
int y[])
 Calls the next one.
mul
public static int[] mul(int a[],
int na,
int b[],
int nb)
 Digitbydigit long multiplication.
The integers are digit lengths.
divide
public static int divide(int dvr,
int dvd[])
 Calls the next one.
divideInto
public static int divideInto(int dvr,
int dvd[],
int ndvd,
int quot[])
 Digitbydigit 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 ndvd1.
divide
public static int divide(int dvr,
int dvd[],
int ndvd)
 Short division: returns remainder, replaces dvd by quotient.
twoThreeDiv
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.
divideInto
public static int[] divideInto(int dvr[],
int dvd[])
 Calls the next one.
divideInto
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 hitormiss 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 overestimates.
(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.