Thread: BigInt division and modulus

  1. #1
    Password:
    Join Date
    Dec 2009
    Location
    NC
    Posts
    587

    BigInt division and modulus

    Code:
    BigInt &BigInt::operator/=(int rhs)
        {
            unsigned int i = this->len;
            long long r = 0;
    
            // Check for div by 0
            if(rhs == 0)
                return *this;
    
            // Check signs
            if(this->sign != (rhs < 0))
                this->sign = !this->sign;
    
            // Make rhs positive
            if(rhs < 0)
                rhs = -1 * rhs;
            do{
                i--;
    
                // Get remainder and store in high word
                r = (r % rhs) << sizeof(unsigned int) * 8;
    
                // Get new low word
                r |= this->data[i];
    
                // Do and store division
                this->data[i] = r / rhs;
            }while(i != 0);
    
            // For later use, (r >>= sizeof(unsigned int) * 8) equals the remainder
    
            // Check for empty last block
            if(this->data[this->len - 1] == 0)
                this->resize(this->len - 1);
    
            return *this;
        }
    
        const int BigInt::operator%(int rhs)
        {
            unsigned int i = this->len;
            long long r = 0;
    
            // Check for div by 0
            if(rhs == 0)
                return 0;
    
            // Check signs
            if(this->sign != (rhs < 0))
                this->sign = !this->sign;
    
            // Make rhs positive
            if(rhs < 0)
                rhs = -1 * rhs;
            do{
                i--;
    
                // Get remainder and store in high word
                r = (r % rhs) << sizeof(unsigned int) * 8;
    
                // Clear low word
                r &= ~((long long)(~((unsigned int)0)));
    
                // Get new low word
                r |= this->data[i];
    
                // Do and store division
                this->data[i] = r / rhs;
            }while(i != 0);
    
            return (int)(r >>= sizeof(unsigned int) * 8);
        }
    It's giving really weird output, and I'm too frustrated to find my likely stupid mistake.

    The below prints 0:
    Code:
    #include <iostream>
    
    #include "BigInt.hpp"
    
    using namespace std;
    
    int main()
    {
        BigNum::BigInt t;
        t = 101;
        t /= 3;
        cout << t % 10 << endl;
        return 0;
    }

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    You could take a look at mine to see how it can be done:
    Useful classes
    In particular my DivMod_short is basically the method you are trying to use, with the main difference being that I'm using data types half the size.
    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"

  3. #3
    Password:
    Join Date
    Dec 2009
    Location
    NC
    Posts
    587
    Thanks iMalc. If I weren't doing this just to have something to do, I'd just use your lib entirely, but you know how it goes; everybody wants to reinvent the wheel.

    I went back a today, after sleeping off my frustration, and thought of what I was doing wrong w/o even looking at the code. I occurred to me on the bus ride to school.

    Code:
    	BigInt &BigInt::operator/=(int rhs)
    	{
    		unsigned int i = this->len;
    		long long r = 0;
    
    		// Check for div by 0
    		//if(rhs == 0)
    			// Throw exception
    
    		// Check signs
    		if(this->sign != (rhs < 0))
    			this->sign = !this->sign;
    
    		// Make rhs positive
    		if(rhs < 0)
    			rhs = -1 * rhs;
    		do{
    			i--;
    
    			// Get remainder and store in high word
    			r <<= sizeof(unsigned int) * 8;
    
    			// Get new low word
    			r += this->data[i];
    
    			// Do and store division
    			this->data[i] = r / rhs;
    
    			// Get remainder
    			r -= (r / rhs) * rhs;
    		}while(i != 0);
    
    		// Check for empty last block
    		if(this->data[this->len - 1] == 0)
    			this->resize(this->len - 1);
    
    		return *this;
    	}
    
    	const int BigInt::operator%(int rhs)
    	{
    		unsigned int i = this->len;
    		long long r = 0;
    
    		// Check for div by 0
    		//if(rhs == 0)
    			// Throw exception
    
    		// Make rhs positive
    		if(rhs < 0)
    			rhs = -1 * rhs;
    
    		do{
    			i--;
    
    			// Store remainder in high word
    			r <<= sizeof(unsigned int) * 8;
    
    			// Get new low word
    			r += this->data[i];
    
    			// Do and store division
    			//this->data[i] = r / rhs;
    
    			// Get remainder
    			r -= (r / rhs) * rhs;
    		}while(i != 0);
    
    		// Check signs
    		r *= (this->sign && (rhs < 0) ? 1 : -1);
    		
    		return (int)r;
    	}
    Is it against style conventions to implement this inside the public function? In other words, should I copy this to a private, named(non-operator) function?

  4. #4
    Password:
    Join Date
    Dec 2009
    Location
    NC
    Posts
    587
    Is it possible to design a way to divide by a bigint? I'm having trouble visualizing how to break a divisor into blocks to loop through like the dividend.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    For your first implementation, I would advise not trying to break it into blocks. Heck, mine still isn't done that way for bigint / bigint.
    What you do is division using the schoolbook method on the whole thing at once, except in base 2, calculating one bit at a time.

    E.g. 47 / 9 = 5, r2 -> 101111 / 1001 = 101, r10
    Code:
         _______
    1001 )101111
    
         ____1__
    1001 )101111
          1001
          0010
    
         ____10_
    1001 )101111
          1001
          0010
            101
    
         ____101
    1001 )101111
          1001
          0010
            1011
            1001
              10
    Each step of the way you would normally have to work out how many times the divisor goes into part of the dividend, and then multiply that by the divisor and subtract, then bring down another digit. However in base two it becomes far easier. At each step the divisor can only go into part of the dividend zero or one times. If the divisor is greater or equal then it's a one, else it' a zero. So you then either subtract the divisor from the portion of the dividend you are working on, or you don't. Then mark your zero or one in the result, shift the divisor along by one bit, and continue. No multiplication!
    So you start with:
    1. Shift the divisor to align its top bit with the dividend's top bit
    Then the bulk of it is just a series of:
    1. Compare divisor and other number
    2. Subtract divisor from other number if other number is greater or equal, and mark a one in the result at that bit position
    3. Shift the divisor to the right by one bit
    4. Repeat

    Stop when you've got all the bits of the result and what's left is the remainder.

    Most important thing is to ensure that you first code your bigint's bit-shift, comparison (e.g. less-than) and subtraction operations first.
    Last edited by iMalc; 09-11-2010 at 04:12 PM.
    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"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Modulus to Bitwise
    By blurrymadness in forum C Programming
    Replies: 1
    Last Post: 12-01-2009, 12:49 PM
  2. Modulus division
    By WatchTower in forum C Programming
    Replies: 4
    Last Post: 07-20-2009, 11:26 PM
  3. simple modulus question
    By movl0x1 in forum C Programming
    Replies: 5
    Last Post: 07-25-2007, 05:34 AM
  4. Problem with modus division.
    By stillwell in forum C++ Programming
    Replies: 3
    Last Post: 10-19-2004, 11:54 AM