EDIT: I rebased my bignum class to use std::bitset and I just implemented long division fine. I just didn't know any class to store bits. (like std::bitset)
I'm making a bignum class with std::string to use decimal characters as internal representation. I tried implementing division with a simple algorithm:
while N ≥ D do
N := N - D
end
return N
And of course it was slow. I tried implementing long division but that was too hard to do with decimal characters.
Thanks in advance.
Instead of subtracting D very often you could try to find the highest value of the form D^2n and sub this. Than repeat that steps with the remaining value until the remaining is less than D.
Pseudocode
0 result=0
1 powerOfD = D
2 while (powerOfD*powerOfD<N)
3 powerOfD=powerOfD*powerOfD
4 result = result+powerOfD/D, N=N-powerOfD;
5 if(N>D)
6 goto 1
7 return result
Example 31/3 (N=31, D=3)
0 result=0
1 powerD = 3;
2 3*3 < 31 TRUE
3 powerOfD= 3*3;
2 9*9 < 31 FALSE
4 result=0+9/3; N=31 - 9
5 22> 3 TRUE
6 goto 1
1 powerD = 3
2 3*3 < 22 TRUE
3 powerOfD= 3*3;
2 9*9 < 31 FALSE
4 result=3+9/3; N=22 - 9
5 13> 3 TRUE
6 goto 1
1 powerD = 3
2 3*3 < 13 TRUE
3 powerOfD= 3*3;
2 9*9 < 31 FALSE
4 result=6+9/3; N=13 - 9
5 4> 3 TRUE
6 goto 1
1 powerD = 3
2 3*3 < 4 ALSE
4 result=9+3/3; N=4-3
5 1> 3 FALSE
7 return 10
result? Can you please show the steps for 31/3?
NandD?+,*,<=