Big Integer Division

[Anmu]

Hello all, I have been programming my own Big Integer class and I have successfully made adding subtraction and multiplication functions for my Big Integer class now I have been looking for good ways to implement a division function I recently found this topic: http://www.cplusplus.com/forum/general/3954/ but I did not find what I was looking for as I wan't something that is fast I also found some algorithms here : https://en.wikipedia.org/wiki/Division_algorithm and here : https://en.wikipedia.org/wiki/Fourier_division but I couldn't grasp how they work could anyone explain how I would go about doing such a thing?
Currently I have this algorithm in place but it is too slow :

BigInt operator/(const BigInt& left, const BigInt& right)
{
	//set all of the numbers to positive
	BigInt temp1 = left, temp2 = right;
	int sign = 1;
	//if signs are not the same then answer is negative else it is positive
	if (temp1.sign != temp2.sign) sign = -1;
	else sign = 1;
	temp1.sign = 1;
	temp2.sign = 1;

	BigInt quotient = BigInt(), dividend = temp1, divisor = temp2;

	for (; dividend >= divisor; dividend -= divisor, quotient++);

	
	return quotient * sign ;
}

[Duthomhas]

A Fourier transform is a polynomial multiplication, but unless you've got some pretty big numbers it's overkill for division.

But as you can use multiplication to effect divisions, check out the Newton-Raphson method:
https://en.wikipedia.org/wiki/Division_algorithm

Good luck!

[Anmu]

I have looked at the Newton raphson method but I am still trying to grasp how it works and How I would apply it, and the whole point of Big Integer is to hold really big numbers.Could you explain more in depth how newton raphson works?

[Duthomhas]

Sorry, I don't have much time to explain in very much detail.

It is a "guess and refine" method. Basically you guess a possible inverse value, then iterate to refine the guess.

Newton-Raphson finds roots, which is something you need to refine your guesses.

One thing to consider, now that you're playing with bignums, is that you have considerable leeway on how you think about the bits of a number.

For an inverse, you "pretend" a bignum is a fractional value much like you do with fixed-point numbers. Pick a spot where things magically become powers of 1/2. Do your refinements, and multiply.

(Remember, the bits of a fractional value are nothing like the bits of a whole value, so don't try to think much about it other than selecting a fairly good guess to start. Any guess will do -- you can simply set the bit one higher than the highest bit in the divisor. Try googling around for suggestions.)

Hope this helps.

[anup30]

I've been also thinking to code big division calculator. these things came to my mind. you can give it a try.

for (; dividend >= divisor; dividend -= divisor, quotient++);

you can use quotient *= 10; this way you'll be close faster. when quotient*divisor > dividend correct quotient will be in between previous two quotients.

alternatively, you can approximate even faster.
e.g.
a= 14661.....252 > 1000 digits
b= 325......515 > 400 digits

you need a/b
how many digits the quotient will have? (if you are not calculating decimals)

- at least 1000-400-1 digits
- so quotient will be at least 10^508