[havannas]

Yep, here's a little project where I'm trying to get values out of Pascal's triangle using this equation as the basis:





I have 2 questions if anyone feels up to it:

1. Is their a Cocoa/C function that already does ! multiplications/iterations so I can ditch my for loops.

2. When my row values get near the 35th row and above it falls apart... I get 'Inf' returns in my field..... Is this an error in the function? or is the number too big to be held in the variable?

Thanks in advance anyone who can help.






------------------------------------------------------------------------------

#import "rowlController.h"

@implementation rowlController

- (IBAction)myTriangle id)sender
{

float spac, fill, leftover, a, b, c, i, tote;
NSString *overError = @"'Filled' must be = or < 'Spaces'.";

spac = [theSpaces floatValue];
fill = [theFilled floatValue];
leftover = spac - fill;

if(leftover == 0)
{
leftover = 1;
}

a = 1;
b = 1;
c = 1;


if (spac>=fill)
{


for (i=1;i<(spac+1);i++)
{
a = a * i;
}

for (i=1;i<(fill+1);i++)
{
b = b * i;
}

for (i=1;i<(leftover+1);i++)
{
c = c * i;
}

tote = a/(b*c);

[thePossible setFloatValue:tote];


}
else
{
[thePossible setStringValue :overError];
}

}

@end


[This message has been edited by havannas (edited 05-15-2001).]

[This message has been edited by havannas (edited 05-15-2001).]

[DayLateDon]

Hello ...

35! is approximately 10^40, which is too much trouble to be storing in a variable, when the largest value [35:k] achieves is about 4.5x10^9.

You can lessen some computational expense by taking advantage of cancellation in the fraction. Cancelling (n-k)! from the numerator and denominator leaves:

[n:k] = (n-k+1)x(n-k+2)x...x(n-1)xn / k!

(Note that the top and bottom have k factors. You can build the elements of the final computation within one loop instead of three.)

Since [n:k] = [n:n-k], you can be even a little more thrifty by computing

[n:k] = (n-h+1)x(n-h+2)x...x(n-1)xn / h!, where h = min(k,n-k)

This way, you begin your computation after having cancelled the larger of factors k! and (n-k)!. (You won't find your self computing 35! twice just to get the value 1 in [35:35].)

[Edit: Replaced a stray "k" with an "h".]


[This message has been edited by DayLateDon (edited 05-15-2001).]

[mccullocht]

1. Is their a Cocoa/C function that already does ! multiplications/iterations so I can ditch my for loops.

I don't know of any Cocoa/C functions that do factorials (n!), but you could write a little recursive c function to do it like so:

Code:
int factorial(int n)
{
  if (n <= 0)
    return -1;  /* don't take factorial of negative numbers!!! */

  if (n == 0)
  {
    return 1;
  }
  else
  {
    return (n * factorial(n - 1));
  }
}

It makes the problem somewhat simpler.

2. When my row values get near the 35th row and above it falls apart... I get 'Inf' returns in my field..... Is this an error in the function? or is the number too big to be held in the variable?

Well, I don't know exactly why you need to use floating point numbers, but to prevent overflow in this case you really ought to change all your 'float's to 'double's. Doubles are more precise and can go a lot higher before overflowing. If you don't need to use floating point numbers, go with 'long long's.

mccullocht

[havannas]

Wow,thanks alot to both of you.

It's been a long time since if done any algebraic factoring so it's gonna take a little while to wrap my head around equations .

I did think of moving it to it's own function but i didn't think of using a recursive one... too used to crashing codewarrior in Os9, heh.

I shouldn't being using the float's, I just seemed to get some weird errors with int's earlier on. So 'long's are the larger int variable then? That's kinda what I'm looking for.

Sorry, I've only had a couple lighweight c++ courses and those were geared more towards multimedia as they were taught at an art school rather than a CS type thingy.

Anyway thanks alot, these already have me pointed in a more correct direction.

[int69h]

When in doubt, check /usr/include/machine/limits.h

I would recommend using unsigned long long.

[ladavacm]

int happens to be exactly as long as long.

However, your problem is that you are actually computing factorials, which is not at all necessary--please heed the advice of the poster who explained that most of the factors actually cancel out, and need not be computed at all. Furthermore, to further avoid overflows, please remeber that

(a * b * c) / (d * e * f)

is almost the same as

(a / d) * (b / e) * (c / f)

in which case you are multiplying together much lesser quantities (i.e. instead of dividing a big number by another big number, you multipy a lot of small numbers)

Beware of the almost the same part, though: the statement holds for infinitely precise rational numbers--it does not hold for limited precision float/double, nor integers. However, since the binomial coefficients are in fact integers, one should be able to find a particular permutation of operands and avoid rounding problems altogether