Thread: factorial problem

  1. #1
    Just because ygfperson's Avatar
    Join Date
    Jan 2002
    Posts
    2,490

    factorial problem

    I can't upload the program to show you what I mean, but the piece of code looks like this:
    Code:
    inline const int Factorial::operate(const int x) const {
      if (!x) return 1;
      return x * operate(x-1);
    }
    My program parses the expression so that the '!' would signal a factorial. That number is converted to a double, converted back to an integer, inserted into this function, and the output is converted back to a double, then printed out. (Ignore the lack of error-handling code... it will be there soon.)

    Positive, integral factorials act the way they should up to 12!. At 13! and upwards, it just fails. (The result is usually around e+09, and it sometimes decreases.) At 34! and upwards, it becomes 0. (Which isn't unusual, given my program's handling of infinity.)

    If I have the answer to 12! and multiply it by 13, the answer is correct. I'm assuming that there's a conversion error between a double and an int when the int gets big.

    Is that possible? Or am I approaching int_max?

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
    if (!x) return 1;
    What are you doing exactly here? Are you overloading the ! operator? If not, !x means "NOT X". Thus, this equates to "if (NOT X is anything other than zero) then return 1".

    So in effect, anything non-zero that you pass to the function will end up returning 1.

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

  3. #3
    Just because ygfperson's Avatar
    Join Date
    Jan 2002
    Posts
    2,490
    Originally posted by quzah
    Code:
    if (!x) return 1;
    What are you doing exactly here? Are you overloading the ! operator? If not, !x means "NOT X". Thus, this equates to "if (NOT X is anything other than zero) then return 1".

    So in effect, anything non-zero that you pass to the function will end up returning 1.

    Quzah.
    x is an int here. And your logic is flawed. The bitwise not operator is '~'. The '!' returns true if the argument is false, and false if the argument is true.

    > Or am I approaching int_max?
    Sailed straight past it
    11! is the max you can store in a signed 32 bit integer.
    No, it's 12!. 13! is around 6 billion, and 12! is 400 million.
    Guess this means I should change the return to a double... and probably the input too, so I don't have twelve or more int to double cast operations.

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Originally posted by ygfperson
    x is an int here. And your logic is flawed. The bitwise not operator is '~'. The '!' returns true if the argument is false, and false if the argument is true.
    Please know what you're talking about. If not, prove me wrong. I said nothing about bitwise. The ! is a logical not operator.

    Watch, and be amazed:
    Code:
    #include <iostream>
    using namespace std;
    
    int main( void )
    {
        int x = 5;
    
        cout << "x is " << x << endl;
        cout << "!x is " << (!x) << endl;
    
        x = 0;
        cout << "x is " << x << endl;
        cout << "!x is " << (!x) << endl;
    
    
        cout << "Thank you, move along." << endl;
    
        return 0;
    }
    Enjoy.

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

  5. #5
    Registered User
    Join Date
    May 2003
    Posts
    1,619
    His termination condition is correct:

    if (!x) return 1;

    returns 1 when x is zero. For nonzero x, (x) evaluates to true, so (!x) evaluates as false.

    There is no reason to keep things internally as integers, although you need to know that doubles cannot exactly represent all integer values.

    BTW, it makes no sense to return "const int" because you're returning by copy anyway.

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Originally posted by Cat
    His termination condition is correct:

    if (!x) return 1;

    returns 1 when x is zero. For nonzero x, (x) evaluates to true, so (!x) evaluates as false.
    :expletive: I can't believe I got that backwards. It's been a long day. That's my current excuse anyway...

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

  7. #7
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    hee hee.

    That's alright Quzah, as far as I can tell, that's the first mistake you've ever made. Now you know what it's like to be me.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  8. #8
    ¡Amo fútbol!
    Join Date
    Dec 2001
    Posts
    2,138
    A) I'd create a BigNum/BigFloat class to go along with this project. It'd make things very nice.

    B) That recursive method has a couple of flaws. If it is a big number, it might lead to a stack overflow. Also, what about if the user asks for the factorial of a negative number? In your case, you have an eventual stack crash caused by infinite recursion.

  9. #9
    Just because ygfperson's Avatar
    Join Date
    Jan 2002
    Posts
    2,490
    Originally posted by golfinguy4
    A) I'd create a BigNum/BigFloat class to go along with this project. It'd make things very nice.

    B) That recursive method has a couple of flaws. If it is a big number, it might lead to a stack overflow. Also, what about if the user asks for the factorial of a negative number? In your case, you have an eventual stack crash caused by infinite recursion.
    The calling function for the factorial restricts factorials to positive numbers (or 0). I've changed both types to a const double to take care of number problems. I don't think I'll be factorializing any number big enough to cause a stack problem. I guess it doesn't hurt to make precautions, though.

    re: the bignum/bigfloat idea, I hadn't really thought about it. It seems like a good idea once I get things settled.

    :expletive: I can't believe I got that backwards. It's been a long day. That's my current excuse anyway..
    lol... god knows how many times I've said that.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Memory problem with Borland C 3.1
    By AZ1699 in forum C Programming
    Replies: 16
    Last Post: 11-16-2007, 11:22 AM
  2. Someone having same problem with Code Block?
    By ofayto in forum C++ Programming
    Replies: 1
    Last Post: 07-12-2007, 08:38 AM
  3. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 02:51 PM
  4. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 06:54 PM
  5. Laptop Problem
    By Boomba in forum Tech Board
    Replies: 1
    Last Post: 03-07-2006, 06:24 PM