Factorial number

[luciusFernatore]

Write your question here.

/*HEllo everybody. i would like to see your recommendations and your quotes.

how can i optimize this code?
what is wrong into the code?
what can it be improved?

\Write a program that reads a nonnegative integer and
computes and prints its factorial*/

//factorial of an integer number
//Luis Fernando
//23/08/2018

#include <iostream>

using std::cout;
using std::cin;
using std::endl;

int main(int argc, char** argv)
{
	
	int number;
	int factorial = 1;
	int storeCount = 1;
	int storeMultiplication = 1;
	
	cout << "Join a positive integer: ";
	cin >> number;
	
	if(number > 0){
		
			while(storeCount <= number)
		{
			storeMultiplication = storeCount * 1;
			factorial *= storeCount;
			
			storeCount++;
		}
		
		cout << "the factorial of " << number << "!" << " is " << factorial; 
		
	}
	else
	{
		cout << "Please introduce a positive integer. ";
	}
	return 0;
}

[JLBorges]

#include <iostream>

int main()
{
    std::cout << "enter a positive number: " ;
    unsigned int number ;

    if( std::cin >> number ) // if the user entered a number
    {
        unsigned long long factorial = 1 ;
        for( unsigned int n = 2 ; n <= number ; ++n )
        {
            // note: unsigned arithmetic does not overflow; a result that cannot be represented
            // is reduced modulo the number that is one greater than the largest value that can be represented.
            const unsigned long long next_value = factorial * n ;

            if( next_value > factorial ) factorial = next_value ;
            else // result was reduced modulo
            {
                std::cout << "the result is too large\n" ;
                return 1 ; // exit failure
            }
        }

        std::cout << number << "! == " << factorial << '\n' ;
        return 0 ; // exit success
    }

    else std::cout << "error: non-numeric input\n" ;
    return 1 ; // exit failure
}

[tpb]

Sadly, even with 64 bits you can only go up to 20!

20!                                       2,432,902,008,176,640,000
2^64                                     18,446,744,073,709,551,616
21!                                      51,090,942,171,709,440,000
30!                     265,252,859,812,191,058,636,308,480,000,000
34!             295,232,799,039,604,140,847,618,609,643,520,000,000
2^128           340,282,366,920,938,463,463,374,607,431,768,211,456
35!          10,333,147,966,386,144,929,666,651,337,523,200,000,000
40! 815,915,283,247,897,734,345,611,269,596,115,894,272,000,000,000

Here's code that uses gcc's built-in 128-bit type and prints the result with commas.

#include <iostream>
#include <iomanip>
#include <cstdlib>

void print_r(__uint128_t x) {
    if (x < 1000)
        std::cout << int(x);
    else {
        print_r(x / 1000);
        std::cout << ',' << std::setw(3) << int(x % 1000);
    }
}

void print(__uint128_t x) {
    std::cout << std::setfill('0');
    print_r(x);
    std::cout << std::setfill(' ');
    std::cout << '\n';
}

int main(int argc, char **argv) {
    if (argc != 2) {
        std::cerr << "Usage: factywack N\n";
        return 0;
    }
    int n = std::atoi(argv[1]);
    if (n > 34) {
        std::cerr << "Can only calculate up to 34!\n";
        return 0;
    }

    __uint128_t f = 1;
    for (int i = 2; i <= n; i++)
        f *= i;

    print(f);
}

[lastchance]

fernatore wrote:

what is wrong into the code?

Well, strictly speaking, you ask for a positive integer and then procede to try to calculate a factorial only if it is negative - see the logic following line 31
if(number < 0){
Try running the code.


I'm also not sure what this line is trying to achieve:
storeMultiplication = storeCount * 1;


It would be nice to make factorial( n ) a separate function, I think.


If you want some really big factorials ...

#include <iostream>
#include <vector>
using namespace std;

//------------------

ostream &operator << ( ostream &strm, const vector<int> &V )
{
   for ( int j = V.size() - 1; j >= 0; j-- ) strm << V[j] << ( j % 3 || !j ? "" : "," );
   return strm;
}

//------------------

vector<int> factorial( unsigned n )
{
   if ( n <= 1 ) return vector<int>{ 1 };

   vector<int> result;                   
   vector<int> last = factorial( n - 1 );
   int size = last.size();
                        
   int i = 0, carry = 0;
   while ( i < size || carry > 0 )
   {
      if ( i < size ) carry += n * last[i];
      result.push_back( carry % 10 );
      carry /= 10;
      i++;
   }
   return result;
}

//------------------

int main()
{
   for ( int n = 10; n <= 100; n += 10 ) cout << n << "! = " << factorial( n ) << '\n';
}

10! = 3,628,800
20! = 2,432,902,008,176,640,000
30! = 265,252,859,812,191,058,636,308,480,000,000
40! = 815,915,283,247,897,734,345,611,269,596,115,894,272,000,000,000
50! = 30,414,093,201,713,378,043,612,608,166,064,768,844,377,641,568,960,512,000,000,000,000
... lots of very long lines ...

[jonnin]

IMHO factorials should be stored in a lookup table such that
result = fact[input];

this is how to optimize factorials for normal use cases.

dealing with very large values aside (you have to pick your solution here), there is a *very* accurate factorial approximation function that you can use that directly computes the values without loops/recursion/ etc that may be good enough depending on what you are doing.

you can shave off the powers of 2 or powers of 10 (note that after a bit all factorials have extra trailing zeros that you can optimize out with various techniques) and squeeze a few more out of standard integers if you care to do that (eg store it in a pair of values like base, 10^x exponent). Or store log of the values, but this is the alien problem (an alien takes all the data in the universe, does a 1/x of it as an integer form, records that tiny number on his magic ruler, and leaves). But of course you have to have billions of digits of precision on the inverted number, its just as big as the original in terms of digits... so log approach won't store any more than any other approach really, you are up against the precision of your biggest accessible double type (12 bytes now? I forget?).

[JLBorges]

Brute force computation of factorials just involves repeated multiplications; it does not take too much time.

#include <iostream>
#include <boost/multiprecision/cpp_int.hpp>
#include <ctime>
#include <sstream>

int main()
{
    volatile int v = 0 ;

    for( unsigned int number : { 1'000, 5'000, 10'000, 30'000 } )
    {
        const auto start = std::clock() ;

        boost::multiprecision::cpp_int factorial = 1 ;
        for( unsigned int n = 2 ; n <= number ; ++n ) factorial *= n ;
        v += msb(factorial) ;

        const auto end = std::clock() ;

        std::ostringstream stm ;
        stm << factorial ;
        std::cout << "computing " << number << "! (" << stm.str().size() << " digits) took "
                  << (end-start)*1000.0/CLOCKS_PER_SEC << " millisecs.\n" ;
    }
}

echo && echo && g++ -std=c++17 -O3 -Wall -Wextra -pedantic-errors main.cpp && ./a.out

computing 1000! (2568 digits) took 0.324 millisecs.
computing 5000! (16326 digits) took 7.701 millisecs.
computing 10000! (35660 digits) took 13.041 millisecs.
computing 30000! (121288 digits) took 136.585 millisecs.

http://coliru.stacked-crooked.com/a/7189c1abf8b1857f

[luciusFernatore]

hey guys
Thank you for your time and your compression, i-m really starting onto programming knowledge.

to be honest i don't understand some of your notes right now. even that thank you for your time and generous help.