I was recently asked, in an interview, to describe a method to calculate the factorial of any arbitrarily large number; a method in which we obtain all the digits of the answer.
I searched various places and asked in a few forums. But I would like to know if there is any way to accomplish this without using libraries like GMP.
Thank you.
GNU Multiprecision library is a good one! But since you say using of external libraries are not allowed, only way I believe its possible is by taking an array of int and then multiplying numbers as you do with pen on paper!
Here is the code I wrote some time back..
#include<iostream>
#include<cstring>
int max = 5000;
void display(int arr[]){
int ctr = 0;
for (int i=0; i<max; i++){
if (!ctr && arr[i]) ctr = 1;
if(ctr)
std::cout<<arr[i];
}
}
void factorial(int arr[], int n){
if (!n) return;
int carry = 0;
for (int i=max-1; i>=0; --i){
arr[i] = (arr[i] * n) + carry;
carry = arr[i]/10;
arr[i] %= 10;
}
factorial(arr,n-1);
}
int main(){
int *arr = new int[max];
std::memset(arr,0,max*sizeof(int));
arr[max-1] = 1;
int num;
std::cout<<"Enter the number: ";
std::cin>>num;
std::cout<<"factorial of "<<num<<"is :\n";
factorial(arr,num);
display(arr);
delete[] arr;
return 0;
}
'arr' is just an integer array, and factorial is a simple function that multiplies the given number to the 'large number'.
Hope this solves your query..
The accepted answer is fine, but this is C++; we can do better. Let's make the start of our own Bignum class, with a totally unbounded number of digits.
For the highest efficiency we would work with pure binary numbers, packing each array element with as many bits as we can efficiently handle. The simpler approach is to store a single decimal digit in each element. Here I've gone for a compromise, storing 9 decimal digits in each uint32_t element.
The data is stored little-endian, since it's much easier to extend a vector at the end when we need higher order elements.
Once we have this class, the factorial function is simplicity itself.
#include <assert.h>
#include <iomanip>
#include <iostream>
#include <stdint.h>
#include <vector>
class Bignum
{
public:
Bignum(int value)
{
assert(value >= 0 && value <= 999999999);
parts.push_back(value);
}
Bignum& operator*=(int rhs)
{
assert(rhs >= 0 && rhs <= 999999999);
uint32_t carry = 0;
for (size_t i = 0; i < parts.size(); i++)
{
uint64_t product = (uint64_t)parts[i] * (uint64_t)rhs + carry;
parts[i] = (uint32_t)(product % 1000000000LL);
carry = (uint32_t)(product / 1000000000LL);
}
if (carry != 0)
parts.push_back(carry);
return *this;
}
friend std::ostream & operator<<(std::ostream& stream, const Bignum& num);
private:
std::vector<uint32_t> parts;
};
inline std::ostream& operator<<(std::ostream& stream, const Bignum& num)
{
char oldfill = stream.fill('0');
for (std::vector<uint32_t>::const_reverse_iterator it = num.parts.rbegin(); it != num.parts.rend(); it++)
stream << *it << std::setw(9);
stream.fill(oldfill);
stream.width(0);
return stream;
}
Bignum factorial(int n)
{
Bignum fac = 1;
for (int i = 2; i <= n; i++)
fac *= i;
return fac;
}
int main(int argc, char* argv[])
{
for (int n = 0; n <= 52; n++)
std::cout << factorial(n) << std::endl;
return 0;
}
Nice solution by Srivatsan Iyer and my suggestion are :
It can still be made more memory efficient by using unsigned char array rather than using int array to store digits. It will take only 25% of the memory need to that of int array.
For the best memory optimization , we can also use single byte to represent a 2 digits. Since only 4 bits are suffice to represent any digit from 0 to 9. So we can pack two digits in a single byte using bitwise operations. It will take 12.5% of the memory need to that of int array.
Well, you'd have to write your own math routines using arrays. That's very easy for addition, multiplication is a bit harder, but still possible.
EDIT: Wanted to post an example, but Srivatsan Iyer's example is just fine.
A BigInteger class would solve your problem, and the C implementation above gives you an idea about how a BigInt would be implemented, except that the code is optimized for speed and tailored to computing the factorial only.
I have a solution for calculating the factorial, which works fine for at least n<=15000. Factorial of 10000 can be calculated under 1 sec and that for calculating the factorial takes less than 2 seconds. (Of course your question tells nothing about time constraints and these timings are totally dependent on the machine). Anyways, the concept is quite simple. I use a char array. The first character of the array is '1'. The LSBs are stored from the index starting with 0. A variable(m according to my program) keeps track of the factorial length. The final value of m is the number of digits in the factorial and the (m-1)th element of the char array is MSB of the factorial. As the loop iterates, the characters get added in the right side of the array. A variable 'c' keeps track of the carry.
The drawbacks of using the array is left over chunks of unused bytes. And beyond a certain point, you cannot reserve space for an array.Besides, arrays tend to get slow.
You can check out my program on ideone: http://ideone.com/K410n7
I believe my solution can still be optimized. Please suggest how.
include<stdio.h>
char res[200000];
inline int fact(int n)
{
int i,j;
register int m,c;
m=1;
res[0]='1';
for(i=2;i<=n;i++)
{
c=0;
for(j=0; j< m; j++){
c =((res[j]-48)*i)+c;
res[j]=(c%10)+48;
c=c/10;
}
while(c>0){
res[m]=(c%10)+48;
c=c/10;
m++;
}
}
return m;
}
int main() {
int n,i,d;
scanf("%d",&n);
d=fact(n);
for(i=d-1;i>=0;i--)
printf("%c",res[i]);
return 0;
}
#include <iostream>
using namespace std;
int main ()
{
int i,n,p=1;
cout<<"Enter a number: ";
cin>>n;
cout<<endl;
for (i=1;i<=n; i++)
{
cout<<i<<" X ";
p=p*i;
}
cout<<endl<<endl<<p<<" factorial of "<<n;
return 0;
}
That's actually pretty easy. Here are two ways. One is exact and one is an approximation. For exact figures, any number over 10,000 is going to take multiple seconds to calculate. Approximating it will take microseconds, until you get into the millions. It is Stirling's approximation if anyone is interested.
Factorial of 10,000,000 is aprox 1.2024234127436e+65657059 This took 5.9 seconds Finding the exact amount would take 34 days.
<?php
$test= 3579;
echo 'Factorial of '.$test.'<br><br>';
$tm= microtime( true);
echo 'Exact '.( $f= factorialexact( $test)).' e+'.(strlen( $f)-1).' missing decimal place after first digit<br>';
echo ( microtime( true) - $tm). ' seconds<br><br>';
$tm= microtime( true);
echo 'Aprox '.factorialapprox( $test).'<br>';
echo ( microtime( true) - $tm). ' seconds<br><br>';
function factorialexact( $n){
$f= '1';
for ( $i=$n; $i>1; $i--){
$f= JL_bcmul( $f, (''.$i));
}
return $f;
}
function factorialapprox( $n){
// Stirling's factorial approximation
// aprox factorial n = sqrt( 2 * pi * n) * n^n / e^n
// store in t the easy part, calc the first term easily
$t= sqrt( 2 * 3.14159265358979 * $n);
// things get tough from here because for large n
// n^n can blow away floating point pachages
// declare exponent of the number
$e= 0;
// the remaining terms are n^n / e^n
// both n and e (natural log) are raised to the same power
// that is n, just negative of each other
for ( $i=0; $i<$n; $i++){
// loop to
// mulitply by n and divide by e for each iteration
$t= $t * $n / 2.71828182845904;
// exponents are going to get away from us
// so reduce or increase t
while ( $t>1000){
$t= $t/1000;
$e= $e+3;
}
while ( $t<0.001){
$t= $t*1000;
$e= $e-3;
}
}
// garentee the base number is between 1 and 10
while ( $t>=10){
$t= $t/10;
$e= $e+1;
}
while ( $t<1){
$t= $t*10;
$e= $e-1;
}
// return at a floating string.
// do not use parseFloat() or floatval()
// $v= explode( 'e', $result); $floatvalue= $v[0] * pow( 10, $v[1]);
// won't work either. $v[1] is way too large
// the exponent can easily be in the tens of thousands
$p= '-';
if ( $e>=0){ $p= '+'; }
return $t.'e'.$p.$e;
}
function JL_bcmul( $a, $b){
if ( function_exists( 'bcmul')){
return bcmul( ( ''.$a), (''.$b));
}
$s= array();
for ($i=0; $i < count( $a) + count( $b); $i++){ $s[$i]= '0'; }
$t= 0;
for ($i=0; $i < strlen( $b); $i++){
for ($j=0; $j < strlen( $a); $j++){
$t= $s[$i+$j] + intval( $a[strlen( $a) - $j - 1]) * intval( $b[ strlen( $b) - $i - 1]);
$s[$i+$j]= $t % 10;
$s[$i+$j+1]= $s[$i+$j+1] + floor( $t / 10);
}
}
$s= array_reverse( $s);
return trim( trim(( implode( '', $s).'_'), '0'), '_');
}
#include<stdio.h>
#include<string.h>
char f[10000];
char factorial[1010][10000];
void multiply(int k){
int ci,sum,i;
int len = strlen(f);
ci=0;
i=0;
while(i<len){
sum=ci+(f[i] - '0') * k;
f[i] = (sum % 10) + '0';
i++;
ci = sum/10;
}
while(ci>0){
f[i++] = (ci%10) + '0';
ci/=10;
}
f[i]='\0';
for(int j=0;j<i;j++)factorial[k][j]=f[j];
factorial[k][i]='\0';
}
void fac(){
int k;
strcpy(f,"1");
for(k=2;k<=1000;k++)multiply(k);
}
void print(int n){
int i;
int len = strlen(factorial[n]);
printf("%d!\n",n);
for(i=len-1;i>=0;i--){
printf("%c",factorial[n][i]);
}
printf("\n");
}
int main()
{
int n;
factorial[0][0]='1';
factorial[1][0]='1';
fac();
while(scanf("%d",&n)==1){
print(n);
}
return 0;
}
Code shown below :
#include<bits/stdc++.h>
using namespace std;
#define MAX 5000
void factorial(int n)
{
int carry , res_size = 1, res[MAX];
res[0] = 1;
for(int x=2; x<=n; x++)
{
carry = 0;
for(int i=0; i<res_size; i++)
{
int prod = res[i]*x + carry;
res[i] = prod % 10;
carry = prod/10;
}
while (carry)
{
res[res_size++] = carry%10;
carry = carry/10;
}
}
for(int i=res_size-1; i >= 0; i--)
{
cout<<res[i];
}
}
int main()
{
int n;
cin>>n;
factorial(n);
cout<<endl;
return 0;
}
Since everyone voted for Srivatsan, I just have a doubt related to the problem. Do you need to store all the digits? If yes, then Srivatsan's solution is fine. If not, why not just display the numbers, as you calculate the factorial? I am not formatting the output properly, but this could serve the purpose.
int factorial(int num)
{
if (num <= 0)
return 1;
else
{
std::cout << num << std::endl;
return num * factorial(num - 1);
}
}
UPDATE
For all the downvoters, though this 5 year old post, and the output for factorial(3);
3
2
1
6 // this is the result of the factorial and the digits above are the ones all the digits in the calculation.
I thought this is what asked.
