From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-0.3 required=5.0 tests=BAYES_00, REPLYTO_WITHOUT_TO_CC autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: fc89c,97188312486d4578 X-Google-Attributes: gidfc89c,public X-Google-Thread: 1014db,6154de2e240de72a X-Google-Attributes: gid1014db,public X-Google-Thread: 109fba,baaf5f793d03d420 X-Google-Attributes: gid109fba,public X-Google-Thread: 103376,97188312486d4578 X-Google-Attributes: gid103376,public From: seebs@solutions.solon.com (Peter Seebach) Subject: Re: What's the best language to start with? [was: Re: Should I learn C or Pascal?] Date: 1996/08/08 Message-ID: <4udb2o$7io@solutions.solon.com> X-Deja-AN: 172952168 references: <31FBC584.4188@ivic.qc.ca> <01bb83f5$923391e0$87ee6fce@timpent.airshields.com> <4uah1k$b2o@solutions.solon.com> <01bb853b$ca4c8e00$87ee6fce@timpent.airshields.com> organization: Usenet Fact Police (Undercover) reply-to: seebs@solon.com newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada Date: 1996-08-08T00:00:00+00:00 List-Id: In article <01bb853b$ca4c8e00$87ee6fce@timpent.airshields.com>, Tim Behrendsen wrote: >> But your concept of what the "fundemental operations" are is completely >tied >> up in how specific hardware you've seen operates. Algorithms exist in >terms >> of abstract operations, not moves and branches. >Please name me the hardware that does not use moves and branches. That's not the *point*. Can you name me hardware with no protons? Can you name me hardware students are likely to learn on that doesn't use 5 volt power on the chip? However, the algorithm is *NOT DEPENDANT ON* moves and branches. I can do quicksort. In my head. On paper. I can sit down, with a pencil, and implement quicksort. You can say "these operations correspond to moves and branches", but really, moves and branches are corresponding to more general operations. If you teach the students that it's all moves and branches, they end up with more understanding of the specific hardware you teach them on, and current trends in CPU design, *and less of the algorithm*. I think algorithms should be taught on paper. *Away* from implementations on computer. Believe me, you understand quicksort much better after *DOING* it than you can from writing any reasonable number of implementations. >> In C, we write >> int >> gcd(int x, int y) { >> if (y == 0) >> return x; >> return gcd(y, (x % y)); >> } >This is an interesting case, because it is somewhat inefficently >implemented. If you're interested in speed, you would do... >int gcd(int x, int y) { > int z; > while (y != 0) > z = y; y = x % y; x = z; > return(y); >} Yes, you would. But so would at least one compiler I use. Internally. It doesn't *matter*. The realization is that, for non-zero x and y, the greatest common divisor of x and y is conveniently the greatest common divisor of y and (x mod y). *THAT* is the algorithm. The rest is fluff and nonsense. You can do that operation on paper, too. >Using my AIX compiler, I get a nominal improvement of about >10%, mostly because the speed of the modulo is much slower >than the inefficiency of recursion. So? What numbers are students entering that we *CARE* about the 10% speed difference? Optimization is an interesting thing to look at, but has nothing to do with algorithms. >My point is that how does a C programmer know that recursive >implementations are somewhat inefficient? The C programmer doesn't. And at least one compiler has been known to optimize tail-recursion into iteration, sometimes even in the 2-function case. >Recently the C/C++ >Users Journal had a little bite-sized article about a >general looping algorithm, where you could specify the number >of nested loops in a dynamic fashion. It was implemented >recursively. I wrote a letter back reimplementing the >algorithm non-recursively, and got like a 40% increase in >speed. Neat. And? The key here is that, once they showed you *the algorithm*, you could implement it however you want. The algorithm itself does not depend on your speed. >These sorts of issues are where code bloat comes from, and >it comes from naive implementations of "valid C syntax". No, they aren't. All of those put together wouldn't explain code bloat. We are seeing programs that are a factor of ten, or more, larger than we think they are. These would have to be *mind-numbing* idiocy. Microoptimizing will not fix it. Teaching people about *real* design principles will. It's worth observing good programmers rewriting. A good programmer will add features and cut the size of a program slightly; a bad programmer will bloat it hugely to add the feature. (Assuming the original program to be mediocre.) A good design will save more space and time than any amount of optimization of a bad design. >> But it also prevents them from learning the abstraction, and truly >> understanding the *principle* of the solution. >If the C abstraction is good, more abstraction must be better >then. How about we teach everything in APL, where we can >*really* abstract away the details? No data types, full >array operations. Talk about easy quicksort! I can write it >in one line of code using a handful of operations (my APL >is *really* rusty, so I can't give the example). I sorta favor lisp, which I don't know, but which is elegant and readable. >The student learns Quicksort, there is no question about it. >But what have they *really* learned? They've learned the algorithm itself. If you want to teach them about optimization and efficiency, go right ahead, but distinguish O(n) vs O(N^2) type efficiency from the kinds of efficiency you're talking about. Remember, that O() includes arbitrary constant multipliers and additions. 8N is just the same as N in complexity. I think it's a cool idea to teach people how to turn an 8N into a 4N algorithm. I don't think it's part of the algorithm, I think it's a different thing. >> Nonsense. A well designed and considered abstraction will generally lend >> itself to an efficient and elegant implementation. An ill-considered >> abstraction will spend more time on cruft than it will on solving the >problem. >Like recursive algorithms? I'm not sure what you're referring back to. Recursion is one of the first things I look to eliminate if I have an expensive implementation of what I know to be a good algorithm. But if the cost is small, it tends to stay, because it's frequently obvious how it's supposed to work. >Agreed; but there are general principles that can be learned >across *all* architectures. See follow up to Dan Pop post for >example of this. Sure, there are. And these, I think, can reasonably be taught. But that teaching doesn't need any assembly. -s -- Peter Seebach - seebs@solon.com - Copyright 1996 - http://www.solon.com/~seebs Unix/C Wizard - send mail for help, or send money for consulting! The *other* C FAQ, the hacker FAQ, et al. See web page above. Unsolicited email (junk mail and ads) is unwelcome, and will be billed for.