#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
typedef unsigned char uint8;
typedef unsigned short uint16;
#if UINT_MAX >= 0xFFFFFFFF
typedef unsigned uint32;
#else
typedef unsigned long uint32;
#endif
typedef unsigned uint;
void MulInPlace(uint8* dst/* n bytes */,
const uint8* src/* n bytes */,
uint n)
{
uint c1, c2;
if (n
>= 0xFFFF) abort();
for (c1 = n - 1; c1 != ~0u; c1--)
{
uint16 s = 0;
uint32 p = 0; // p must be able to store ceil(log2(n))+2*8 bits
for (c2 = c1; c2 != ~0u; c2--)
{
p += dst[c2] * src[c1 - c2];
}
dst[c1] = (uint8)(p & 0xFF);
for (c2 = c1 + 1; c2 < n; c2++)
{
p >>= 8;
s += dst[c2] + (uint8)(p & 0xFF);
dst[c2] = (uint8)(s & 0xFF);
s >>= 8;
}
}
}
int ByteDivInPlace(uint8* dst/* n bytes */,
uint n,
uint8 divisor,
uint8* remainder)
{
uint rem = 0;
int nonzero = 0;
while (n)
{
rem += dst[n - 1];
nonzero |= (dst[n - 1] = rem / divisor);
rem = (rem % divisor) << 8;
n--;
}
if (remainder != NULL)
*remainder = (uint8)(rem >> 8);
return nonzero; // 1 if the quotient is non-zero, 0 otherwise
}
void IncInPlace(uint8* dst/* n bytes */,
uint n)
{
uint c = 1;
while (n-- && c)
{
c += *dst;
*dst++ = c & 0xFF;
c >>= 8;
}
}
void DestroyingDecimalPrint(uint8* dst, uint n)
{
uint8 r;
if (ByteDivInPlace(dst, n, 10, &r))
DestroyingDecimalPrint(dst, n);
}
int main(void)
{
int i;
uint8 factorial[66];
uint8 factor[sizeof(factorial)];
uint8 tmp[sizeof(factorial)];
// factor = 1
memset(factor
, 0, sizeof(factor
)); factor[0] = 1;
// factorial = 1
memcpy(factorial
, factor
, sizeof(factorial
));
for (i = 1; i <= 100; i++)
{
// factorial *= factor
MulInPlace(factorial, factor, sizeof(factorial));
// tmp = factorial
memcpy(tmp
, factorial
, sizeof(factorial
));
// print i and tmp
DestroyingDecimalPrint(tmp, sizeof(tmp));
// factor += 1
IncInPlace(factor, sizeof(factor));
}
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdHJpbmcuaD4KI2luY2x1ZGUgPHN0ZGxpYi5oPgojaW5jbHVkZSA8bGltaXRzLmg+Cgp0eXBlZGVmIHVuc2lnbmVkIGNoYXIgdWludDg7CnR5cGVkZWYgdW5zaWduZWQgc2hvcnQgdWludDE2OwojaWYgVUlOVF9NQVggPj0gMHhGRkZGRkZGRgp0eXBlZGVmIHVuc2lnbmVkIHVpbnQzMjsKI2Vsc2UKdHlwZWRlZiB1bnNpZ25lZCBsb25nIHVpbnQzMjsKI2VuZGlmCnR5cGVkZWYgdW5zaWduZWQgdWludDsKCnZvaWQgTXVsSW5QbGFjZSh1aW50OCogZHN0LyogbiBieXRlcyAqLywKICAgICAgICAgICAgICAgIGNvbnN0IHVpbnQ4KiBzcmMvKiBuIGJ5dGVzICovLAogICAgICAgICAgICAgICAgdWludCBuKQp7CiAgdWludCBjMSwgYzI7CgogIGlmIChuID49IDB4RkZGRikgYWJvcnQoKTsKCiAgZm9yIChjMSA9IG4gLSAxOyBjMSAhPSB+MHU7IGMxLS0pCiAgewogICAgdWludDE2IHMgPSAwOwogICAgdWludDMyIHAgPSAwOyAvLyBwIG11c3QgYmUgYWJsZSB0byBzdG9yZSBjZWlsKGxvZzIobikpKzIqOCBiaXRzCgogICAgZm9yIChjMiA9IGMxOyBjMiAhPSB+MHU7IGMyLS0pCiAgICB7CiAgICAgIHAgKz0gZHN0W2MyXSAqIHNyY1tjMSAtIGMyXTsKICAgIH0KCiAgICBkc3RbYzFdID0gKHVpbnQ4KShwICYgMHhGRik7CgogICAgZm9yIChjMiA9IGMxICsgMTsgYzIgPCBuOyBjMisrKQogICAgewogICAgICBwID4+PSA4OwogICAgICBzICs9IGRzdFtjMl0gKyAodWludDgpKHAgJiAweEZGKTsKICAgICAgZHN0W2MyXSA9ICh1aW50OCkocyAmIDB4RkYpOwogICAgICBzID4+PSA4OwogICAgfQogIH0KfQoKaW50IEJ5dGVEaXZJblBsYWNlKHVpbnQ4KiBkc3QvKiBuIGJ5dGVzICovLAogICAgICAgICAgICAgICAgICAgdWludCAgIG4sCiAgICAgICAgICAgICAgICAgICB1aW50OCAgZGl2aXNvciwKICAgICAgICAgICAgICAgICAgIHVpbnQ4KiByZW1haW5kZXIpCnsKICB1aW50IHJlbSA9IDA7CiAgaW50IG5vbnplcm8gPSAwOwoKICB3aGlsZSAobikKICB7CiAgICByZW0gKz0gZHN0W24gLSAxXTsKICAgIG5vbnplcm8gfD0gKGRzdFtuIC0gMV0gPSByZW0gLyBkaXZpc29yKTsKICAgIHJlbSA9IChyZW0gJSBkaXZpc29yKSA8PCA4OwogICAgbi0tOwogIH0KCiAgaWYgKHJlbWFpbmRlciAhPSBOVUxMKQogICAgKnJlbWFpbmRlciA9ICh1aW50OCkocmVtID4+IDgpOwoKICByZXR1cm4gbm9uemVybzsgLy8gMSBpZiB0aGUgcXVvdGllbnQgaXMgbm9uLXplcm8sIDAgb3RoZXJ3aXNlCn0KCnZvaWQgSW5jSW5QbGFjZSh1aW50OCogZHN0LyogbiBieXRlcyAqLywKICAgICAgICAgICAgICAgIHVpbnQgbikKewogIHVpbnQgYyA9IDE7CiAgd2hpbGUgKG4tLSAmJiBjKQogIHsKICAgIGMgKz0gKmRzdDsKICAgICpkc3QrKyA9IGMgJiAweEZGOwogICAgYyA+Pj0gODsKICB9Cn0KCnZvaWQgRGVzdHJveWluZ0RlY2ltYWxQcmludCh1aW50OCogZHN0LCB1aW50IG4pCnsKICB1aW50OCByOwogIGlmIChCeXRlRGl2SW5QbGFjZShkc3QsIG4sIDEwLCAmcikpCiAgICBEZXN0cm95aW5nRGVjaW1hbFByaW50KGRzdCwgbik7CiAgcHJpbnRmKCIlZCIsIHIpOwp9CgppbnQgbWFpbih2b2lkKQp7CiAgaW50IGk7CiAgdWludDggZmFjdG9yaWFsWzY2XTsKICB1aW50OCBmYWN0b3Jbc2l6ZW9mKGZhY3RvcmlhbCldOwogIHVpbnQ4IHRtcFtzaXplb2YoZmFjdG9yaWFsKV07CgogIC8vIGZhY3RvciA9IDEKICBtZW1zZXQoZmFjdG9yLCAwLCBzaXplb2YoZmFjdG9yKSk7CiAgZmFjdG9yWzBdID0gMTsKCiAgLy8gZmFjdG9yaWFsID0gMQogIG1lbWNweShmYWN0b3JpYWwsIGZhY3Rvciwgc2l6ZW9mKGZhY3RvcmlhbCkpOwoKICBmb3IgKGkgPSAxOyBpIDw9IDEwMDsgaSsrKQogIHsKICAgIC8vIGZhY3RvcmlhbCAqPSBmYWN0b3IKICAgIE11bEluUGxhY2UoZmFjdG9yaWFsLCBmYWN0b3IsIHNpemVvZihmYWN0b3JpYWwpKTsKCiAgICAvLyB0bXAgPSBmYWN0b3JpYWwKICAgIG1lbWNweSh0bXAsIGZhY3RvcmlhbCwgc2l6ZW9mKGZhY3RvcmlhbCkpOwoKICAgIC8vIHByaW50IGkgYW5kIHRtcAogICAgcHJpbnRmKCIlaSEgPSAiLCBpKTsKICAgIERlc3Ryb3lpbmdEZWNpbWFsUHJpbnQodG1wLCBzaXplb2YodG1wKSk7CiAgICBwcmludGYoIlxuIik7CgogICAgLy8gZmFjdG9yICs9IDEKICAgIEluY0luUGxhY2UoZmFjdG9yLCBzaXplb2YoZmFjdG9yKSk7CiAgfQoKICByZXR1cm4gMDsKfQo=