# Thread: Help in implementing BIGNUM

1. ## Help in implementing BIGNUM

I want to write a small big integer library using grammer school methods !
I am facing a problem with the representation and printing .

First a string is to be converted into an array of digits .. assume base is 10^4
so 12345678999 will be represented as

arr[0]=9998;
arr[1]=7654;
arr[2]=321;

but for some numbers such as 10000000 it will be
arr[0]=0;
arr[1]=1;

Now the main problem is with printing a bignum .. to print the first example ..i have to break each number using '%' operator so as to get 12345678999 ..which i think will make it slow !
and also extra care should be taken while printing the second case ... or else i'll end up showing 10

Any help ?

2. I'd recommend using base 10, and putting the digits into a char array. I can't recall grammar school arithmetic covering base 10^4.

3. Originally Posted by jack_carver
First a string is to be converted into an array of digits .. assume base is 10^4
so 12345678999 will be represented as

arr[0]=9998;
arr[1]=7654;
arr[2]=321;
That does not make sense to me. I would think that it should be:
Code:
```arr[0] = 8999;
arr[1] = 4567;
arr[2] = 123;```
Originally Posted by jack_carver
but for some numbers such as 10000000 it will be
arr[0]=0;
arr[1]=1;
And 10000000 would be stored as:
Code:
```arr[0] = 0;
arr[1] = 1000;```
Now the main problem is with printing a bignum .. to print the first example ..i have to break each number using '%' operator so as to get 12345678999 ..which i think will make it slow !
and also extra care should be taken while printing the second case ... or else i'll end up showing 10
You just need to iterate over the array in reverse, ignoring all 0s until you reach the first non-0, then printing all subsequent elements formatted as right aligned strings to a width of 4 with '0' as the fill character.

Originally Posted by Adak
I can't recall grammar school arithmetic covering base 10^4.
True, but it is just a change of base.

4. What do you use to represent 1's place digits above 9? In hex we use the letters A-F, but with a base of 10^4??

5. Originally Posted by Adak
What do you use to represent 1's place digits above 9? In hex we use the letters A-F, but with a base of 10^4?
Looking at the context provided by jack_carver's question, I assumed that he is trying to print in base 10, not base 10000, so that is not a problem.

6. hey
I don't know if you are following this step
every time you you use the % operator
you should reassign bignumber=bignumber/10^4

7. ## Help

Thank you all for your replies..
@laserlight .. I made mistake thank you for your help !!
Now i have the following code(WORKING) that does only converting and printing
Code:
```#define RADIX 8                  // Multiplication Complexity = O(a*b/RADIX^2)
#define BASE 100000000 				// 10^RADIX
#define MAX_DIGITS 20005         // Precision
#define DT unsigned long long	   // Data type

struct bignum
{
int pos;
DT digits[MAX_DIGITS/RADIX+9];

bignum(DT num) // for initializations like bignum N=72039847
{
pos=0;
while(num)
{
digits[pos++]=num%BASE;
num/=BASE;
}
digits[pos]=digits[pos+1]=0; // extra padding
}
bignum(const char *str) // for initializations like bignum N="72039847"
{
pos=0;
int i,len=strlen(str),no=len/RADIX;
int start=len-RADIX,end=len;
DT temp;
while(no--)
{
temp=0;
for(i=start;i<end;i++) temp=10*temp+(str[i]-'0');
digits[pos++]=temp;
end=start;
start-=RADIX;
}
temp=0;
for(i=0;i<end;i++) temp=10*temp+(str[i]-'0');
if(temp) digits[pos++]=temp;
digits[pos]=digits[pos+1]=0; // extra padding
}
void print(bool new_line=0)  // displays bignum if new_line required pass 1 as argument
{
int i=pos;
printf("%llu",digits[--i]);
while(i>0)	printf("%08llu",digits[--i]);
if(new_line) printf("\n");
}
};```
For the addition operation
Code:
```bignum operator +(const bignum &A)
{
bignum result;
...
...
return result;
}```
But the problem with this is i have to create a temp bignum to hold the result and then return it after the operation is done !.And if this exists in loop say
Code:
```for(int i=0;i<1000000;i++)
bignum a=b+c;```
The code becomes way too slow

I assume that if i write a function add in this way the code will be much faster !!
Code:
```void add(const bignum &a,const bignum &b,bignum &c) // c=a+b;
{

}```
Is there any way to speed up the earlier process since c=a+b looks much more intutive that add(a,b,c);

Thank you very much !

8. Moved to C++ programming forum.

Originally Posted by jack_carver
Now i have the following code(WORKING) that does only converting and printing
You should:
• Declare your member variables as private.
• Turn those macros into enums within the class, or perhaps as static const member variables.
• Add a default constructor

Originally Posted by jack_carver
But the problem with this is i have to create a temp bignum to hold the result and then return it after the operation is done !.
(...)
I assume that if i write a function add in this way the code will be much faster !!
You have to create a bignum object to hold the result either way. Your concern is probably that there is a cost to creating a bignum object and then using it to store the result, and then there is the cost of copying it to the destination object that is being constructed, as compared to the cost of creating the destination object, then using it directly to store the result.

However, with the named return value optimisation, this extra copying to the copy constructed destination object can be avoided. Unfortunately, you are at the mercy of the compiler, which may demand that you write your code with some restrictions in order for this optimisation to be applied, and might not even have this optimisation available at all.

Furthermore, as far as I know, this optimisation will not be applied in the case of copy assignment, but copy assignment might be useful so as to avoid creating destination objects in a loop, i.e., to reuse the storage of that one destination object. This can be done easily when the destination object is passed by reference, but a suitable equivalent might involve making the copy assignment operator smart enough to reuse storage if possible, and then overloading operator+=, so you could write:
Code:
```bignum a;
for(int i=0;i<1000000;i++)
{
a = b;
a += c;
// ...
}```
There is also the technique of using expression templates, as demonstrated by the C++ wrapper of GMP, but I am afraid that I am not very familiar with it.

9. Don't worry about the C++ operator syntax making it slow. RVO or NRVO should take care of that if you're careful. You can have the nice syntax and the speed too!

I'm more concerned about the use of base 10^8. You could just as easily have chosen 10^9 and used at least 10% less memory.
But my main point is that whilst using base 10^x will certainly make conversion to and from decimal string easier, it will make everything else slower. In such a class those conversions should be used relatively less often, so it makes sense to optimise everything else instead.

Given computers naturally use base 2, using a base of 2^32 is more more efficient.
You'll find that when it comes to division for example, that dividing by anything other than a power of ten is hard, slow, or both, if you use base 10^8.
When using base 2^32, division by any number is equally easy. It's all just shifts, compares, setting bits etc.

10. ## Re

@ laserlight Thank you ..implemented it ..
@iMalc ..
i guess you are right !
since even a simple PIKE code (PIKE supports bignum and has the GMP library) take long time when i put it inside a similar loop to add two numbers

Now about the base as 10^9
For some operations overflow unsigned long long since i want to implement the multiplication operation in a different way reducing the usage of /,% operators .. as multiplication is the most costliest operation

This was actually suggested by some person (Robert Gerbicz)
SPOJ Community Forum &bull; View topic - MUL - Wrong Answer

And i will surely think about using base as 2^X ... Thanks for posting..if you have anymore suggestions
please do post !

Thanks !

11. ## code

This is how the code looks. Still have to implement -,*,/ operators
And you were right i have no clue how to implement division ! :P
May be someone can help ..

I was also wondering about these lines in the code
Code:
```		printf("%llu",digits[--i]);
while(i>0)	printf("%08llu",digits[--i]);```
Is it possible to redefine these %llu , %08llu(note 8=>10^8) Since when i change the radix and data type i have to search for these and change them..is there any way to write custom format specifiers ??

Thank you again !

Code:
```class bignum
{
private:

static const int RADIX=8;					// Multiplication Complexity = O(a*b/RADIX^2)
static const int BASE=100000000;			// 10^RADIX
static const int MAX_DIGITS=20005;  	        // Precision
typedef unsigned long long DT;			// Data type

int pos;
DT digits[MAX_DIGITS/RADIX+9];

/*----------------------------------------------------------------*/
public:

inline void pad() // pads with three extra zeros !
{
digits[pos]=digits[pos+1]=digits[pos+2]=0;
}
bignum() // default constructor
{
pos=0;
pad();
}
bignum(DT num) // for initializations like bignum N=72039847
{
pos=0;
while(num)
{
digits[pos++]=num%BASE;
num/=BASE;
}
pad();
}
bignum(const char *str) // for initializations like bignum N="72039847"
{
pos=0;
int i,len=strlen(str),no=len/RADIX;
int start=len-RADIX,end=len;
DT temp;
while(no--)
{
temp=0;
for(i=start;i<end;i++) temp=10*temp+(str[i]-'0');
digits[pos++]=temp;
end=start;
start-=RADIX;
}
temp=0;
for(i=0;i<end;i++) temp=10*temp+(str[i]-'0');
if(temp) digits[pos++]=temp;
pad();
}
void print(bool new_line=0)  // displays bignum.. if new_line required pass 1 as argument
{
int i=pos;
printf("%llu",digits[--i]);
while(i>0)	printf("%08llu",digits[--i]);
if(new_line) printf("\n");
}
void fix() // reduces bignum
{
DT carry=0;
for(int i=0;i<pos;i++)
{
digits[i]+=carry;
carry=digits[i]/BASE;
digits[i]%=BASE;
}
}
bignum operator +(const bignum &a)
{
bignum result;
int i,new_pos=max(pos,a.pos);
DT carry=0;
for(i=0;i<=new_pos;i++)
{
result.digits[i]=digits[i]+a.digits[i]+carry;
carry=result.digits[i]/BASE;
result.digits[i]%=BASE;
}
while(new_pos>=0 &&result.digits[new_pos]==0) new_pos--;
result.pos=new_pos+1;
return result;
}
// ...
// More operators to implement
// ...

bool operator <(const bignum &a)
{
if(pos<a.pos) return true;
if(pos>a.pos) return false;
for(int i=pos-1;i>=0;i--)
{
if(digits[i]<a.digits[i]) return true;
if(digits[i]>a.digits[i]) return false;
}
return false; // since numbers are equal !
}
bool operator >(const bignum &a)
{
if(pos<a.pos) return false;
if(pos>a.pos) return true;
for(int i=pos-1;i>=0;i--)
{
if(digits[i]<a.digits[i]) return false;
if(digits[i]>a.digits[i]) return true;
}
return false; // since numbers are equal !
}
bool operator ==(const bignum &a)
{
if(pos!=a.pos) return false;
for(int i=pos-1;i>=0;i--)
if(digits[i]!=a.digits[i]) return false;
return true;
}
};```

12. I don't like the idea of a public "fix" function. If you really need such a function (and I think you probably don't) then at the very least it should be private because the class should maintain certain invariants upon exit of every public method. It should never be seen to be in an inconcistent state by the caller.

Both "fix" and your operator + should not need to use division or modulus. The worst case for addition is adding 99999999 plus 99999999 plus one for the carry.
This equals 199999999 which as you can see never exceeds 200000000. Thus you only need to test if the result is above 100000000 and if so subtract that amount and set the carry to one.
This is even simpler when using a base of 2^32.

13. ## Thanks !

Wow !...that was definitely major optimization for addition .. thank you very much !

And for that fix function i use it only for multiplication !
Ex: 47696 * 98597
Assuming BASE=100 for this case .. we get
Code:
```A[0]=96
A[1]=76
A[2]=4

B[0]=97
B[1]=85
B[2]=9```
Now multiplying the A and B array by grammar school method(No % and / are used). The result will be in the prod array:
Code:
```prod[0]=9312
prod[1]=15532
prod[2]=7712
prod[3]=1024
prod[4]=36```
Now the fix function reduces the above array to get the answer 4702682512
Code:
```prod[0]=12
prod[1]=25
prod[2]=68
prod[3]=2
prod[4]=47```
Can u see another alternative..if yes then i will be glad to hear :-)
Agreed that i should have added the code of the fix function inside the multiplication itself..but still... i thought it could be used somewhere else also.
So what say ??

14. You could just make it a private method for now. You might end up using it in a few places and you might end up merging that code into those function later to make fewer passes over the memory. But for now, just make sure it's private.

15. ## Division

Ya..i did that as soon as you told in your earlier post :P

Still have no clue how to implement division .. can someone please help me out .. or guide me to some resources

Thank you iMalc @ laserlight for your help

Popular pages Recent additions