http://qs321.pair.com?node_id=386925

Given the following contrived problem:

Print out the sum of the numbers from 1 to 100.
The average programmer would probably see this as something to be written with a loop, a nice O(n) problem, and might code it in perl as follows:
#!/usr/bin/perl -w use strict; my $n = 100; my $sum = 0; $sum += $_ for 1 .. $n; print "$sum\n";

Give the same problem to a mathematician, and might be seen as:

Sum(1..n) = n(n+1)/2
however it may ultimately be coded -- a nice O(1) problem.

The programmer will implement the algorithm provided in the most efficient way possible, hopefully, whereas the mathematician is the one who should provide the most efficient algorithm.

If these two work together, we might get a program like this:

#!/usr/bin/perl -w use strict; my $n = 100; my $sum = $n * ( $n + 1 ) / 2; print "$sum\n";
which runs in essentially the same amount of time for any number, n, rather than taking longer and longer to run -- see first program, above.

Many times I've seen people say, "Let the programmer solve it all...he'll make it go fast!" But what about the other disciplines? By involving the mathematician, her algorithms are implemented by the programmer to produce even faster code.

How many of your projects incorporate the disciplines necessary for the realization of the most efficient solution possible?

Pondering,
-v

Update:
Kudos to St. grinder for catchin' a typo: a few missing $ signs in the last example.

"Perl. There is no substitute."

Replies are listed 'Best First'.
Re: Problem Domains and Multiple Disciplines
by dragonchild (Archbishop) on Aug 30, 2004 at 15:34 UTC
    I think you're bringing up a very interesting distinction, which is too often blurred in our field(s). This reminds me of an interesting story -

    A friend of mine from college (call him George) went to the ACM programming contest. He brought his girlfriend along as a member of his team. The third member was assigned one problem to solve during the three hours. George solved the other five problems by writing the algorithms down on paper and handing them to his girlfriend (who knew enough to compile, debug, and test - she was a freshman CS major). George didn't actually touch a computer during the entire contest.

    A similar distinction can be made in game of Magic: the Gathering. A friend of mine is a world-class deck designer, but has never made much money at the tournaments. Another friend can win with any deck handed to him, but cannot design a world-class deck to save his life. A good team will have members of both types.

    Maybe this is similar to the difference between theoretical scientists, applied scientists, engineers, and businessmen.

    • The theoretical scientist figures out new avenues to explore.
    • The applied scientist actually explores the new avenues and figures out what the limits are.
    • The engineer figures out how to make a prototype of some new device, based on the new physics.
    • The businessman figures out how to actually bring that prototype to the public.

    A good example of this could be powered flight.

    • Galileo figured out that flight was possible.
    • Bernoulli figured out the optimum wing design for flight.
    • The Wright Brothers proved a prototype could work.
    • The Boeing corporation mass-produced airplanes.

    In our field, you have a similar hierarchy.

    • Charles Babbage figures out that computing is possible.
    • Dijkstra et al. actually figure out how to make computing work, algorithmically.
    • TheDamian actually figures out code that makes the crazy stuff work.
    • You and I make money on it.

    ------
    We are the carpenters and bricklayers of the Information Age.

    Then there are Damian modules.... *sigh* ... that's not about being less-lazy -- that's about being on some really good drugs -- you know, there is no spoon. - flyingmoose

    I shouldn't have to say this, but any code, unless otherwise stated, is untested

      First things first: the story about Gauss and the schoolteacher was in my high school math textbook, so I'm inclined to believe it. On a nifty note, while he recieved it at age 10, I recieved it on a Math entrance exam in grade 8 at age 13 - and came up with the same algorithm. Of course, I also confirmed it with my calculator afterwards (I thought I was smart, but I also didn't trust myself). A couple of years later I read the story of him coming up with it (and getting whacked because the teacher didn't believe he'd summed them), and I've been unneccesarily proud since.

      On a more on-topic note, there's a sig I see quite often that says "algorithm, algorithm, algorithm." I fully agree; this is not a "how do you approach it" question, but a "how well do you approach it" question. Analysing the problem and finding the best solution is part of writing good code, whether you call yourself a coder, a programmer, or a computer scientist.

      As for mathematicians with lovely O(N) solutions - a bigger problem is not size of N but size of constants. As an example, primality testing can now be done in polynomial time - a huge breakthrough for mathematicians - but in practice number sieves that give ~99.999% accuracy in constant time are used. There are great (in terms of O())solutions for lots of problems that have constants in over ten digits, but worse solutions with constants under a hundred that are used almost exclusively in practice. (It's been a while since I took an algorithms course, but I remember there were a couple of really good examples, even if I can't remember what they were.)

      I think Thompson's "when in doubt, use brute force" quote is fine - when making the first iteration of something. After all, it'll work. If anyone's tried using MS's Indexed Search and had it fail with a false negative, this is familiar - better traditional but correct than convoluted and fancy and purportedly better, especially when building small 'blocks,' since then when the blocks are weaved/welded together to make a complex whole, the interesting behaviour is where it should be - in the weaving/welding code, not in the basic blocks.

      As for mathematicians and their ilk being poor programmers - sure, quite often, but at the same time it's normally fixable. Eg, they'll have something written inefficiently, but it'll be something like not freeing memory when they're done with it, or recursing but not tail recursing, or the like. Easily fixable. They rarely make fundamental mistakes - writing code that does it, but does it in a way that no matter what cannot be efficient.

      And - known facts? If told, using basic integer math, to find all divisors of a number N, what would you do? Loop through 1 to N, finding the remainder, and whenever it's 0 saving the result? No, you'd save the result at 0 and then divide by that number to get a second divisor, and stop at sqrt(N). It's reasonably obvious. Now, if he was asking for something truly from another field, for instance the surface area to volume ratio of a strange solid, then sure. But we, as programmers, don't get that every day. We do, quite frequently, get "from i to n, do X" - even if X is a simple sum - and we should be able to handle slightly offbeat questions along those lines without any difficulty.

        As an example, primality testing can now be done in polynomial time - a huge breakthrough for mathematicians - but in practice number sieves that give ~99.999% accuracy in constant time are used.

        This reminds me of a recent post on http://lambda-the-ultimate.org where (twards the end) the author makes a comment on "Physics vs. Mathematics" (the thread it's attached to is a rather interesting debate on modern type systems). Math majors would rather have their toenails chewed off by chipmunks than use a theorum that wasn't completely true for every little edge case. But a Physics major (and Engineering majors, too) almost have to in order to get work done.

        Orbits of planetary bodies comes to mind. Newton presented some simple equations that almost, but not quite, fit the data (he passed this off as God fiddling with the universe). Einstein gave a much more complex equation that perfectly fit the data. However, Newton's equation is still prefered by Physicists because it's easier to work with, and the minor differences in the outcome usually don't matter.

        As programming is more or less an Engineering discipline, we can often get away with things that aren't mathmatically pure. I suspect that good programers know their math, but also know when to throw it away.

        "There is no shame in being self-taught, only in not trying to learn in the first place." -- Atrus, Myst: The Book of D'ni.

      Hmmmm... I like what you say in general, but I have to complain about your treatment of women in your anecdote. I'm not sure if you realize the condescending treatment of "George's girlfriend".
      1. She is only known by her relationship to George. She could have been referred to as a team member with a name, say Anna. You might as well have called her "the missus", or "the little lady."
      2. She "knew enough" to code and debug the programs. Like once you have written the algorithm the code practically writes itself. Only if you are a brilliant programmer, perhaps. There are lots of issues after the design stage - what language to implement the algorithm it, getting it to actually work, etc.
      3. Why did you have to explain her credentials at all? You didn't mention that George was a senior Math major and that is why he was a brilliant algorithmist.
      I'm pretty sure you didn't mean any harm, of course, but I thought I should point this out nevertheless.
        The comment meant to say that she was a freshman who knew the mechanics of using a computer to enter and manipulate code, but did not have the experience to solve complicated problems and develop new algorithms on the fly. The story as I heard it had a girl in the typist's role, so that is how I retold it. It would have been just as meaningful if I replaced "George's girlfriend" with "George's freshman typist". It most definitely would have been less insulting, and I'll retell it as such, in the future. The reason for describing her credentials was to cast her in the role of the "codeslinger" and to cast 'George' in the role of the "algorithm master", as per the OP.

        A similar story happened with me as the main character. My last semester at college also had the ACM contest occurring within it. This year, we only had four students interested in "wasting" a Saturday afternoon on programming tasks. There was me, the resolute (dissolute?) super-senior and three other students, who had less combined semesters in college than I did by myself. (I was on my 9th in 5-and-a-half years, if you're wondering.) So, we divided the teams up as so - I was team A and they were team B. Out of some 54 teams in our division, I came in 9th, solving 5 problems and having a solution for the 6th. I would've solved six and come in 4th had I realized that int on Windows was 2 bytes long, not the four I was used to from Unix. Tracking that down lost me 30 minutes and about 70 points. The other team solved 2 problems and had solutions for 2 more.

        The only difference between me and the members of team B was exposure to over a hundred algorithms and techniques they had never seen. That's the same difference that 'George' had over his teammates, including his girlfriend / typist. (She later went on to be a valued member of subsequent ACM contest teams from my school, graduated with a 3.7 GPA in computer science, and was a close friend of mine.)

        ------
        We are the carpenters and bricklayers of the Information Age.

        Then there are Damian modules.... *sigh* ... that's not about being less-lazy -- that's about being on some really good drugs -- you know, there is no spoon. - flyingmoose

        I shouldn't have to say this, but any code, unless otherwise stated, is untested

        Since the contest some things have changed... Most importantly George has had a series of transgender procedures and his girlfriend (GF) was the recipient of the removed appendage(s). Because of this gender swap she (GF->BF) now takes the lead in all intellectual contests while George (Georgia) does the grunt work of coding.
Re: <<Problem Domains and Multiple Disciplines>>
by Anonymous Monk on Aug 30, 2004 at 14:45 UTC
    It's the difference between a programmer, and a computer scientist. The basis of computer science is not computers, and nor is it programming. The basis is math.

      As in a quote I put on my homenode long ago:

      Computer science is no more about computers than astronomy is about telescopes.
      — Edsger W. Dijkstra

      Makeshifts last the longest.

      A sum of a natural sequence is taught in school. Fourteen years old schoolboy is not a computer scientist yet, but he can be a pretty good programmer. :)
Re: Problem Domains and Multiple Disciplines
by ccn (Vicar) on Aug 30, 2004 at 14:27 UTC

    The difference between the first code and the second one is the difference between a coder and a programmer

Re: Problem Domains and Multiple Disciplines
by BrowserUk (Patriarch) on Aug 30, 2004 at 15:11 UTC

    Personally, I'd code that as:

    my $sum = 5050;

    Examine what is said, not who speaks.
    "Efficiency is intelligent laziness." -David Dunham
    "Think for yourself!" - Abigail
    "Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - tachyon
      I would do print 5050; ;-)

      In response to the original post, you don't need to be a mathematician to know this. I heard about this formula in elementary school, with an anecdote supposedly involving Carl Friedrich Gauss and a nasty math teacher.

      Regarding the "programmer/mathematician" comparison, be careful, because sometimes you see naive "mathematicians" that:

      • suggest a wonderful but extremely complicated O(N) algorithm, without noticing that for a given aplication N is always between 0 and 2, and considering the overhead, the N^2 method is actually faster.
      • don't care about the implementation issues of the language they are using, so they use a theoretically pretty but unnecessary recursive implementation that ends up being too slow or resource-intensive.

      The point that thinking is sometimes better than brute force is well taken, but sometimes the opposite is good enough or better. From the Jargon File:

      Ken Thompson, co-inventor of Unix, is reported to have uttered the epigram "When in doubt, use brute force". He probably intended this as a ha ha only serious, but the original Unix kernel's preference for simple, robust, and portable algorithms over brittle 'smart' ones does seem to have been a significant factor in the success of that OS. Like so many other tradeoffs in software design, the choice between brute force and complex, finely-tuned cleverness is often a difficult one that requires both engineering savvy and delicate esthetic judgment.

      That's a bad idea. You should code it as

      my sum = 100 * 101 / 2;
      or something like that.

      I know this from practice, as I once accidentally wrote 8092 instead of 32*256 in a program and had a hard time finding out why it wouldn't work. A computer can do arithmetic better than any of us.

        I did it with a computer...in the shape of a calculator:)

        I get your point, but unless the constants 100, 101 and 2 have some meaning in context, you've just advocated magic numbers.

        A well named constant, that made sense in context, would be preferable.


        Examine what is said, not who speaks.
        "Efficiency is intelligent laziness." -David Dunham
        "Think for yourself!" - Abigail
        "Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - tachyon
Re: Problem Domains and Multiple Disciplines
by perlfan (Vicar) on Aug 30, 2004 at 16:48 UTC
    I have learned that although mathematicians can "code" a solutions, it is often one that "works", but there is no guarantee that it will be the most efficient. This is what computer scientists study, and more often than not, they are the only ones concerned with efficiency/performance.

    At some point, especially once a programmer gets through the learning curve for his language of choice, efficiency starts becoming a bigger focus by trying to figure out "better" ways of doing things.

    I have worked with oceanographers, mathematicians, chemists, and physicists, and I can tell you from first hand experience that they are better suited at doing research than writing good/efficient code. Often times an experienced programmer, not necessarily with a CS background, can run circles around some of the crap that these otherwise smart people write. In fact, many of them have a problem in thinking that because the are experts in <insert your discipline here>, that they will write the best code; and therefore neglect to consult a *real* programmer. Oneday they realize that their code works but is crap, so they dump it on the computer guy to fix it - am I bitter? Of course not ;)
Re: Problem Domains and Multiple Disciplines
by davido (Cardinal) on Aug 31, 2004 at 06:28 UTC

    Computer Programming is a trade. Computer Science is a dicipline, a study, and an intellectual pursuit. A programmer who appreciates and understands the science behind effective programming will write algorithmically efficient code when appropriate. And if he has a foot firmly planted in reality, he won't waste a lot of time devising the perfect algorithm when the objective isn't execution efficiency so much as getting it up and running soon. Fortunately for us, CPAN has a plethora of modules written by Computer Science enthusiasts, that can be applied to the needs of the Computer Programming trade.


    Dave

Re: Problem Domains and Multiple Disciplines
by artist (Parson) on Aug 30, 2004 at 18:54 UTC
    Known facts: Your improved solution is using a 'known fact' from other field. It often helps to know little bit about other fields to make your application faster, especially if your problem doamin involves that field. It is upto you, how do you know other facts and make efficient usage of them.

    Just like your life, everybody can give 2 cents from their perspective, no matter how expert you are. They have their own perspectives to look at the problem.. (remember light bulb jokes).

    Mathematics and Algorithm have heavy impact on programming. We develop libraries to solve such things in most efficient ways so that you don't have to deal with it on personal level.

      I'm currently reading Dale Carnegie's How to win friends and influence people (an excellent book for all nerds and geeks). In it, he quotes at several places many smart people who say that every single person they would meet could teach them something.

      Sometimes, Hubris is a bad thing ...

      ------
      We are the carpenters and bricklayers of the Information Age.

      Then there are Damian modules.... *sigh* ... that's not about being less-lazy -- that's about being on some really good drugs -- you know, there is no spoon. - flyingmoose

      I shouldn't have to say this, but any code, unless otherwise stated, is untested

Re: Problem Domains and Multiple Disciplines
by hsmyers (Canon) on Sep 01, 2004 at 13:16 UTC
    Having started out long ago as a sculptor and silversmith, I've never approached programming with mono-disciplinary background! It's even possible to apply disciplines you don't possess to the code you are writing---ever see what Mathematica can do to equations (simplifying them that is)?

    --hsm

    "Never try to teach a pig to sing...it wastes your time and it annoys the pig."
Re: Problem Domains and Multiple Disciplines
by Ytrew (Pilgrim) on Sep 15, 2004 at 15:16 UTC
    At my university, Computer Science was a department in the Faculty of Mathematics, but I understand your distinction between mathematicians and programmers. A professional statistician or applied mathematican may know algorithms I've never heard of.

    However, I'm not sure calling in specialists is a very practical idea in the business world. They all want to be paid, and they usually cost a lot. The more they know, in general, the more they cost.

    And sometimes, what the programmer should code may still be the O(n) solution, not the O(1) solution. The O(n) solution is slower, but it's simpler, more obviously correct to someone who doesn't know the mathematics involved, and "fast enough". A simpler solution may also be more maintainable.

    Three weeks from now, when someone from the marketing department steps in and says 'We need you to omit all the odd primes from that calculation, when run for the following customers', you'ld have to throw away Gauss's formula -- it doesn't apply.

    You can keep the loop from the other version, and add an if statement, "if (is_odd_prime($i) && is_special_customer($cust)) { $sum += $i }". Admittedly, the whole thing is toy problem, but hopefully you see my point.

    In some applications, fast code is important. In almost all applications, correct code is as important. Optimizing for verifyably correct, maintainable code is not the same as optimizing for speed, but it's arguably more important. And for businesses, the optimization computation really comes down to the utility of the application in terms of cost savings versus the development and maintainance costs.

    So, yes, your points about cross-disciplinary understanding are well taken, but they need to be balanced with the costs involved, as well.

    Just some musings, -- Ytrew