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=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 109fba,baaf5f793d03d420 X-Google-Attributes: gid109fba,public X-Google-Thread: 103376,97188312486d4578 X-Google-Attributes: gid103376,public X-Google-Thread: fc89c,97188312486d4578 X-Google-Attributes: gidfc89c,public X-Google-Thread: 1014db,6154de2e240de72a X-Google-Attributes: gid1014db,public From: miker3@ix.netcom.com (Mike Rubenstein) Subject: Re: What's the best language to start with? [was: Re: Should I learn C or Pascal?] Date: 1996/08/10 Message-ID: <320bf032.7193774@nntp.ix.netcom.com>#1/1 X-Deja-AN: 173271962 references: <31FBC584.4188@ivic.qc.ca> <01bb83ad$29c3cfa0$87ee6fce@timpent.airshields.com> <4u89c4$p7p@solutions.solon.com> <01bb83f5$923391e0$87ee6fce@timpent.airshields.com> <4uah1k$b2o@solutions.solon.com> <01bb853b$ca4c8e00$87ee6fce@timpent.airshields.com> <320b35a2.43769707@nntp.ix.netcom.com> <01bb8609$59339140$87ee6fce@timpent.airshields.com> organization: Netcom x-netcom-date: Fri Aug 09 9:24:54 PM CDT 1996 newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada Date: 1996-08-09T21:24:54-05:00 List-Id: "Tim Behrendsen" wrote: > Mike Rubenstein wrote in article > <320b35a2.43769707@nntp.ix.netcom.com>... > > "Tim Behrendsen" wrote: > > > Peter Seebach wrote in article > > > <4uah1k$b2o@solutions.solon.com>... > > > > 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); > > > } > > > > I don't understand how going into an infinite loop when y != 0 > > improves the speed? I guess I cut class that day. > > > > Nor do I see how dividing by 0 (when y == 0) is an improvement? > > Perhaps I just cut too many classes. > > > > Let's review the bidding. Peter gives an algorithm. You claim that > > knowledge of assembly helps one understand it better and produce a > > program that goes into an infinite loop if y is not zero and divides > > by 0 if y is zero. > > > > Perhaps you meant > > > > int gcd(int x, int y) { > > int z; > > while (y != 0) > > { z = y; y = x % y; x = z; } > > return(y); > > } > > > > This avoids the infinite loop, but can be made even more efficient: > > > > int gcd(int x, int y) > > { > > return 0; > > } > > > > Of course this isn't quite equivalent to Peter's function. > > > > I guess, like Peter, I'm a little thick today. Please explain again > > how knowing assembly language helps one understand algorithms? I got > > a little confused when you transformed Peter's correct, but slightly > > inefficient function into an infinite loop. > > Yes, you're right; my typo proves all my arguments false. How can I > have been such a fool? Perhaps because you think like an assembly language programmer -- there's an enormous advantage to clear code. Efficiency may, or may not be important. Yet you assumed that it was worthwhile to make Peter's code more efficient. This is the assembly language programmer's disease. If I were doing a lot of gcd calculations, I'd certainly try to optimize the program. But in most applications very little of the code is time critical. Where it is not, clear code wins over efficient code. Furthermore, when teaching algorithms Peter's code is what you want, at least for the first cut. It shows a general technique of algorithm design, reducing a problem to a similar but easier one, that your code, even if written correctly, hides. It's near September, and I feel safe in predicting that we will soon see quite a few posts asking how to solve the towers of Hanoi puzzle. Those who understand Peter's formulation of Euclid's algorithm will do better than those who only know yours. Michael M Rubenstein