java.lang.Object | +----Decimal
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 231. This very class uses a static variable Base which can be reset to any other base no larger than about 215 without any modification except to input and output (or, equivalently, conversion to and from base 10). For base 231 the major additional changes would be (1) to use long integers to hold products, and (2) to manipulate bits and numbers modulo 232carefully 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,
Decimal
public Decimal()
mulBasePower
public static int[] mulBasePower(int x[],
int n)
valueOf
public static int valueOf(String s)
equals
public static boolean equals(int a[],
int b[])
lessThan
public static boolean lessThan(int a[],
int b[])
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[])
toArray
public static int[] toArray(String s) throws NumberFormatException
toArray
public static int[] toArray(long n) throws ArithmeticException
toString
public static String toString(int a[])
toString
public static String toString(int a[],
int w)
copy
public static int[] copy(int x[])
gcd
public static int[] gcd(int a[],
int b[])
gcd
public static int[] gcd(int a[],
int na,
int b[],
int nb)
sum
public static int[] sum(int x[],
int y[])
sum
public static int[] sum(int x[],
int nx,
int y[],
int ny)
sub
public static int[] sub(int x[],
int y[])
sub
public static int[] sub(int a[],
int na,
int b[],
int nb)
mul
public static int[] mul(int a,
int x[])
mul
public static int[] mul(int a,
int b[],
int nb)
mul
public static int[] mul(int x[],
int y[])
mul
public static int[] mul(int a[],
int na,
int b[],
int nb)
divide
public static int divide(int dvr,
int dvd[])
divideInto
public static int divideInto(int dvr,
int dvd[],
int ndvd,
int quot[])
divide
public static int divide(int dvr,
int dvd[],
int ndvd)
twoThreeDiv
public static int twoThreeDiv(int dvr[],
int dvd[])
divideInto
public static int[] divideInto(int dvr[],
int dvd[])
divideInto
public static int[] divideInto(int dvr[],
int ndvr,
int dvd[],
int ndvd) throws ArithmeticException