8 ms·
Because the algorithm is so astronomically complicated that people can’t see any pattern or reason in it anymore and it becomes an opaque mystery. I have a PhD
by chrisseaton 7y ago
Because the algorithm is so astronomically complicated that people can’t see any pattern or reason in it anymore and it becomes an opaque mystery.
I have a PhD in computer science but I cannot understand long division.
- dboreham 7y ago>I have a PhD in computer science but I cannot understand long division I think you're trolling us a little: you could sit down with pencil and paper and think about how it must work and 20 minutes later you'd understand it, surely.
- chrisseaton 7y agoI have no intuitive understanding or mental model of the algorithm. I could follow the instructions if they’re written in front of me but I have never managed to understand why they work or to memorise them. I have a similar mental block for standard deviation - I always seem to have another ‘but why?’ question that eventually people answer with ‘because!’ and then we’ve both given up.
- dboreham 7y agoTry this? https://web.stanford.edu/class/ee486/doc/chap5.pdf https://web.stanford.edu/class/ee486/doc/chap5.pdf Edit: standard deviation is just a fancy name for root mean squared over the sample offsets. The square is there to deal with the fact that there are positive and negative offsets. The mean is the whole point of the exercise, and the root is to negate the fact that we squared earlier.
- chrisseaton 7y agoBut why not use the abs function or operator rather than squaring and rooting? This is how I always find maths and particularly statistics - I always just want to answer ‘but why’ and then people lose interest in explaining after a while.
- defen 7y agoThat exists too: https://en.wikipedia.org/wiki/Average_absolute_deviation https://en.wikipedia.org/wiki/Average_absolute_deviation Standard deviation is mathematically easier to work with though and has nice properties e.g. you can compute the standard deviation of combining a bunch of independent things by combining their individual standard deviations.
- smabie 7y agoBecause the derivative at 0 of abs is undefined.
- chrisseaton 7y agoWhy do I care about that though?
- smabie 7y agoTaylor series, calculating maxima/minima, etc. also standard deviations compose in a very nice way. All throughout math, we use squared terms instead of absolute value all the time because it’s convenient.
- cjfd 7y agoOkay, we have deviations from the mean. They are (0.1, 0.1, -0.1, -0.1). Or we have deviations from the mean (0.2, 0, 0, -0.2). I think is is pretty intuitive that in the second case the deviation is larger. In the first case there are only two differing values that are 0.2 apart. In the second case there are three differing values and some are 0.2 apart and others are 0.4 apart. Also, in the first case there are two pairs of equal value and in the second case there is only one pair that is of equal value. The squaring and rooting does this for you. Of course, other functions could do a similar thing for you. The squaring and rooting has nice mathematical properties especially if you consider the variance, i.e., omitting the square root. That is much more differentiable than an absolute value. Also, consider that the correlation coefficient consists of similar formulas. They all look like the theorem of pythagoras. This ties in nicely with the fact that observables can be seen as having angles in between them where the correlation coefficient is the cosine of these angles.
- rocqua 7y agoStandard deviation is a form of variance that has the same units as the mean. Whereas the variance has square units. This means the quantity of mean/variance depends on your choice of units, whereas the quantity of mean/standard deviation. Is constant no matter the units. Why do we care about variance? Because it is a nice and linear property. This means it is easy to calculate and manipulate. Moreover, the variance / standard deviation very nicely describe a Gaussian distribution (bell curve). This is a very important distribution because of the law of large numbers. Because we see bell curves so often, it is nice to have tools (std.dev) that work well with these curves. It should be noted that, in optimization problems, there can be reasons to try and minimize something other than variance. We tend to pick the variance / std.dev because it is familiar, easy to work with, and very efficient. Notably, the derivative of variance tends to be linear, which makes it pretty efficient to use in gradient descent.
- jampekka 7y agoThis is the right answer but maybe not to the right question. For most applications the linearity of variance does not really matter (e.g. when taking descriptives of a sample), at least in the way they are used/taught. Not that many appliers of statistics do computations where the mathematical properties of variance have any significance, and even when it does (e.g. ANOVA), most appliers don't really understand where it comes from. I think the OP's frustration in how computation of standard deviation as a quantity is just taught by rote in a cookbook manner is quite understandable. If one's not thought more in depth about distributions and estimation of their parameters, it really makes little sense. Whether the statistics should be taught more in depth is another question. The current state of the mathematics of statistics and probability is such that it needs quite heavy tools to do rigorously. And countless of hours of getting to know the quirky inconsistent notation. But until it is taught more rigorously, more intuitive measures of dispersion like MAD make a lot more sense for most applications. And I don't think it would be an unreasonable ask for the statisticians to lay out the "porcelain" for working with the more intuitive, if somewhat more analytically inconvenient measures. A bit like we don't require programmers to understand how transistors work.
- chongli 7y agoNow you’re talking about something different. The proof of the division algorithm is built up from a bunch of other machinery. It relies on the fact that the ring of integers is a Euclidean domain. Take a course in ring theory if you want to see how all of this machinery gets built up.
- blondin 7y agoGP must be talking about the shortcut procedure to do it that is taught in schools. also maybe they are specific about they way they do long division in the US? it was a surprise to me in college too and i have a french background. it's not how the french system does long division...
- sicariusnoctis 7y ago1. Long division uses a similar idea to Euclid's algorithm for GCD. Are you familiar with that? Regardless, both algorithms are divide and conquer algorithms. 6240 / 5 = divide(6240, 5) = divide(1240, 5) + 1000 = divide(240, 5) + 1000 + 200 = divide(40, 5) + 1000 + 200 + 40 = 1000 + 200 + 40 + 8 = 1248 ---------- 2. Regarding standard deviation, one of these bullets might help: - The normal distribution has exactly one shape, centered at x=0. But it's useful to apply two transformations to it: translation and horizontal stretch. To translate a distribution left/right, change its mean. To horizontally stretch a normal distribution, change its standard deviation. - Mean has units of length. Standard deviation has units of length. They tell you where the normal distribution is offset, and how wide it is. Mean and standard deviation are just measuring sticks/rulers for normal distributions. - When people talk about the standard deviation with any arbitrary data, they're usually assuming the data is normally distributed. If the data is not normally distributed, standard deviation no longer refers to the width of the normal distribution, so we lose that visualization. - With non-normally distributed data, the standard deviation is still useful as an analytical tool because taking the (sqrt of the) summed squares still gives us a number that grows as the data spreads further apart or if the distribution grows wider. There's a center point for the data (the mean), so to ensure you're measuring the overall spread of the data, you subtract the center point off each data point before squaring them. In other words, you're squaring deviations from the mean. And unlike the sum of absolute differences, the sum of squared differences (variance) is differentiable. Differentiability is a great property, so this is the standard way to compute a sum of deviations from the center.
- _bxg1 7y agoBud, 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 agoNo 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 agoTry 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 agoThis 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.
- marakv2 7y agoWhat? 35/350 (to simplify) Once is 325, twice is 300, X, X, X, we end up at 10 times is 350 divisible by 35. I'm wondering if I'm missing something (and if I am I'll own up to it lol)
- chrisseaton 7y agoLol I can't understand any of that. 'Once is', 'twice is' what does that mean? Once what is what? Twice what is what? You aren't even writing coherent English phrases how am I supposed to follow that?
- anewone 7y agoThey're referring to the number of times to subtract 35 from 350. Do it 10 times and you end up with 0, there is nothing more to divide and so 10 is the answer.
- pbhjpbhj 7y agohttps://news.ycombinator.com/item?id=21670030 https://news.ycombinator.com/item?id=21670030 maybe that's understandable?
- rocqua 7y agoIt sounds like you've memorized the very specific notational steps. But if you would have to come up with an algorithm for doing division using only integers with multiplication, subtraction and comparisons, you would come up with some equivalent to long division.
- theli0nheart 7y agoThis animated image of long division from Wikipedia might help show what’s going on: https://commons.wikimedia.org/wiki/File:LongDivisionAnimated.gif https://commons.wikimedia.org/wiki/File:LongDivisionAnimated... In essence, repeated subtractions. The blank areas to the right of each number are really just zeros.
- stjohnswarts 7y agoIf someone really showed it to you then you would understand it. In school you're just taught the algorithm.