Dividing very big integers stored as string in C++

I'm trying to find out an algorithm for dividing one big number with other big number (max about 200 digits both) and which are both stored as strings as decimals.

I can't use classic algorithm from school which works on paper, since the divider would need to be stored as some classic type (long long int etc.).

I have it as a practice, so efficiency or something like that is not the problem here - just the most straightforward way (not something like Furier...).

All simple algorithms I've found are quite complex or do not fits to my needs. I've found that it should be solvable just by adding, subtracting and multiplying, but have absolutely no idea how and I can't find any solid basics.

Thank you

Solution

You can speed up the long division by using divide instruction to generate a partial quotient. Divide the leading 1 or 2 digits of the dividend by 1 + the leading digit of the divisor, this will underestimate the quotient. Then multiply the divisor (full length) by the quotient digit and subtract from the dividend. Repeat this a second time and the quotient digit should be correct or 1 less than it should be. Compare the leading digits of the dividend with the divisor digits to see if the quotient digit can be increased by +1, then repeat the multiply (by 1) / subtract.

divisor is 29, use leading digit + 1 = 2 + 1 = 3 for integer divide to produce partial quotient:

17999 / 29 = 620, remainder 19

To explain this, the divisor is 29, so using 3 to produce the partial quotients. The first partial quotient is 17/3 = 5. Then multiply / subtract divisor by 5 from 179 = 34. Next partial quotient is 3/3 = 1. Multiply / subtract from 34 = 05. 05 is < divisor, so this step done, quotient digit is 5 + 1 = 6.

Next partial quotient digit is 5/3 = 1. Multiply / subtract = 30. 3/3 = 1, multiply / subtract = 1. 1 < divisor so done. quotient digit = 1 + 1 = 2.

Next partial digit is 1/3 = 0. 19 is < divisor so done. quotient = 620, remainder = 19.

Note, if the first digit of the divisor is 9, then the partial quotient is calculated using 9 + 1 = 10, so partial quotient = leading digits of divisor / 10. You'll also have to convert the two leading digits of the dividend into an integer in order to do each divide step (except for the initial step which only uses one leading digit of the dividend, or fakes a leading zero).