Big Decimals

DOWNLOAD SOURCE CODE

Theory (what's all this about ???)
Calculator (you can do some calcs here with 1000-digit-numbers) APPLET
Graph (this applet draws the graph for your own CPU) APPLET

Theory

What's all this about

This page is all about calculating the product of 2 big decimals.. say of 10000 digits and more.. We represent those numbers as an array of machine integers. One element for each digit (I know this is not very efficient.. but this page is only about the theory.. not about practice). For example (in a Java style):

public class BigDecimal {
int len;
int[] digits;

    public BigDecimal(int length) {
        len = length;
        digits = new int[length];
    }

...

}

To calculate the product of these numbers we can use a convolution based algorithm. This means the usual algorithm you apply for calculating the product on paper. In Java this means:

    BigDecimal result = new BigDecimal(a.len+b.len);
    for (int p1 = 0; p1 < a.len; p1++) {
        for (int p2 = 0; p2 < b.len; p2++) {
            result.digits[p1+p2] += a.digits[p1]*b.digits[p2];
        }
    }
    result.carry();    //Digits can be >= 10.. do carry's

As you can see this algorithm has two nested loops. So the complexity is ~N² that's bad. Our data is only 2N and we have to wait like N² secs for the result!! This can done better.. What if we used the FFT? Isn't that thing N.logN or something? First the algorithm.. than some explanation.. (always like to dive right into code).

    float[] re_a, im_a, re_b, im_b, re_io, im_io;
    //Allocate arrays -- this code is left out here
        ...
    //Numbers to float -- set digits in real part,
    //zeros in imag part. Than take the FFT..
    a.bigDecimalToFloats(re_io,im_io);
    calcFFT(re_io,im_io,re_a,im_a);
    b.bigDecimalToFloats(re_io,im_io);
    calcFFT(re_io,im_io,re_b,im_);
    //Pointwise product
    for (ctr = 0; ctr < n; ctr++) {
        re_io[ctr] = re_a[ctr]*re_b[ctr] - im_a[ctr]*im_b[ctr];
        im_io[ctr] = re_a[ctr]*im_b[ctr] + im_a[ctr]*re_b[ctr];
    }
    //InverseFFT and get result back
    inverseFFT(re_io,im_io,re_a,im_a);
    result = new BigDecimal(re_a);

What happens??

And in practice?? Let's take a look at the a graph (comparing the two alogrithms)..

Graph

This graph is generated on an AMD K6 200Mhz CPU with 32Mb ram. The Java Runtime I've used is "Appletviewer 1.0", straigt from the JDK. This runtime is very slow compared to for example the "Symantec Java! ByteCode Compiler Version 210.057" that comes with "Netscape Navigator 4.03" so... find out which one you use before judging my lovely K6.
The vertical axis ranges from zero till 2secs/product, The horizontal axis from zero till 2000 digits.
So, each dot on this graph represents the time it takes to calculate one product. The number of digits is the number of digits in the result. The two factors are random and consist each of digits/2 digits.

The blue line is for the FFT based product, the red graph for the normal product.
You can see when the FFT length changes. For example at 256, 512 and 1024 digits.
The little peaks in the graph are probably caused by other system activities like virtual memory management and Java runtime garbage collection.

Calculator

Using this applet, you can play with some numbers on your own. Just enter the factors (A and B) and hit either [product] or [fft-product]. The result appears (after a while) in the "A*B" textarea. If your numbers are too long for just one line, you can wrap them by inserting [Returns], the applet won't mind at all.
Actually the product is evaluated 10 times to get a better time estimate. This is done 'cause the hardware clock on Intel machines usually has a lousy resolution.

Graph

Using this applet, you can create the graph for your own PC/Java-Environment -- just as the one above. Set the params right and hit the [Start] button. Then... euh... go to the kitchen to get "A cup of hot steaming Java" 'cause this step can take a while...
TimeScale: This is the scale in milli-secs for the vertical axis. The default is, as you can see 2sec.
DigitScale: This is (of course) the scale for the horizontal axis.. but it's a little more complicated. There are 4 parameters on this line -- just enter them with one space as separator character.

The start number of digits (for the left edge of the x-axis)
The end number of digits (for the right edge of the x-axis)
The step number of digits (this sets the resolution for the graph -- and calculation time :o( -- )
The number of times each product is evaluated (this changes the accuracy of the time measurement)

Just play a little bit whit things to see which params are best for your machine.

back home
error calculation