1

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.

quartzsaber
  • 174
  • 3
  • 10
  • 2
    Do they still teach ["long division"](http://en.wikipedia.org/wiki/Long_division) in primary school? Or is everyone dependent on electronics these days? – Mike Seymour Jan 14 '15 at 12:50
  • Bitwise operations can work just fine with a bignum class – harold Jan 14 '15 at 12:51
  • Which Bignum class? Have you read the standard literature? Could you point out what you've researched so far in an edit to your question? Why would bitwise operators not work for your number representation? Why would you be the one to implement division for a numerical type for which almost certainly a competent library exists? – Marcus Müller Jan 14 '15 at 12:54
  • Hey, I said "I'm making a Bignum class" And, I didn't knew Bitwise operators can work with it – quartzsaber Jan 14 '15 at 12:57
  • 1
    That algorithm looks more like modulo than (integer) division. Also, what language are you using, what "Bignum" class do you use, and where is your code? What is the data type of `N` and `D`? – tobias_k Jan 14 '15 at 13:07
  • @MarcusMüller In the given context, what exactly would you consider 'the standard literature'? – Codor Jan 14 '15 at 13:23
  • [numerical recipes](http://www.nr.com/), for example. More importantly than that, whatever library/language/textbook minary took his bignum type from. – Marcus Müller Jan 14 '15 at 13:27
  • The bignum of yours is integer,fixed point or floating point type? for integer and fixed point I recommend binary division for floating point some iteration algorithm is usually better like Newton–Raphson division or http://stackoverflow.com/a/18398246/2521214 see http://en.wikipedia.org/wiki/Division_algorithm for more algos. PS your code compute just the reminder if you want the actual divison you need to add counter how many times the loop was executed – Spektre Jan 15 '15 at 07:10
  • 1
    If stuff above is too much for you then you can try to use binary search (no need for bit operations) you need just `+,*,<=` – Spektre Jan 15 '15 at 07:19
  • This question was based on my old version which were based on `std::string` with decimal characters (I know it was a lazy solution! I just didn't know a class like `std::bitset` when I posted this question). Now I rebased my project to use `std::bitset` and now I just implemented binary division fine. – quartzsaber Aug 27 '16 at 04:06
  • @minary you may be interested in this [Wikipedia article](https://en.wikipedia.org/wiki/Division_algorithm#Large-integer_methods). – xrisk Aug 27 '16 at 04:22
  • @Rishav Thanks but I already solved this problem by using `std::bitset`. But thanks for replying. – quartzsaber Aug 28 '16 at 01:44

1 Answers1

1

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
MrSmith42
  • 9,961
  • 6
  • 38
  • 49
  • What is the significance of `result`? Can you please show the steps for 31/3? – greybeard Jan 14 '15 at 13:17
  • I fixed a problem in the algorithm and added the requested example. 'result' is the devision result 31/3=10 remains = 1 (stored in N) – MrSmith42 Jan 16 '15 at 11:56
  • Thanks for taking may comment seriously (: and excruciatingly to the letter :). – greybeard Jan 16 '15 at 12:13
  • @greybeard: Your comment stuck me to an error in the algorithm and so it lead to a simpler and now working version. So your comment was very productive. – MrSmith42 Jan 16 '15 at 14:38