# Thread: BigInt division and modulus

1. ## 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. 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.

3. 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. 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. 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!