CodeKicks.com
Focus on Microsoft Technologies - Tutorials, Articles, Code Samples.

Friday, November 24, 2006

.NET Arythmetics with huge numbers

Introduction

I was recently involved in 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 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 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 taught 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 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, starting point would be to consider how to form its internal structure and implement basic arithmetic methods, such as addition and subtraction.

By hand, all who reads this, should be quite confident that can add or subtract two numbers, 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 should we keep in mind about addition is that result of two added numbers are never longer than 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 result will be negative.

Subtraction

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

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

You must find larger absolute number of two first and subtract smaller one from larger. 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 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 result becomes zero, and you have division result in n.

Even other more complicated methods, such as powering and finding roots are derivates of 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 code. Please note that I will be using more of a pseudo code than directly applicable code (you can find that in accompanying source) for 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 – first question is - how to assign a numerical value to the custom type you are about to create? Well, you obviously need another, build 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 relay on your computer’s calculator. Pick character by character, parse them to integers and perform addition, remember the overflow and put result back into a resulting string.

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

Subtraction

As with addition, first eliminate 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 number of length that is at most length of longer number minus length of 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 last element zero, simply take substring or eliminate the last element of 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 example above, you would end up adding one to one for million times in a loop. But if you switch places of two numbers you will be adding 1000000 to result only once – much faster!

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

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

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 cutting and pasting trailing zeros from one number to another the same number of times. Yes, this is fast!

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

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

Division

Opposite from multiplication, division is almost the same process, except few additional rules apply. Most important is that you have exception that you cannot divide by zero. Also, handy thing is that if one number equals another 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 the A. Time for another trick – get divisors’ length, stamp 1 ahead and fill the rest of places with zeros and iterate this subtraction the number of times that leading digit contains. For example:

98235364869 / 32347834

You surely know that you will be subtracting 32347834 from divisor at least the number of times it needs to reach equal length, but with 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 are you left with is:

(98235364869 – 32347834000) / 32347834 = 95000581469 / 32347834

And repeat adding thousands, hundreds, tens, etc to R. As soon as divisor becomes larger then 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 same 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 either logical operations (>, <, !=, ==, combinations of that, etc - see attached source) and complex functions such as logarithms, derives, differentials, etc. Parts of irrational numbers can also be simplified using 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 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. More

Post a Comment