14,389,876 members

# Arithmetics of huge numbers

Rate this:
20 Nov 2006CPOL
Tutorial on how to manipulate numbers vastly exceeding the built-in types.

## 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 `int`s.

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.

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 {
}
}
}```

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

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, xn, simply multiply n times x by itself. To get the nth 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.

## Share

 Web Developer Yugoslavia
No Biography provided

 First Prev Next
 Classic method? Maksymus0077-Nov-07 9:23 Maksymus007 7-Nov-07 9:23
 A better way of multiplying Nnamdi Onyeyiri21-Nov-06 0:21 Nnamdi Onyeyiri 21-Nov-06 0:21
 Re: A better way of multiplying Vladimir S.25-Nov-06 10:14 Vladimir S. 25-Nov-06 10:14
 Hi & thank you for comment, My intention was to demonstrate how all other operations could be derived from the two most basic ones and how to progress using them to solve more complex operations. There are many ways to improve all of implementatons to make this example high performant. However, implementing methods such as Karatsuba would probably complicate the code beyond recognition to other readers as it requiress powering, which relies on multiplication, etc. Also, building a most efficient engine could implement more than one of such tricks. Karatsuba and S-S are slow for small numbers. Depending on a kind and length of numbers one may actually choose which method to use - if numbers are smaller than int.MaxValue/2 one can simply use built in integer addition, if multiplier turns to have many zeros simple padding with zeros would probably do the best trick, if numbers are up to 50-ish digits you can even use method above (using integer representation of fractions instead of strings) and if numbers tend to be very large one could go with Karatsuba/S-S/FFT/etc. Although I agree that number theory offers many logical tricks and algorhytms to do things much faster than this, you would still have to implement these in hight performant code using only available base types. I hope that this code and comments will anyway help people progress in building code that requires such facilities and could present a solid base to implement advanced methods such as you suggested. VS. spindlescape.net
 Last Visit: 12-Dec-19 8:33     Last Update: 12-Dec-19 8:33 Refresh 1