### Re^3: Algorithm for cancelling common factors between two lists of multiplicands

by QM (Parson)
 on Aug 09, 2005 at 15:19 UTC Need Help??

So, now I've got my "schoolboy approach" working, care to point me at the methods clever people would use?
I was too lazy to look before, but now that I have, I was a bit off. On the other hand, I snuck in something similar in step 5 anyway. Here's what I remembered when I said that:

In QOTW #2 MJD considers the n_choose_k function that computes:

```sub n_choose_k {
my (\$n, \$k) = @_;
# f(\$n) = \$n!
return f(\$n)/f(\$k)/f(\$n-\$k);
}
He notes that the intermediate values are very large, even though the final result is not. He submits this replacement:
```sub n_choose_k {
my (\$n, \$k) = @_;
my \$t = 1;
for my \$i (1 .. \$k) {
\$t *= \$n - \$k + \$i;
\$t /= \$i;
}
return \$t;
}
and he notes:
\$t here is always an integer, and never gets bigger than necessary.
For your formula, this only applies to a small portion of the terms. You may be better off just ignoring MJD's improvement and proceeding as I outlined before.

-QM
--
Quantum Mechanics: The dreams stuff is made of

Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://482242]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others rifling through the Monastery: (11)
As of 2024-03-01 14:11 GMT
Voting Booth?
My favourite way to spend a leap day ...

Results (28 votes). Check out past polls.