Dividing very big integers stored as string in C++

Question

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

@Galik: I looked at this method but thought that it's the one learned in school - isn't it? Ok, sorry for stupid question than. — kotrfa, Sep 12 '14 at 18:14
Yes it taught in school but I think it suits your case. You don't need to use integral types if you don't want to. You would perhaps need to make your own string based math functions to do the individual parts (subtraction etc). — Galik, Sep 12 '14 at 18:16
possible duplicate of [How to implement big int in C++](http://stackoverflow.com/questions/269268/how-to-implement-big-int-in-c) — Anycorn, Sep 12 '14 at 18:16
@Galik: Unfortunately there isn't example of code doing it with strings. — kotrfa, Sep 12 '14 at 18:21
Doing it with strings is easy - take each character, convert to an integer between 0-9, do the math, convert back. The conversion between character and integer is as simple as `i = c - '0'` and `c = (char)('0' + i)`. — Mark Ransom, Sep 12 '14 at 22:05

rcgldr · Accepted Answer · 2014-09-14T02:09:58.347

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).

score 0 · Answer 2 · answered Sep 12 '14 at 18:23

0

I've just found what was my problem and it was really trivial - I wasn't sure how to divide by bigger than e.g. long int and the solution here is do it by substraction. Hence I'm going to use long division method. Thank you and sorry for stupid question

answered Sep 12 '14 at 18:23

kotrfa

1,191
15
22

Poor solution, there's a better one, see @rcgkdr's answer. – user207421 Sep 14 '14 at 03:28

Dividing very big integers stored as string in C++

2 Answers2