Mathematics for Computer Science [pdf] • Hacker News Board

Post by garethrees » Tue, Mar 14, 2017, 10:37 PM UTC

gjm11 wrote: post #78

mattmanser wrote: post #61

Earlier quoted context omitted.

Honest question, why would you spend weeks doing proof by induction? Looking it up, I think I did that when I was 16, but I've never used it while programming. I can't see a single benefit to knowing it for programming. Been programming professionally for 12 years now. What am I missing? Why do you think it's important?

In some sorts of code, you can get a lot of mileage from "loop invariants" and "loop variants". Understanding these is more or less the same as understanding proof by induction. Whether you are missing anything depends on whether you ever write the sort of code that benefits from this. (Even if you do, you still might not be missing anything. You might be comfortable with loop invariants but not have connected them w…

(Slightly off topic, but maybe still interesting.) I used to write binary searches like yours, with two tests per iteration:

    while lo


But then I discovered that there's an alternative approach which has only one test per iteration:
    while lo 

If comparisons are expensive compared to other operations then this is twice as fast as the variant with two comparisons per iteration. (If comparisons are cheap, as they are if you are searching an array of numbers in a compiled language, then it doesn't make much difference.)