3 ms·

Try again? Long division, dividing A by B, is a for loop that maintains the invariant A = QB + R, where Q is the number written on top (initially 0) and R is t

Try again? Long division, dividing A by B, is a for loop that maintains the invariant A = QB + R, where Q is the number written on top (initially 0) and R is the number written on the bottom (initially A), by subtracting values of the form B(C)(10^N) from R and adding values (C)(10^N) to Q to compensate. func Longdiv(A, B) { // Assume A > 0, B > 0. N = floor(log10(A)) Q = 0 R = A while (N >= 0) { // Invariant: A = B * Q + R // Invariant: B * 10^(N+1) > R C = 0 while (B * (C + 1) * (10 ^ N) <= R) { C += 1 } // C is the largest C such that B * C * 10 ^ N <= R R -= B * C * (10 ^ N) Q += C * (10 ^ N) // R is still positive. // Invariant A = B * Q + R is maintained. // We know B * 10^N > R because otherwise we // would have picked a larger C. N -= 1 // Invariant B * 10^(N+1) > R is maintained. } // By loop invariants, we have // A = B * Q + R and B * 10^0 > R. return (Q, R) } This is ten lines, not “astronomically complicated.”

chrisseaton 7y ago
This is just re-stating the algorithm for the umpteenth time. I can read the algorithm. I just can't intuit why it works or why it has been designed this way. I mean your very first line has a logarithmic operation that was not mentioned anywhere in your text or your comment! Just pops in there out of nowhere. I guess it's about the number of decimal digits? But why? Why are we doing things in decimal? A dense ten-line algorithm like this seems far more complicated than other algorithms we try to get school children to memorise.
- SamReidHughes 7y ago
  > But why? Why are we doing things in decimal? We’re subtracting off multiples of 10^N because that’s easy when you write your numbers in base 10. Try subtracting off multiples of 9^N, or multiples of N!, or some other choice, and you’ll see why.
  - chrisseaton 7y ago
    Ok, but do you see what I mean about how that part was just sitting there without any explanation? That's why I find it hard.
    - hackermailman 7y ago
      Wildberger has a channel that explains this from scratch, also shows a different method of long division https://m.youtube.com/playlist?list=PL5A714C94D40392AB https://m.youtube.com/playlist?list=PL5A714C94D40392AB His method for polynomials/derivatives is also interesting if you watch until the end, dead simple calculus.
    - xorcist 7y ago
      Is the question really why we train children on basic arithmetics in base 10? That could be meant shallow or deep. The shallow answer is because that's all you need to do to function in society (and conversely, while arguing with a police officer about the presumed base on speed limit signs may be fun, it is also pointless). The other answer probably needs to explore the question a bit further. Perhaps a good starting point is the fact that we almost universally share the physical characteristics of having ten fingers.
- seppel 7y ago
  > Why are we doing things in decimal? I think this is maybe the crucial part that you might be missing. All this long division (and long multiplication) stuff works on base-n represenations of numbers. I.e. if you have an number like 3376, it is actually a short hand for 3*10^3 + 3*10^2 + 7*10^1 + 6*10^0. And if want to divide it 4 and, suppose, you cannot do it in your head, you do it step by step, by clever regrouping with the distribute law: (3*10^3 + 3*10^2 + 7*10^1 + 6*10^0) / 4 == 3*10^3/4 + 3*10^2/4 + 7*10^1/4 + 6*10^0 / 4 == (3/4 does not work, so let merge the first two again) (3*10^3 + 3*10^2)/4 + 7*10^1/4 + 6*10^0 / 4 == (33)/4*10^2 + 7*10^1 /4 + 6*10^0 / 4 == (now we have progress) (33)/4*10^2 + 7*10^1 /4 + 6*10^0 / 4 == (32+1)/4*10^2 + 7*10^1 /4 + 6*10^0 / 4 == (32)/4*10^2 + (1)/4*10^2 + 7*10^1 /4 + 6*10^0 / 4 == 8*10^2 + (1)/4*10^2 + 7*10^1 /4 + 6*10^0 / 4 == (now merge the 1 and the 7 group) 8*10^2 + (17)/4*10^1 + 6*10^0 / 4 == 8*10^2 + (16+1)/4*10^1 + 6*10^0 / 4 == 8*10^2 + 4*10^1 + (1)/4*10^1 + 6*10^0 / 4 == 8*10^2 + 4*10^1 + (16)/4*10^0 / 4 == 844 The same works for other bases. If you were to implement some bignum library, you would also choose some base n representation for you numbers. Base 10 is not so optimal for computers, so maybe you chose base 2^32. If you then were to implement a division function, you would use similar algorithms.
  - dclowd9901 7y ago
    Hell yes! You finally made this clear for me why we can go through the dividend number by number (or power of 10 by power of 10) to apply the divisor. Thank you so much!
- edflsafoiewq 7y ago
  You don't have to do things in decimal, it's just convenient since you get the answer digit-by-digit. The idea of long division is just that to solve A/B, we can find another problem C/B we know the answer to and break it into the smaller problem A/B = (A-C)/B + C/B. For example, to solve 742/13, the normal way is to observe that 13×5=65 is as close as we can get to 74 without going over, so we can reduce this to 742/13 = (742 - 13×50)/13 + 13×50/13 = (742 - 650)/13 + 50 = 92/13 + 50 Now we only have to solve the simpler problem 92/13. All the long division stuff is just a book-keeping method for this data. But you could also use 13×4=52 and work out 742/13 = (742 - 520)/13 + 40 = 222/13 + 40 222/13 = (222 - 130)/13 + 10 = 92/13 + 10 92/13 = ( 92 - 91)/13 + 7 = 1/13 + 7 This gives the same answer, but it goes 40->50->57. The normal long division goes 50->57, so it never "goes back" on a digit it has decided on.

chrisseaton 7y ago

This is just re-stating the algorithm for the umpteenth time. I can read the algorithm. I just can't intuit why it works or why it has been designed this way. I mean your very first line has a logarithmic operation that was not mentioned anywhere in your text or your comment! Just pops in there out of nowhere. I guess it's about the number of decimal digits? But why? Why are we doing things in decimal? A dense ten-line algorithm like this seems far more complicated than other algorithms we try to get school children to memorise.

SamReidHughes 7y ago
> But why? Why are we doing things in decimal? We’re subtracting off multiples of 10^N because that’s easy when you write your numbers in base 10. Try subtracting off multiples of 9^N, or multiples of N!, or some other choice, and you’ll see why.
- chrisseaton 7y ago
  Ok, but do you see what I mean about how that part was just sitting there without any explanation? That's why I find it hard.
  - hackermailman 7y ago
    Wildberger has a channel that explains this from scratch, also shows a different method of long division https://m.youtube.com/playlist?list=PL5A714C94D40392AB https://m.youtube.com/playlist?list=PL5A714C94D40392AB His method for polynomials/derivatives is also interesting if you watch until the end, dead simple calculus.
  - xorcist 7y ago
    Is the question really why we train children on basic arithmetics in base 10? That could be meant shallow or deep. The shallow answer is because that's all you need to do to function in society (and conversely, while arguing with a police officer about the presumed base on speed limit signs may be fun, it is also pointless). The other answer probably needs to explore the question a bit further. Perhaps a good starting point is the fact that we almost universally share the physical characteristics of having ten fingers.
seppel 7y ago
> Why are we doing things in decimal? I think this is maybe the crucial part that you might be missing. All this long division (and long multiplication) stuff works on base-n represenations of numbers. I.e. if you have an number like 3376, it is actually a short hand for 3*10^3 + 3*10^2 + 7*10^1 + 6*10^0. And if want to divide it 4 and, suppose, you cannot do it in your head, you do it step by step, by clever regrouping with the distribute law: (3*10^3 + 3*10^2 + 7*10^1 + 6*10^0) / 4 == 3*10^3/4 + 3*10^2/4 + 7*10^1/4 + 6*10^0 / 4 == (3/4 does not work, so let merge the first two again) (3*10^3 + 3*10^2)/4 + 7*10^1/4 + 6*10^0 / 4 == (33)/4*10^2 + 7*10^1 /4 + 6*10^0 / 4 == (now we have progress) (33)/4*10^2 + 7*10^1 /4 + 6*10^0 / 4 == (32+1)/4*10^2 + 7*10^1 /4 + 6*10^0 / 4 == (32)/4*10^2 + (1)/4*10^2 + 7*10^1 /4 + 6*10^0 / 4 == 8*10^2 + (1)/4*10^2 + 7*10^1 /4 + 6*10^0 / 4 == (now merge the 1 and the 7 group) 8*10^2 + (17)/4*10^1 + 6*10^0 / 4 == 8*10^2 + (16+1)/4*10^1 + 6*10^0 / 4 == 8*10^2 + 4*10^1 + (1)/4*10^1 + 6*10^0 / 4 == 8*10^2 + 4*10^1 + (16)/4*10^0 / 4 == 844 The same works for other bases. If you were to implement some bignum library, you would also choose some base n representation for you numbers. Base 10 is not so optimal for computers, so maybe you chose base 2^32. If you then were to implement a division function, you would use similar algorithms.
- dclowd9901 7y ago
  Hell yes! You finally made this clear for me why we can go through the dividend number by number (or power of 10 by power of 10) to apply the divisor. Thank you so much!
edflsafoiewq 7y ago
You don't have to do things in decimal, it's just convenient since you get the answer digit-by-digit. The idea of long division is just that to solve A/B, we can find another problem C/B we know the answer to and break it into the smaller problem A/B = (A-C)/B + C/B. For example, to solve 742/13, the normal way is to observe that 13×5=65 is as close as we can get to 74 without going over, so we can reduce this to 742/13 = (742 - 13×50)/13 + 13×50/13 = (742 - 650)/13 + 50 = 92/13 + 50 Now we only have to solve the simpler problem 92/13. All the long division stuff is just a book-keeping method for this data. But you could also use 13×4=52 and work out 742/13 = (742 - 520)/13 + 40 = 222/13 + 40 222/13 = (222 - 130)/13 + 10 = 92/13 + 10 92/13 = ( 92 - 91)/13 + 7 = 1/13 + 7 This gives the same answer, but it goes 40->50->57. The normal long division goes 50->57, so it never "goes back" on a digit it has decided on.