Division of large numbers in strings

Question

I wrote a program to divide large numbers using strings in C++. That is a string is used to store each digit of the number. I used continuous subtraction to get the remainder and quotient.

For ex:
16/5 
Subtract 16-5=11
11-5=6
6-5=1
1 is less than 5 so stop
quotient = 3 and remainder = 1

But the problem is this method is extremely slow for very large numbers. What other possible method is there to make it fast?

Answer 1

I do subtract n*times the number. However as you say its slow.

but consider this :

Dividend   Divisor

123456789  987 

9 digits  vs 3 digits


9 digits - 3 digits = 6 , subtract 1 so the factor is 5: 10^5 = 100.000

so:

9 digits      3+5 digits = 100.000 times

123.456.789 - 987*100.000 = 24.756.789
----------------------------------------------
8 digits      3+4 digits = 10.000 times (now 110.000 times)

24.756.789  - 9.870.000  = 14.886.789
-----------------------------------------------
8 digits      3+4 digits = 10.000 times (120.000 times)

14.886.789  - 9.870.000  = 5.016.789
-----------------------------------------------
7 digits      3+3 digits = 1000 times  (121.000 times)

5.016.789   - 987.000    = 4.029.789
-------------------------------------------------

and so on...

Hope it helps!

Answer 2

One approach to get fast bignum computation is to use high values for the base.

As an example consider the sum

12301922342343 +
39234932348823
--------------
51536854691166

When doing this computation by hand you start from rightmost digit and sum them keeping a "carry" in mind if the result gets past 9. From right to left 3+3=6, 4+2=6, 3+8=1+carry 1, 2+8+1=1+carry 1 and so on.

What you can do is however do the computation in multiple digits chunks... for example

012 301 922 342 343 +
039 234 932 348 823
-------------------
051 536 854 691 166

This is the same computation as before but now I'm using base 1000 instead of base 9 (digits go from 000 to 999) and I can use the same approach. Rightmost digit is 343+823=166 carry 001, 342 + 384 + 001 = 691, 922 + 932 = 854 carry 001 and so on.

To be able to easily do multiplications (needed also for the division algorithm) a reasonable choice for the base with 32-bit integers is 9999 because 9999*9999 is still less than 2**32 and so can be computed directly without overflows.

Using a base in the form of 10**n makes it easy to print out results in decimal one digit at a time.

Answer 3

there are some very fast( O(n log n) time ) algorithms for bignum multiplication, so you can use that with binary search to get a O( n * ( log n )^2 ) overall time

Answer 4

I've attempted to program bignums in the past, and my solution was to divide the most significant digits(s) of the numerator by the most significant digit(s) of the denominator, and adjust for scale differences. This is the first digit(s)of of the answer. Multiply this my the denominator, and subtract it from the numerator. Then repeat with this as the new numerator. This is just like long division in elementary school

10000 / 3
=10/3 * 1000 + ? 
=3*1000 + ?
=3000 + (10000-3000*3)/3
=3000 + (1000 / 3)  //repeat recursively from beginning