Large Integer Division - Knuth's Algorithm D

Question

I have to divide any number (no matter the size) by another number using Large Integer Division using Knuth's Algorithm D (The art of programming Volume 2), for example 74839234 by 72548.

I made two arrays to represent these numbers

n[] = {7,4,8,3,9,2,3,4}
d[] = {7,2,5,4,8}

I am trying to get an output like this:

q[] = {1,0,3,1}
r[] = {4,2,2,4,6}

I really don't know where to start with this. Any help or guidance would be appreciated!

Write the algorithm you have been instructed to use in english instructions, e.g. how you would tell a human to do it. Identify programming structures like for loops and ifs and whiles in it. Rewrite as pseudocode. Then, rewrite it as code. — Patashu
– Patashu, Commented Apr 18, 2013 at 4:23
Im having some issues understanding the algorithm. Because of that i dont know where to start when pseudocode. I have been sitting playing in excel trying to figure it out. — Z3R0
– Z3R0, Commented Apr 18, 2013 at 4:59

Steve Benett · Accepted Answer · 2013-10-18 09:30:45Z

1

At D1 you have d=1, so set

n[]={0,7,4,8,3,9,2,3,4}

n = 5, m = 3.

Also, there is a formal error in step D4: (second line) should be ...

minus q(hat) times (v1, v2, ..., vn)b TIMES b ** (m - j).

Here, ** means "power of" (Fortran style for easy writing). Of course, b = 10 here, so

times b ** (m - j) shifts the subtrahend left, to proper place for subtraction.

edited Oct 18, 2013 at 9:30

Steve Benett

12.9k7 gold badges62 silver badges81 bronze badges

answered Oct 18, 2013 at 9:07

user2893968

111 bronze badge

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Large Integer Division - Knuth's Algorithm D

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related