Arithmetics of huge numbers

• Download source files - 5.78 KB

Introduction

I was recently involved in a project dealing with some heavy math, prime number extraction, and that required manipulation with very large numbers. Whoever had dealt with these issues know that numbers quickly tend to grow very large, and at some point, which is very soon, you realize that the capacity of standard data types is simply not sufficient and you start asking yourself how to perform a simple addition of two numbers that exceed the limits of Int64 or double. Therefore, I started building my own code for an efficient number cruncher and, surprisingly, found myself actually coding something interesting. So, I thought I might share my experiences.

Preface

The Problem

There were actually two goals to achieve - to make a well performing and precise library and, secondly, to make it usable to the point where one can use a new type in a most possibly similar fashion as they would do with other, built in, numerical types, such as with ints.

To make an efficient custom numerical type, the starting point would be to consider how to form its internal structure and implement the basic arithmetic methods such as addition and subtraction.

All of you who are reading this should be quite confident of adding or subtracting two numbers by hand, regardless of their length. However, even most modern computers can find that difficult, so we must help them and show them how.

Addition

Primary school, first grade. And you won't easily find or implement a simpler model - start from the end, add two figures, remember the overflow and add that to the next iteration, etc. What we should keep in mind about addition is that the result of two added numbers is never longer than the length of the longer one plus one. Also, if one of two numbers is negative, this is no longer addition, but subtraction. If both numbers are negative, then it is addition, but the result will be negative.

Subtraction

Although as simple as above, computer wise, this one requires additional logic - subtract 800 from 200. If you do:

 200
-800
-----
?400 - you end up nowhere. 

You must find the bigger absolute number of the two first and subtract the smaller one from the bigger. If you have to switch places of numbers, then you will also switch the sign.

 800
-200
-----
 600 - and add '-' in front to get -600

As with addition, if any of the numbers are negative, this becomes addition.

Derived methods

I have intentionally omitted multiplication and division as basic methods as they are, in fact, derivates of addition and subtraction. Add ten times one number to itself and it's the same as multiplying a number by ten. Subtract one number from another n times, until the result becomes zero, and you have division result in n.

Even other more complicated methods such as powering and finding roots are derivates of the above.

What remains

What remains is that your arithmetic type will not start adding and subtracting by itself. You would also need a set of operators to support operations on them. Ideally, you would like, in the end, to have a situation in code where you can simply say:

C = A + B;
Or
If ( A > B ) { C = A - B; }

Implementation

OK, let's get to the code. Please note that I will be using more of a pseudo code than directly applicable code (you can find that in the accompanying source) for the simplicity of understanding. Also, I will focus on manipulation with whole numbers only. Decimal numbers are not considered in this article.

Let's start from the scratch - the first question is - how to assign a numerical value to the custom type you are about to create? Well, you obviously need another, built-in, variable(s) to pass the information. Although you can pass an array of number fractions in integer form, the most simple way is to pass a string containing only numerical characters. That approach will be used in this example, as it represents the cleanest method for demonstration.

private List<int> Digits = new List<int>();

public BigNumberInit(string nr)
{
    int i;

    for (i = 0; i < nr.Length; i++) {
        
        // check here if string contains only numbers and 
        // +/- signs at start
    
        if(i==0 && nr[i]=='-') {
            IsNegative = true;
        } else {
            Digits.Add(int.parse(nr[i]));
        }
    }
}

Again, I'll go through the operations one by one, this time with code samples.

Addition

Actually, not any addition is addition. For example, if you are adding a negative number to a positive (and vice versa), that's actually subtraction, so eliminate these at instant and pass for subtraction.

private static BigNumber operator +(BigNumber A, BigNumber B) {
    ...
    if (A.IsNegative && B.IsNegative) { return -(A.Abs() + B.Abs(); }
    if (A.IsNegative && B.IsPositive) { return (B - A.Abs()); }
    if (A.IsPositive && B.IsNegative) { return (A - B.Abs()); }
    ...
}

So, you have two strings, converted to an array of integers, and at that point, you will want to rely on your computer's calculator. Pick character by character, parse them to integers and perform addition, remember the overflow, and put the result back into a resulting string.

You should pay attention though to one thing; before you start iterating through the characters of a string, you must determine how far you should go. So, first find the "longer" number - the number with the most digits, or the one whose string representation has a bigger ".Length" property. Iterations will never go further than the length of the longest number plus one. If you end up with an overflow, just stick it to the resulting string and add its integer value to the Digits array.

Subtraction

As with addition, first eliminate the situations where you actually end up adding, not subtracting.

private static BigNumber operator -(BigNumber A, BigNumber B) {
    ...
    if (A.IsNegative && B.IsNegative) { return B.Abs() - A.Abs(); }
    if (A.IsNegative && B.IsPositive) { return -(A.Abs() + B); }
    if (A.IsPositive && B.IsNegative) { return (A + B.Abs()); }
    ...
}

Unlike addition, when subtracting, you will end up with the length that is at most the length of the bigger number minus the length of the shorter number plus one (101-1 = 100, 101 - 101 = 0, 99-101 = -2, 1-101 = -100, 50-100 = 0-50, etc). If you end up with the last element zero, simply take substring or eliminate the last element of the Digits array.

Multiplication

Multiplication is very simple:

public static BigNumber operator *(BigNumber A, BigNumber B)
{
    BigNumber R=0, i;

    for(i=0;i<B;i++) R+=A;

    return R;
}

However, we can use a few tricks here to speed things up dramatically. Imagine multiplying 1 by 1000000 - in the example above, you would end up adding one to one for million times in a loop. But if you switch the places of the two numbers, you will be adding 1000000 to the result only once - much faster!

Another trick - say you want to multiply 9876543210 by 1234567890. This is many iterations, and the numbers are of the same length and not qualifying for switching around like in the previous example.

You can't do much here but start with the most basic method - iteration - until you reach zero at the end of the multiplier. Then you do one cunning thing - simply attach zero to the end of the first number and cut the trailing zero from another. In the example above, 9876543210*1234567890 is actually the same as 98765432100*123456789, and I think you will agree instantly.

So, instead of repeating the loop for millions and millions of iterations, you will do addition at most the [sum of all digit] times and cut and paste trailing zeros from one number to another the same number of times. Yes, this is fast!

When multiplying, the length of the result is always at most the length of the first number plus the length of the second number minus one, which is an analogy from the addition principle.

No matter if one or both numbers are negative, you can now rely on the addition and subtraction handlers you are calling anyway.

Division

Opposite from multiplication, division is almost the same process, except a few additional rules apply. The most important is that you have the exception that you cannot divide by zero. Also, the handy thing is that if one number equals another, the result is always 1.

public static BigNumber operator /(BigNumber A, BigNumber B)
{
    BigNumber R=0, N=A;

    if(B==0) throw new Exception(…);
    if(A==B) return 1;
    if(B>A) return 0;

    while(N>0) { N-=B; R++; }
 
    return R;
}

Again, as with multiplication, this can go fairly slow if B is slightly shorter than A. Time for another trick - get the divisor's length, stamp 1 ahead, and fill the rest of places with zeros, and iterate this subtraction the number of times that the leading digit contains. For example:

98235364869 / 32347834

You surely know that you will be subtracting 32347834 from the divisor at least the number of times it needs to reach equal length, but with the constraint that its first digit doesn't rise above the divisor. So, you are certain that:

98235364869 is dividable by 32347834000

Cool, then don't iterate 1000 times, but add 1000 to R immediately. What you are left with is:

(98235364869 - 32347834000) / 32347834 = 95000581469 / 32347834

And repeat adding thousands, hundreds, tens, etc., to R. As soon as the divisor becomes larger than the dividend, you can't divide anymore to get a whole number and R becomes your result.

Third level operations

Third level operations are powering and obtaining roots. You can already guess that they derive from multiplication and division, the same way as multiplication and division derive from addition and subtraction.

To get the power of a number, x^n, simply multiply n times x by itself. To get the n^th root of x, keep dividing by n result of x divided by n until you reach zero.

Other operations

Other operations are logical operations (>, <, !=, ==, combinations of that, etc. - see the attached source) and complex functions such as logarithms, derives, differentials, etc. Parts of irrational numbers can also be simplified using the above mentioned methods.

Conclusion

When I got into this, I was thrilled with each new step I made forward. Actually, all my functions relied on those already made, which actually relied on addition and subtraction in its base and some basic logic. All other operations were just derivates of the two simplest operations already known for thousands of years.

Math is such a good example that big steps are made so slow. And also how small human needs are. Computers of today can quickly solve problems we'd need years to work on without them, yet computers still cannot do very simple things that we are confident to know how to do. Then again, they are such a fun and very useful tools, as long as we are confident we can perform better.

Things to do

• Implementation of decimals
• Performance improvements

Credits

You can freely download the binaries of the BigNumber library from www.spindlescape.net. The study presented here served for its implementation.

History

• Document version 1.0: Nov 20, 2006.