3 ms·

Bud, I really hope you can grasp more complicated algorithms than that if you have a PhD in computer science. It's one thing to call it unintuitive and not wort

by _bxg1 7y ago

Bud, I really hope you can grasp more complicated algorithms than that if you have a PhD in computer science. It's one thing to call it unintuitive and not worth your time, but let's not be hyperbolic.

chrisseaton 7y ago
No I have genuinely tried to learn it and I have no understanding why I am doing any of the steps in the algorithm.
- SamReidHughes 7y ago
  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.
- LifeLiverTransp 7y ago
  So you know the how, but not the why. The why knowledge is genrally more valuable, because basic principles are reused over and over, while the how changes often. And its hard to recover from a how change, if you do not know the background whys applied. Thats why university focuses so much on the whys, and doesent give a fuck about the hows. Hows can be learned fast. Hows can even be deduced if you know the whys. If you now a recipe to brew beer - you can create your own brew. If you know about microbiology of fermentation, you can deduce why the recipe sometimes doesent work...
notacoward 7y ago
Some people are just pathological hyperbolists. I think that's really the handicap here, not any facility for understanding algorithms.

by _bxg1 7y ago

chrisseaton 7y ago

No I have genuinely tried to learn it and I have no understanding why I am doing any of the steps in the algorithm.

SamReidHughes 7y ago
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.
LifeLiverTransp 7y ago
So you know the how, but not the why. The why knowledge is genrally more valuable, because basic principles are reused over and over, while the how changes often. And its hard to recover from a how change, if you do not know the background whys applied. Thats why university focuses so much on the whys, and doesent give a fuck about the hows. Hows can be learned fast. Hows can even be deduced if you know the whys. If you now a recipe to brew beer - you can create your own brew. If you know about microbiology of fermentation, you can deduce why the recipe sometimes doesent work...

notacoward 7y ago

Some people are just pathological hyperbolists. I think that's really the handicap here, not any facility for understanding algorithms.