Given two large natural numers A and B ( A, B >= 264 ) find their quotient q and remainder r, where A = B * q + r,
0 <= r < B. How do you solve this problem? Please post comments ( solution, code ). I mention I would be interested in seeing the code for the schoolbook algorithm and in seeing what would be the simplest way to code division without using libraries for Big Integers.
0 <= r < B. How do you solve this problem? Please post comments ( solution, code ). I mention I would be interested in seeing the code for the schoolbook algorithm and in seeing what would be the simplest way to code division without using libraries for Big Integers.
int k = 0;
while (x > y)
{
y = y * 2;
z = z * 2;
k = k + 1;
}
q = 0;
r = 0;
while (k >= 0)
{
if (x >= y)
{
x = x - y;
q = q + z;
}
y = y / 2;
z = z / 2;
k = k - 1;
}
r = x;
q * y + r == x
The complexity is O(n * Log(Q)) ~ O(n ^ 2 * Log(Base))
there is another method, it is faster, but more complex.
It is used in BigInteger library