SLD
Contributor
Any idea what this number could be? Too hard to calculate normally. I’d be curious to know if we can even estimate the order of magnitude of the number. Probably an upper bound.
-
Features
One million factorial
- Thread starter SLD
- Start date
barbos
Contributor
SLD
Contributor
So basically on the order of 1,000,008
barbos
Contributor
0.5*log10((2*M_PI*1e6))+1.e6*(log10(1.e6/exp(1))) = 5565708.91718668
on the order of 5,565,709
on the order of 5,565,709
Swammerdami
Squadron Leader
barbos
Contributor
https://www.calculatorsoup.com/calculators/discretemathematics/factorials.php
1000000! = 8.263931688 E+5565708
1000000! = 8.263931688 E+5565708
steve_bank
Diabetic retinopathy and poor eyesight. Typos ...
skepticalbip
Contributor
- Joined
- Apr 21, 2004
- Messages
- 7,304
- Basic Beliefs
- Everything we know is wrong (to some degree)
Not much at all for a system that uses scientific notation.
steve_bank
Diabetic retinopathy and poor eyesight. Typos ...
That might give you order of magnitude. Many digits if you want an exact number.
barbos
Contributor
Code:
/*
Prints factorial of very big number
Courtesy of barbos
*/
#include <stdio.h>
#include <math.h>
using llong=long long;
void factorial(llong x)
{
double lf=0;
for(llong i=2;i <=x; i++)lf+=log10((double)i);
double pwr=0;
double mant=exp10(modf(lf,&pwr));
printf("%lld! = %ge+%.0f\n", x, mant, pwr);
}
int main(int np, char **par)
{
llong x;
if(np == 2)
{
sscanf(par[1],"%lld",&x);
factorial(x);
}
return 0;
}1,000,000,000! = 9.90143e+8565705522
Swammerdami
Squadron Leader
105565709
You could save some space by stripping off the final 249998 digits — all zero — and appending the note " followed by 249998 zeroes." Of course, if such shortcuts are acceptable you could just store the eight bytes "1000000!" and be done with it.
5565709 digits, about the same as a very short video clip.
You could save some space by stripping off the final 249998 digits — all zero — and appending the note " followed by 249998 zeroes." Of course, if such shortcuts are acceptable you could just store the eight bytes "1000000!" and be done with it.
barbos
Contributor
Slightly better precision and range for very large numbers:
Code:
/*
Prints factorial of very big number
Courtesy of barbos
*/
#include <stdio.h>
#include <math.h>
using llong=long long;
void factorial(llong x)
{
double lf=0;
for(llong i=2;i <=x; i++)lf+=log10((double)i);
double pwr=0;
double mant=exp10(modf(lf,&pwr));
printf("%lld! = %ge+%.0f\n", x, mant, pwr);
}
void factorial_2(llong x)
{
double lf1=0;
llong lf2=0;
for(llong i=2;i <=x; i++)
{
double pwr=0;
lf1+=log10((double)i);
lf1=modf(lf1,&pwr);
lf2+=(llong)pwr;
}
printf("%lld! = %ge+%lld\n", x, exp10(lf1), lf2);
}
int main(int np, char **par)
{
llong x;
if(np == 2)
{
sscanf(par[1],"%lld",&x);
factorial_2(x);
}
return 0;
}Swammerdami
Squadron Leader
As long as we're posting code to calculate OP's number, we may as well calculate it exactly.
Code:
#include <stdlib.h>
#include <stdio.h>
#define BASE 10
struct bnum {
long leng;
char val[7000000];
} Res;
void mpy(struct bnum *res, long mpyr)
{
long i, j;
for (j = i = 0; i < res->leng; i++, j /= BASE)
res->val[i] = (j += res->val[i] * mpyr) % BASE;
for (; j; j /= BASE)
res->val[res->leng++] = j % BASE;
}
int main(int argc, char **argv)
{
long i, mpyr = argv[1] ? atol(argv[1]) : 1000000;
Res.leng = 1;
Res.val[0] = 1;
for (i = 2; i <= mpyr; i++)
mpy(&Res, i);
for (i = Res.leng; i--; )
printf("%c",
Res.val[i]["0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"]);
printf("\n");
}OP's number begins 8,263,931,688,331,240,062,376,646,103,172,666,291,135,347,978,963,873,045,167,775,885... As previously mentioned, the number ends with 249998 zeros. Altogether it has 782336 0's, 532223 1's, 532921 2's, 531100 3's, 532174 4's, 531421 5's, 531351 6's, 530558 7's, 530361 8's, and 531264 9's.
SLD
Contributor
As long as we're posting code to calculate OP's number, we may as well calculate it exactly.
My rusty old laptop will print 50000! in a few seconds running this code; 100000! takes about a minute. It wasted over an hour to compute 1000000!, but it had nothing better to do anyway.Code:#include <stdlib.h> #include <stdio.h> #define BASE 10 struct bnum { long leng; char val[7000000]; } Res; void mpy(struct bnum *res, long mpyr) { long i, j; for (j = i = 0; i < res->leng; i++, j /= BASE) res->val[i] = (j += res->val[i] * mpyr) % BASE; for (; j; j /= BASE) res->val[res->leng++] = j % BASE; } int main(int argc, char **argv) { long i, mpyr = argv[1] ? atol(argv[1]) : 1000000; Res.leng = 1; Res.val[0] = 1; for (i = 2; i <= mpyr; i++) mpy(&Res, i); for (i = Res.leng; i--; ) printf("%c", Res.val[i]["0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"]); printf("\n"); }
OP's number begins 8,263,931,688,331,240,062,376,646,103,172,666,291,135,347,978,963,873,045,167,775,885... As previously mentioned, the number ends with 249998 zeros. Altogether it has 782336 0's, 532223 1's, 532921 2's, 531100 3's, 532174 4's, 531421 5's, 531351 6's, 530558 7's, 530361 8's, and 531264 9's.
Outstanding! I never expected quite so accurate a response.
I wonder what the computational limit is? 1,000,000,000? Or 1,000,000,000,000?
barbos
Contributor
barbos
Contributor
Swammerdami
I have a 10x faster than yours:
I have a 10x faster than yours:
Code:
#include <vector>
using ullong=unsigned long long;
class Fact
{
std::vector<unsigned int> data;
void mult(ullong m)
{
unsigned int carr=0;
size_t len=data.size();
for(size_t i=0; i < len;i++)
{
ullong r12=m*data[i] + carr;
data[i]=r12%1000000000;
carr=(unsigned int)(r12/1000000000);
}
if(carr)data.push_back(carr);
}
public:
void print()
{
auto s1=data.begin();
auto s2=data.end();
s2--;
printf("%d",*s2);
while(s2 != s1)
{
s2--;
printf("%.9d",*s2);
}
printf("\n");
}
void factorial(ullong f)
{
data.clear();
data.push_back(1);
for(ullong z=2; z<=f;z++)mult(z);
print();
}
};
void factorial_exact(llong x)
{
Fact f;
printf("Exact: %lld! = ", x);
f.factorial(x);
}
int main(int np, char **par)
{
llong x;
if(np == 2)
{
sscanf(par[1],"%lld",&x);
// factorial(x);
// factorial_2(x);
// factorial_stirl(x);
factorial_exact(x);
}
return 0;
}steve_bank
Diabetic retinopathy and poor eyesight. Typos ...
It makes me tingly all over when I see C code.
Swammerdami
Squadron Leader
If you don't have a compiler handy to scratch that itch, and cold shower doesn't help, you might want to stare at some Cobol code. That should kill your high.
Code I write for a message board may emphasize compactness and, perhaps, whimsy. Code I write for a paying client would be (slightly?) more readable. The following line, with Res.val NOT declared as a 2-D array, wasn't even deliberate whimsy. I was only semi-conscious when I wrote it.
printf("%c", Res.val["0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"]);
I wonder what TFT C programmers think of that "...[...][...]" expression.
- Never seen that before, but it's obvious what it does. Neato!
- Never seen that before, but it's obvious what it does. Barf!
- Never seen that before and don't understand it.
- Yeah, I indulged in that trick occasionally when I was a teenager, but I'm an adult now and have put aside childish things.
ETA: I know some C programmers who despise printf("%c", ... since putchar(... does the same thing and saves some nanoseconds. I, OTOH, despise that anal-retentive "efficiency" because I often search for the strong printf as part of reading or debugging a program.
barbos
Contributor
I knew about 1[ptr] crap. I would never use it.