Big integer arithmetic functions

[YoungPhysicist]

NOTE:This is not a homework question! This is just a topic that I like very much,but don’t have the programming ability to do many of them.That’s why I post this thread.

C++ is a language without built-in big integer calculation functions,so building ones that can do such job is a great way to practice algorithm testing skills.

For the past couple days,I’ve been searching on the internet for functions capable of doing such calculations,but most of them depends on methods that need to “cout” it’s result digit by digit and unable to return it. That makes them useless when I need to perform several different types of operations in a row on the same input.

So,I would be pleased if I can have functions that can return the result using std::string or int.

The tasks I will need to perform are:

1. Adding
2. Subtracting
3. Multiplying
4. Dividing
5. Square root
6. Exponent
7. Logarithms
8. Modulus(the remainder one,not $|x|$)

I will be appreciated if functions/concepts/great algorithms capable of doing any of the above operations is posted.Thank you!

The big integer that I am talking about are ones over $10^{500}$

 

[YoungPhysicist]

The only things I got:
Adding:

int char2int(char in){
   return int(in-48);
}
string bint_add(string a,string b){
   string out;
   bool go_on = false;
   int tmp;
   if(a.length() > b.length())
   swap(a,b);
   out.resize(b.length());
   //---------------------------
   if(a.length() < b.length()){
       string add = "0";
       for(int i = a.length();i<b.length()-1;i++){
           add = "0"+add;
       }
       a = add+a;
   }
   //---------------------------
   for(int i = b.length()-1;i >= 0;i--){
       tmp = char2int(a) + char2int(b)+go_on;
       if(tmp >= 10){
           go_on = true;
           out = char((tmp%10)+48);
       }
       else{
           go_on = false;
           out = char(tmp+48);
       }
   }
   if(go_on == false)
   return out;
   else
   return "1"+out;
}

This function have(not sure) a time complexity of $O(n)$.
modulus:

int mod(string num, int a) {
    int res = 0;
    for (int i = 0; i < num.length(); i++)
         res = (res*10 + (int)num[i] - '0') %a;
    return res;
}

Also with a time complexity of $O(n)$.(I suppose)
Those two functions took me two months.

 

[Baluncore]

You will need a User Defined Type or Object that can hold the numbers in your chosen format.
You must decide what format to use. Will you store the numbers in decimal strings, ASCII, or BCD, or convert them to binary and store them in an array of 32 bit integers, so a 32 x 32 multiply will give a 64 bit product, which makes partial products easy.
If you use binary you will need to decide on twos complement or signed data format.
The bottleneck will be converting between human readable ASCII and arrays of binary data, which is a slow base change.

The fastest technique I found was breaking the long decimal number into blocks of 9 decimal digits, then converting them block by block into a compact array of 32 bit unsigned integers, base 1e9. That uses fast modulo 1e9 arithmetic, you keep track of carry and avoid slow base changes. It uses available functions to pack and unpack the blocks in linear time.

 

[Tom.G]

I can only help a little, but here goes.

• bint_add() uses a boolean variable, go_on, in an arithmetic expression. Not a 'Generally Accepted Practice'.
• I suggest that bint_add() (and any others you implement) operate on "Binary Coded Decimal" (BCD) data rather than ASCII data. That way you don't have to strip and rebuild the ASCII in each operation, you can do it once on input and output.
• Multiply can be done as in the 'Paper And Pencil' method taught in grade school Arithmetic.
  • apply each digit of the multiplier to the multiplicand (with carry) to a partial product, shifting the partial products as from successive multiplier digits.
    As an optimization to decrease memory usage and complexity, you can add the partial products as you go.
    • If working in Assembly language, another possible optimization is to multiply by one Bit at a time.
    • This has the advantage that testing each bit is a Shift operation (they're fast) and the shifted multiplicand is conditionally added to the partial product (again fast).
• Divide is again the 'Paper And Pencil' method as in Multiply and the same optimizations can be implemented

The rest of the operations are composed of tha Add, Subtract, Multiply, and Divide

Another optimization is on entry of those 500 digit numbers, you convert them into a binary string or an array of Long Int and operate on those rather than on the individual digits. The drawback is on output you have to convert back to ASCII.

I see Baluncore beat me to this as I was typing. He has some good suggestions there, although a bit more complex to implement.

A thorough explanation of all this is in THE ART OF COMPUTER PROGRAMMING, Volume 2 / Seminumerical Algorithms, Donald E. Knuth. Addison-Wesley Publishing Company, ISBN 0-2-1-03802-1 is from 1969, I believe there are newer versions.

Another good source is Numerical Algorithms in C (Google it)

Cheers, and have Fun!
Tom

 

[Baluncore]

Here is the FreeBASIC source for a big number floating point calculator that uses 9 digit blocks in base 1e9. FB is easy to read and compiles to C.
https://www.freebasic.net/forum/viewtopic.php?f=7&t=15173&hilit=base1e9

 

[Svein]

MPIR: Multiple Precision Integers and Rationals (http://mpir.org/).

 

[Baluncore]

Do you want the recreational fun of writing your own BigNum package?
or do you want to download a complete BigNum library written by others such as GMP?
https://en.wikipedia.org/wiki/List_of_arbitrary-precision_arithmetic_software