Binary Division using Templated Big Integers
I am trying to implement a Division Binary Algorithm.
The code has some Logical Errors which I am still trying to figure out how to fix them.
myuint operator/(const myuint<T>& x)
{
myuint<T> temp;
myuint<T> result;
int count = 0;
for(int i = bits.size() - 1 ; i >= 0; --i)
{
temp.bits.push_back(bits[i]);
if(temp >= x)
{
count++;
*this = *this - x;
temp = 0;
}
}
result = count;
return result;
}
I am also overloading the >=, >, and == operators for the division.
The logical problem most probably is in the for loop . What should I do? Thanks
Full code can be accessible from here
== EDIT
What I am trying to achieve is this. *this is 10100 (20 in decimal) x is 100 (4 in decimal)
- Get the first Bit (1).
- Compare it to x
- If the bit is greater than the value of x, count++, subtract x from *this. And then Start the loop again which a different *this size.
- If the bit is small, then we move to the bit next to it so, now we have 2 bits (10) and we compare it to x.
- Then I return the value of count which represents this number of divisions to reach 0.
Solution 1:
Not a full answer, but here is the algorithm that you need to implement:
myuint div(const myuint& x, const myuint& y)
{
if (y == 0)
throw "division by zero";
myuint res = 0;
myuint one = 1;
unsigned int xLength = x.bitLength();
unsigned int yLength = y.bitLength();
while (xLength > yLength)
{
res += one << (xLength - yLength - 1);
x -= y << (xLength - yLength - 1);
xLength = x.bitLength();
}
if (x >= y)
return res+1;
return res;
}