CODEWITHSUNDEEP
algorithmdivision
Kudayar Pirimbaev
Kudayar Pirimbaev

Reputation: 1320

Algorithm: Donald Knuth division algorithm confusion

I'm trying to implement a program that divides two big precision numbers (I'm taking them as strings). Someone from other question on Stack Overflow suggested to implement the algorithm that is explained in Donald Knuth's The Art of Computer Programming book. While reading I've got a general idea of algorithm, but I have confused in some parts.

  1. The algorithm uses the concept of long-division from school. I haven't understood how the program "guesses" the digits of quotient while performing algorithm.

  2. Even if it "guesses", how should I divide the part of dividend to the divisor? Assuming that I must convert divisor into int...

  3. ...what if the divisor is a big number? Doesn't problem stay the same?

Any bit of help will be appreciated.

Thanks in advance.

Upvotes: 1

Views: 4242

Answers (1)

Mercurial
Mercurial

Reputation: 3885

I can suggest only, Division can be implemented by taking the difference between the digits of divider and divident. And then multiplying the divider with some guess based on digit difference and altering it till desired output is achieved. And yes you have to write your own addition, multipthcation functions and use arrays if computing very large data.

UPDATE Taking hint by term elementary. Suppose, 1923/695 As |695| = 3, take first 3 digits of divident and try to divide. As 193<695 add quotient 0 and add one more digit to divident. Now we have to divide 1923 by 695. One plus side of this algo is that you have to guess number between 1-9 each time. To optimise and reduce number of guesses you can implement if conditions, such as, if divident is > divisor*5 your guess would be 6,7,8 and 9. Etcetc.

I used this method to calculate factorials of large numbers before. Hope this helps you too.

Upvotes: 3

Related Questions