C++ and BigNums

[mimis]

Hello, I have seen many problems that deals with big integers.
I use C++ and it can handle only some digits.

Can you help me on how to represent and use them?

[ArkM]

There are lots of problems with big integers...
Can you explain YOUR problems?

[mimis]

I can't tell you any special problem because there are lots.
But i ask you how to represent big integers and how to to do operations in general.

[tux4life]

Please check out the following C++ libraries:

> http://mattmccutchen.net/bigint/
> http://sourceforge.net/projects/cpp-bigint/

[ArkM]

I can't tell you any special problem because there are lots.
But i ask you how to represent big integers and how to to do operations in general.

Well, some weeks ago I have seen a post where the author wanted "big numbers because C++ provides only six digits after decimal point" ;)...

[monkey_king]

I can't tell you any special problem because there are lots.
But i ask you how to represent big integers and how to to do operations in general.

What exactly do you want, your question is to general.

If you want to represent a arbitrary integer,
you could use a int array, and only assume you will be using vals from 0-9 on each entry.
This will make basicly be how you write a integer on a piece of paper.

And what kind of operations are you talking about?
Basic algebra? or high level polynomial factorization, or some other obscure problem.

You really need to clarify,

good luck

[mimis]

I want to do simple operations like addition, subtraction, division, multiplication, compare with very big integers like:
452475291464857345394534534594385437591546515496541+7234653459367960966043676573657376345345435364373532560623443052353652657454

[monkey_king]

Do you just need to use huge integers,
then check the links given by tux4life.

Or is this some kind of school assignment?

[mimis]

I just need to use big integers.
But i have to implement it without any extra library.

[tux4life]

In that case you'll have to implement your own algorithm ...
You can maybe try to implement the following:

When you do math and you have to make the sum of two big numbers, without using a calculator ...
What do you do ??

Well, you just sum up each digit with the corresponding digit of the other number ...

To give you an idea of what I mean:
Let's say you want to make the sum of 361 and 221, in that case you do the following:

|| 3 6 1
|| 2 2 1
= 5 8 2

You could also adapt this algorithm to your needs and use it with very big integers ...

You have analog algorithms for multiplying and dividing numbers ...

You could store the big numbers for e.g. in a string and convert it digit by digit, sum up the two digits and add the result each time to another string which holds the answer of the calculation ...

To hide all these operations it would be nice to implement your own class ...

Hope this helps !!

[mimis]

I tried to make an algorithm to do the addition of two big numbers.
Can you see my code and tell me why it doesn't work?

#include <iostream>
#include <string.h>
using namespace std;

struct bignum{
int n; //number of digits
char digits[200];
};

int char2num(char a) {
    return a-'0';
}

char num2char(int a) {
    return a+'0';
} 

void init(bignum a, int dif)
{
for (int i=a.n-1;i<=0;i++)
{
a.digits[i+dif]=a.digits[i];
a.digits[i]='0';
}
}

void addition(bignum a, bignum b, bignum c)
{
int carry;
int temp;
int dif;
if (a.n>b.n)
{
dif=a.n-b.n;
init(b,dif);
}
if (a.n<b.n)
{
dif=b.n-a.n;
init(a,dif);
}

for (int i=a.n-1;i>=0;i--)
if (carry==0)
{
temp=char2num(a.digits[i])+char2num(b.digits[i]);
if (temp>9)
{
carry=temp/10;
c.digits[i+1]=num2char(temp%10);
c.n++;
}
else if (temp<=9)
{
carry=0;
c.digits[i+1]=num2char(temp);
c.n++;
}
}
else if (carry>0)
{
temp=char2num(a.digits[i])+char2num(b.digits[i])+carry;
if (temp>9)
{
carry=temp/10;
c.digits[i+1]=num2char(temp%10);
c.n++;
}
else if (temp<=9)
{
carry=0;
c.digits[i+1]=num2char(temp);
c.n++;
}
}
}


int main()
{
bignum a,b,c;
cin >> a.digits >>b.digits;
a.n=strlen(a.digits);
b.n=strlen(b.digits);
c.n=0;
addition(a,b,c);
for (int i=c.n;i>=0;i--)
cout << c.digits[i];
cout << endl;
return 0;
}

[tux4life]

Mmm, did you make a plan before writing your program ?
As you're writing an algorithm this is a very important thing to do ...
You have to describe step by step how YOU would do it, afterwards it's much simpler to code the algorithm, and you would also make less mistakes ...

[tux4life]

You could also represent a big integer in an array, where each element represents a digit of the number ...

E.g: int bigint[12] = {1,5,6,9,7,2,3,4,5,1,0,2}; (which represents number 156972345102)

I think it's much easier to program if you use this method ...

[monkey_king]

just out of curiosity,
what does your init method do?

-----------------------------------------
I would do some thinking about the problem before i started coding.

What base do you need to use,
base_10 is quite naturally for most people.

What kind of datastructure do you want.
If you are using base_10 then a ctype int is somewhat a waste since you wont be using more than 1 byte.
So a char would be nicer but also more difficult to code.

Would it be wise to use reversed lists internally in the program.
When you do plus, minus, multiplication you always start with the least significant bit.

[tux4life]

Ok, I know using an array is (a little) waste of memory, but if you do a quick math sum:
> 1MB = 1024 * 1024 Bytes = 1048576 Bytes
> An integer is maximum 4 bytes
> So, 1048576/4 = 262144
> Which means that in 1MB computer memory you can store a number of 262144 digits ...
> And today most computers have (I hope so) much more than 1MB RAM ...

It's a little waste of space, but much easier to code ...
If you really want to use your computer memory as efficient as possible you should work with strings (but it will be more difficult to code, but it is do-able) ...

[tux4life]

Hello mimis, I've written a snippet to add two big integers ...
You can find it here ...

Hope this helps !