Implementing Long Division of two Large arrays...

Question

I wish to perform division on two numbers stored as integer arrays. Both the numbers are greater than LONG_LONG_MAX, so I have to use arrays.

I am storing the number in the array as reverse.

I have functions for addition, subtraction and multiplication of such arrays, and a simpler division which can divide one of these arrays with a long long int.

I tried using repeated subtraction , but that is very slow for me.

Here is my Algorithm for Division of Array with int :

///
Array res;res.size=0;
int rem=0,divdi=0,i=0;
for(;i<len(n2);i++)
{
divdi+=n1[n1.size-i-1];
if(i!=(len(n2)-1)) divdi*=10;
}
if(divdi<n2){divdi*=10;divdi+=n1[n1.size-i-1];i++;}
res[res.size] = divdi/n2; res.size++;
rem = ((divdi%n2)*10)+n1[n1.size-i-1]; i++;
for(;i<=n1.size;i++)
{
res[res.size] = floor(rem/n2);
rem = ((rem%n2)*10)+n1[n1.size-i-1];
res.size++;
}
reverse(res,res+res.size);
res.Resize(); return res;
///

I am unable to think of a better algorithm. Please help.

Answer 1

@Ace
Sir, I wish to store numbers even larger than 2^127, and so, _int128 didn't work for me.
As for the library, Ill try it. I currently have the Boost Multiprecision library with my Compiler. Thank You.

But this is for some competition where I cannot use external libraries. So I need the way to implement the division as well. If there is a way without arrays, please let me know.

//I know extensive use of arrays for such tasks is a complete waste of memory...

Answer 2

@Ace
So Ill save 3 bytes per digit?
Ill use strings.

But what about the algorithm? How am I to implement division correctly?

Answer 3

@Ace
Ill try this. Thank You!