Thread: Find bigest number!!! Help!!!!!!

  1. #1
    Registered User
    Join Date
    May 2003
    Posts
    5

    Question Find bigest number!!! Help!!!!!!

    Im about writing a program input number, implemented it with apply this formular: n!/(n/2)!, using recursive function. Question is: How would I be able to find the largest number of n without overflowing, which number is too big for the computer handle?

    So far, I just had this program to calculate n!/(n/2)!

    int GetVal(int n);

    int main()
    {
    int n;
    scanf("%d", n);

    printf("Result found: %c", GetVal(n)/GetVal(n/2);
    return 0;
    }

    int GetVal(int n)
    {
    if (n == 1)
    {
    return 1;
    }
    else
    return n * GetVal(n - 1);
    }

    Any help would be highly appreciate!

  2. #2
    Registered User
    Join Date
    Oct 2002
    Posts
    98
    which number is too big for the computer handle?
    This value is limited by the datatype of the variable you use to hold the input number. According to my sturdy manual, a signed int has a range of -2147483648 to 2147483648; a float has a range of -3.4E+38 to 3.4E+38; a double has a range of -1.7E+308 to 1.7E+308.

    So if you use double as the datatype, your value of n can become colossal before overflowing!

    The actual code you subject the variable bears no relevance to its upper boundary.

  3. #3
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    But, using doubles and floats, it isn't anywhere near as precise as ints or long ints. You have to decide which is more important: precision (long int), or large numbers and decimal places (double/float).
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  4. #4
    Registered User
    Join Date
    Mar 2003
    Posts
    19

    Hum

    I would have to disagree with the previous answers.

    Factorials grow extremely fast, so I doubt you will be able to reach n=50 before you will overflow, regardless of whether you use doubles or ints. 50! is MUCH bigger than 10^38.

    Keeping this in mind, it should be very easy to manually figure out what the limit is. Just feed bigger numbers until it crashes or you get a weird result.

    Then you add an error message if n is bigger than whatever this value is.

    Tor

  5. #5
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826

    Re: Hum

    Originally posted by f97tosc
    I would have to disagree with the previous answers.
    Well then you're intentionally ignorant. limits.h does tell you how much your compiler will allow for variable sizes. That's why it's called "limits".

    Furthermore, floats and doubles are less precise than ints/longs.

    Quzah.
    Hope is the first step on the road to disappointment.

  6. #6
    Registered User
    Join Date
    Mar 2003
    Posts
    19

    HUm again

    Well, what is really needed is to find the

    biggest n, such that n! <= limit_value

    Even if you know limit_value from limit.h or whatever, that does not tell you what your biggest input value n is (only the biggest answer value n!).

    In order to find the biggest n, you can try to solve the problem mathematically; this would be a pain but I think it is possible.

    However, if you are familiar with faculties you know that they grow extremely fast, so the biggest input n will be quite small. Thus the simplest way is probably to try n=20, n=30 and so on until n! have passed the limit value.

    Tor

  7. #7
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826

    Re: HUm again

    Originally posted by f97tosc
    Well, what is really needed is to find the

    biggest n, such that n! <= limit_value

    Even if you know limit_value from limit.h or whatever, that does not tell you what your biggest input value n is (only the biggest answer value n!).
    What are you talking about? Of course it tells you the biggest number you can input. The limit is the biggest number. Period. You can't input a number bigger than the limit. How is this difficult to understand?

    Example: a signed char, it will let you input 127. In limits.h, guess what the limit is set to? 127. Not a hard concept.

    Quzah.
    Hope is the first step on the road to disappointment.

  8. #8
    Registered User
    Join Date
    Mar 2003
    Posts
    19

    Re: Re: HUm again

    Originally posted by quzah
    You can't input a number bigger than the limit. How is this difficult to understand?
    No of course you can't input a number that is greater than the limit.

    But in addition, if your program somwhere generates a number that is larger than the limit, then you are in trouble as well.

    And my point is that even for a relatively small input value (such as n=50, which is much smaller than the limit), the program will (try to) generate an answer that is bigger than the limit, and thus cause trouble. And that is what this guy needs to watch out for.

    Tor

  9. #9
    Registered User
    Join Date
    May 2003
    Posts
    5
    I rekcon using limits.h could solve this problem, but how would you be able to implement code for it? Have a look at the function

    int GetVal(int n)
    {
    if (n == 1)
    {
    return 1;
    }
    else
    return n * GetVal(n - 1);
    }

    It will run till n = 1, then return to value. As soon as value returned gets over limit. It should print the previous value of n (that n is the biggest number - i think). How could you find n?
    Please help!!!

  10. #10
    Registered User
    Join Date
    Mar 2003
    Posts
    19
    Try running this function

    Code:
    void trymax(void)
    {
    int i;
    for(i=1;i<25;i++)
    {
    GetVal(i);
    }
    }
    Read the output column and you will see where you passed the limit.

    If you make n to a double you might reach a maximum input value of 50 with some loss in accuracy.

    Tor

  11. #11
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005

    Re: Find bigest number!!! Help!!!!!!

    Originally posted by Chook
    Im about writing a program input number, implemented it with apply this formular: n!/(n/2)!, using recursive function. Question is: How would I be able to find the largest number of n without overflowing, which number is too big for the computer handle?
    An example using limits.h and an integral type might be as follows.
    Code:
    #include <stdio.h>
    #include <limits.h>
    
    int main(void)
    {
       unsigned long n;
       for ( n = 2UL; n < 200UL; n += 2UL )
       {
          /* calculate n!/(n/2)! */
          unsigned long i, result = n, n2 = n / 2UL;
          for ( i = n - 1; i > n2; --i )
          {
             /* check for possible overflow before multiplying */
             if ( result > ULONG_MAX / i )
             {
                printf("overflow warning: %lu * %lu would exceed %lu\n",
                       result, i, ULONG_MAX);
                return 0;
             }
             /* multiply will not overflow */
             result *= i;
          }
          printf("%lu!/%lu! = %lu\n", n, n2, result);
       }
       return 0;
    }
    
    /* my output
    2!/1! = 2
    4!/2! = 12
    6!/3! = 120
    8!/4! = 1680
    10!/5! = 30240
    12!/6! = 665280
    14!/7! = 17297280
    16!/8! = 518918400
    overflow warning: 1764322560 * 10 would exceed 4294967295
    */
    A similar approach could be used with floating point; DBL_MAX and friends are found in float.h.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  12. #12
    Banned
    Join Date
    May 2003
    Posts
    124

    unsigned long?

    Why do you have to declare n as usigned long, and not only as long? Does it make any difference?

  13. #13
    Banned
    Join Date
    May 2003
    Posts
    124
    I know that unsigned takes only possitive values for n, but it doesn't have to be used, does it?

  14. #14
    Registered User
    Join Date
    Oct 2002
    Posts
    98
    The long int datatype varies from -x -> 0 -> x. The unsigned equivalent doesn't have to include negative numbers, so varies from 0 -> 2x. This allows for a larger upper limit...

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Looking for constructive criticism
    By wd_kendrick in forum C Programming
    Replies: 16
    Last Post: 05-28-2008, 09:42 AM
  2. Stone Age Rumble
    By KONI in forum Contests Board
    Replies: 30
    Last Post: 04-02-2007, 09:53 PM
  3. Find first 250 Prime Number
    By dummies in forum C Programming
    Replies: 4
    Last Post: 01-12-2007, 09:18 AM
  4. Prime number program problem
    By Guti14 in forum C Programming
    Replies: 11
    Last Post: 08-06-2004, 04:25 AM
  5. Can't find the lowest number in array?
    By Nate2430 in forum C++ Programming
    Replies: 1
    Last Post: 11-20-2001, 10:21 AM