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?
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.
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
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
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!
