Implementing factorial numbers in Objective C 2.0

I was implementing a function that would calculate factorial number for a given positive integer value. Factorial is denoted by n! and is the product of all positive integers less than or equal to n. For example:

6! = 1*2*3*4*5*6 = 720

So I implemented the function factorialX as follows:

-(double) factorialX: (int) value {
  double tempResult = 1;
  for (int i=2; i<=value; i++) {
    tempResult *= i;
  }
  return tempResult
}

Tried the code out and [self factorialX:6] does return 720 as it should. Then I tried it with bigger numbers, and the first problem noticed was with 13! which returned result 1,932,053,504 but it should have returned 6,227,020,800. Well that is a little bit strange, then I googled factorial a little bit and found this post: Factorial Function in Objective C, and the author points out: “That’s because 13! exceeds unsigned integer maximum of about 4,000 million on 32-bit platforms.”.

Ok, but I have tempResult defined as double, so why did I get the problem that is associated with int. It turns out that in the loop tempResult is multiplied by i (which is defined as int) and thus the whole calculation is done for int values.

The solution is to cast the i as double, thus changing the expression in the loop to:

tempResult *= (double) i;

Then if I try to calculate 13! I get the correct result of 6,227,020,800 πŸ™‚

Found that math.h indeed has a gamma function, so I could calculate any factorial n (where n can be any positive number) with lgamma(n+1).

(One question I have, which maybe of of the readers can solve is, how to calculate factorial of non integer value. For example 6.4!. If you input this into wolframalpha.com it shows you the result and it is calculated as Gamma(7.4), since Gamma(n+1) = n!. But Gamma function is defined as integral, and I do not know a way to calculate it numerically…)

Advertisements

, , ,

  1. #1 by John Cook on August 26, 2010 - 11:51 am

    The asymptotic series I give in my article will work for any argument, not just integers. However, that leaves open the question of what to do for smaller arguments.

    One approach is to use the identity Gamma(x + 1) = x Gamma(x) to turn small arguments into large arguments.

    Another approach is to use a different approximation for small arguments. You can find such approximations in Abramowitz and Stegun’s book Handbook of Mathematical Functions.

    • #2 by Ladislav Klinc on August 28, 2010 - 12:23 pm

      Hey John,

      I have one question that is unrelated to factorial, but still I would like to get your opinion on this problem I have.

      I have a class that does basic math, for cos, I have following definition for calculating cos if argument is inputted in degrees.

      -(double) cosX: (double) value {
      return cos((2*M_PI/360)*value);
      }

      M_PI is the PI constant from math.h file. If I try to calculate cos(90) it returns 6.123233E-17, where the result should have been 0. Why does that happen, is that because of M_PI only has x number of digits and the calculation to rad is not totally correct?

      Thanx

  2. #3 by John Cook on August 28, 2010 - 12:47 pm

    Floating point results are only good to about 15 or 16 significant figures in general. To see where that comes from, read http://www.johndcook.com/blog/2009/04/06/anatomy-of-a-floating-point-number/.

    Your answer was off by less than 10^-16, so that’s not unusual at all.

    • #4 by Ladislav Klinc on August 29, 2010 - 9:11 am

      Hey John,

      great article you sent me here…i subscribed to your blog πŸ™‚ Just curious do you do mostly math or computer science?

  3. #5 by John Cook on August 29, 2010 - 11:20 am

    Thanks. My career has been a mixture of math, software development, and management. The proportions of the three areas varies over time. Currently I’m doing more math than software development and not much management.

    Here’s more detail: http://www.johndcook.com/resume.html

  4. #6 by Dan Rathbun on August 30, 2010 - 5:51 am

    I think, reading the wiki page above:

    where n can be expressed a positive real = i (integer part) + r (real part):

    n! = (Ο€^(1/r))((ri+1)!/((r^(ri+1))(i!))

    But perhaps John should “check my assumption”…

  5. #7 by Dan Rathbun on August 30, 2010 - 5:54 am

    • #8 by Ladislav Klinc on August 30, 2010 - 5:25 pm

      Hey Dan,

      nice to see you once again on my blog πŸ™‚

      Interesting method you found, will try to compare it with the results this function returns compared to gamma function provided in the math.h.

      Anyway, do any of you guys have an iPad, I am finishing a calculator for iPad and would like to get some early feedback.

      Cheers,
      Ladislav

      • #9 by Dan Rathbun on August 31, 2010 - 6:17 am

        No iPad… sorry

      • #10 by Dan Rathbun on August 31, 2010 - 8:12 am

        BTW… that folmula I suggested, if the integer part is 0, your likely to end up with “div by zero” error.

        So .. it wouldn’t work in all cases.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: