Thread: Help in implementing BIGNUM

  1. #1
    Registered User
    Join Date
    Jan 2009
    Posts
    71

    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. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote 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;
    Quote 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.

    Quote Originally Posted by Adak
    I can't recall grammar school arithmetic covering base 10^4.
    True, but it is just a change of base.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote 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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    Registered User
    Join Date
    Oct 2009
    Posts
    7

    Question

    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. #7
    Registered User
    Join Date
    Jan 2009
    Posts
    71

    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. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Moved to C++ programming forum.

    Quote 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


    Quote 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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  10. #10
    Registered User
    Join Date
    Jan 2009
    Posts
    71

    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 !
    Last edited by jack_carver; 10-08-2009 at 04:00 AM.

  11. #11
    Registered User
    Join Date
    Jan 2009
    Posts
    71

    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. #12
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  13. #13
    Registered User
    Join Date
    Jan 2009
    Posts
    71

    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. #14
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  15. #15
    Registered User
    Join Date
    Jan 2009
    Posts
    71

    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 subscribe to a feed

Similar Threads

  1. Implementing IRC protocol
    By cs_student in forum Networking/Device Communication
    Replies: 6
    Last Post: 07-14-2009, 11:25 AM
  2. Implementing TLVs
    By brooksbp in forum Networking/Device Communication
    Replies: 1
    Last Post: 07-30-2008, 01:41 PM
  3. Implementing shared/exclusive locking (readers/writer) lock
    By ruj.sabya in forum Linux Programming
    Replies: 0
    Last Post: 05-08-2008, 12:06 AM
  4. Replies: 12
    Last Post: 12-23-2004, 12:32 AM
  5. BigNum Quick Question?
    By gqchynaboy in forum C++ Programming
    Replies: 12
    Last Post: 09-10-2003, 09:06 PM