a bit of C++ code

[69dodge]

// probability of exactly r successes in n trials,
// if p is the probability of success in one trial.
// 0 <= p <= 1, 0 <= r <= n
double binom(int n, int r, double p) {
   const int x = std::min(r, n-r);
   double d = 1;
   int i = 0, j = 2*x+n;
   while (i < j) {
      const int k = d<1 ? i++ : --j;
      d *= k <   x   ?  n-k       :
           k < 2*x   ? 1./(2*x-k) :
           k < 2*x+r ?   p        :
                        1-p       ;
   }
   return d;
}

Enjoy.

 

[Angus McPresley]

That's some Stirling work you've done there.

 

[opqdan]

Boo for unreadable "? :" conditional structure, expecially when the compiler doesn't care and optimizes to the same assembly anyways.

Would have been awesomer if you had done it in a single line of obsfucated Perl.

Note that I am in no way commenting on your capacity as a developer. It is just that I feel that the "? :" structure is one of the most unreadable and worst programming practices ever... EVER. Use goto all you want, but the minute you use the short conditional, you sacrifice readability, extension and sanity. I once used it in an interview as a joke and almost got slapped.

 

[JamesM]

the minute you use the short conditional, you sacrifice readability, extension and sanity.

Once you learn what it means, it's no less readable than an if-then-else block. A single ternary operator is, anyway. Not sure about chaining them together.

Some people (e.g. Stephen Dewhurst in C++ Gotchas) have noted that there are places in C++ where you have to use an expression, like a constructor initializer list or a throw expression.

Anyone choosing to work with C++ is presumably bright enough to deal with obscure lookup rules to do with template and namespaces; in which case, the ternary operator is a walk in the park.

 

[opqdan]

Once you learn what it means, it's no less readable than an if-then-else block. A single ternary operator is, anyway. Not sure about chaining them together.

Some people (e.g. Stephen Dewhurst in C++ Gotchas) have noted that there are places in C++ where you have to use an expression, like a constructor initializer list or a throw expression.

Anyone choosing to work with C++ is presumably bright enough to deal with obscure lookup rules to do with template and namespaces; in which case, the ternary operator is a walk in the park.

Yeah, my post was more jocular than serious. Even I have used it in the past, but after over a decade of C++ work (since I was a wee boy), running into it still causes me to think twice.

I had a co-worker tell me once that "Good programmers don't use goto... but great ones do". I guess this works the same way (except that even great programmers shouldn't use goto).

 

[cyborg]

I consider ? a mathematical operator and if...then flow control. They may compile to equivalent structures but they do have different meanings. (And I know of at least two instances where they are treated as such in C derivatives that are not aimed at tradition interpretative environments (i.e. x86s)).

 

[Beerina]

Anyone choosing to work with C++ is presumably bright enough to deal with obscure lookup rules to do with template and namespaces; in which case, the ternary operator is a walk in the park.

That's true. Template classes make debugging and tracing a nightmare of understanding magnitudes more complex than a ternary operator, even a nested one like the above. (Which, BTW, I would use indenting to make more readable. Also probably parenthesis.)

 

[Beerina]

Something like this:

      d *= k <  x ?  n-k :
                           k < 2*x ? 1./(2*x-k) :
                                                  k < 2*x+r ? p :
                                                                  1-p;

 

[69dodge]

It's funny how programming styles differ so much.

I wasn't trying to obfuscate; I was trying to be clear.

I want to multiply d by something. Different somethings, depending on the value of k. But always "d *= something;". So that's what I wrote. I could have written

if ([i]k_satisfies_this_condition[/i])
   d *= [i]this_value[/i];
else if ([i]k_satisfies_that_condition[/i])
   d *= [i]that_value[/i];
else if ([i]k_satisfies_the_other_condition[/i])
   d *= [i]the_other_value[/i];
else
   d *= [i]yet_another_value[/i];

But that wouldn't make it explicit that the only difference between the different situations is the value by which d gets multiplied while what's common to all of them is that d gets multiplied by something.

Regarding indentation, is spreading things out really clearer than lining up the conditions in one "column" and the corresponding values in another? Or, analogously, would anyone write the above if statements as follows?

if ([i]k_satisfies_this_condition[/i])
   d *= [i]this_value[/i];
else
   if ([i]k_satisfies_that_condition[/i])
      d *= [i]that_value[/i];
   else
      if ([i]k_satisfies_the_other_condition[/i])
         d *= [i]the_other_value[/i];
      else
         d *= [i]yet_another_value[/i];

Hmm. Probably some people would, actually, now that I think about it. But I prefer the former. The idea behind the code isn't really that of a binary choice, one branch of which happens to be another binary choice, etc. The idea is a sort of generalized switch on k, in which each case comprises a range of values rather than just a single value, but where all the cases are conceptually at the same "level". Pascal's Case statement can do this, but C++'s switch statement can't, so we need to simulate it using a bunch of deeply nested if's. But we don't have to actually write them that way---deeply nested, that is---if doing so wouldn't express the underlying idea well, even though that's how the compiler interprets them.

Anyway, this is all just syntax. The interesting thing about the code, in my opinion, is the way it avoids overflow and underflow if at all possible, by interleaving the computations of n!/(n - r)!, 1/r!, p^r, and (1 - p)^{n - r} so as to keep d, as long as possible, near 1, i.e., far from 0 or infinity.

 

[Jekyll]

If I wanted to emphasise that pattern I'd go for;

int newFactor;
switch (k){
             case 1: newFactor =thing1;
             break;
            case 2: newFactor =thing2;
             break;
         etc. etc.
}
d*=newFactor;

And just trust that the compiler will work it's magic.
This is probably because I've been thinking in lisp for the last month and a half. It was a major effort not to write that in S-expressions.