Division of a big number of 100 digits stored as string

Question

I have a 100 digit number stored as string. I want to divide this number with an integer less than 10. How do I efficiently divide a big integer stored as a string with an integer?

Gader

Two possible (most obvious, among many) ways. (1): Use a BigInt library. (2): Implement in code the algorithm that you learned in 3rd or 4th grade for longhand division. – Banquette

Thanks @Banquette but the longhand division runs very slowly for such huge integers. How can I overcome it? – Gader

Yes, that's not surprising. If this is a learning exercise, I would recommend "Option 2", but it's probably going to be slow. If it's for real use, I would recommend "Option 1", because it will be fast, well tested, and well documented. – Banquette

One way, for learning only: convert the number to base N, where N is the number you want to divide with; right shift one place; convert back to the original base 10. Converting to base N involves base N addition and multiplication. Well it's perhaps not "efficient". Just looking at that in my mind's eye it appears to be O(n^2), quadratic time. But good for learning. – Behlau

The long division method works irrespective of the base your number is represented in. Since you want a base which you can convert your string to with no overhead, you only care about bases which are powers of 10, and fit in the primitive integer size for your machine. Thus, assuming a 32-bit machine, you can do the longhand division in base 10^8. This will lead to an 8x reduction in the number of divisions. You might be able to achieve further speed ups by precomouting the 8 powers of 10. This will help your compiler vectorize the conversion from 8 digits to the corresponding number. – Driftage

Answer 1

You can check the big integer library.

You can use this library in a C++ program to do arithmetic on integers of size limited only by your computer's memory. The library provides BigUnsigned and BigInteger classes that represent nonnegative integers and signed integers, respectively. Most of the C++ arithmetic operators are overloaded for these classes, so big-integer calculations are as easy as:

#include "BigIntegerLibrary.hh"

BigInteger a = 65536;
cout << (a * a * a * a * a * a * a * a);

(prints 340282366920938463463374607431768211456)

Also check GMP

Abagail

Thanks @R.T.Is there any way of implementing it without using this library and the longhand division method? – Gader

@WasimThabraze Yes, you do exactly what the person who wrote the library did :v. (Or, just use the library) – Obstacle

:P I'll go with the library! @MohammadAliBaydoun – Gader

Answer 2

@WasimThabraze - what is your understanding of the longhand division method? Since the divisor is less than 1/2 the size of an integer you can use something like this for each divide:

char array[10] = {9,8,7,6,5,4,3,2,1,0};

void divide(int dvsr)
{
int rem = 0;
int dvnd;
int quot;
int i;
    for(i = 0; i < (sizeof(array)/sizeof(array[0])) ; i++){
        dvnd = (rem * 10) + array[i];
        rem = dvnd % dvsr;
        quot = dvnd / dvsr;
        array[i] = quot;
    }
}

int main(void)
{
    divide(8);
    return (0);
}

Twopiece

What if rem * 10 is higher than INT_MAX? – Favorable

@Favorable - The max value for dvsr (divisor) is 9, so max value of rem*10 is 80. – Twopiece

@Twopiece Sorry to bring up an old question, but are you storing the big number in a way that the number with the biggest weight is on the first position in the array or vice versa? – Buckra

@Buckra - in this example, the most significant digit is first, which equals array[0]. – Twopiece

Answer 3

I hope this helps you because not all online judges allow BigIntegerLibrary.I have assumed for some arbitrary input.

string input="123456789";
int n=input.size();
string final(n,'0');
string::const_iterator  p=input.begin(),q=input.end();
string::iterator f=final.begin();

void divide(int divisor)
{
 int reminder = 0,dividend,quotient;

 /*repeatedly divide each element*/
 for(; p!=q ; p++,f++){
    dividend = (reminder * 10) + (*p-'0');
    reminder = dividend % divisor;
    quotient = dividend / divisor;
    *f = quotient + '0';
 }
 /*remove any leading zeroes from the result*/
 n = final.find_first_not_of("0");
 if (n != string::npos)
 {
    final = final.substr(n);
 }
 std::cout << final ;
}

int main(){
   int x;
   std::cin  >> x;
   divide(x);
   return 0;
}

Reilly