// bigint.c
/*
* Enzo Ferber : <enzo@veloxmail.com.br>
*
* Big Ass Size Fatorial Numbers
* Using implemented 'unlimited' number size
*
* GCC 4.1.2
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define BASE 10
#define ASCII 48
// For larger number of digits, ajust here for bigger numbers...
// 120! has 199 digits.... that's quite a lot... but if you wanna calc anything bigger... be my guest... :)
//
// WARNING! Keep in mind that the functions go through the WHOLE ARRAY every step... and it's quite a lot of steps yet...
// The bigger the number of digits, the more time it will take to proccess.... Above 200 digits it starts to get pretty slow....
// Still working on performance improvments. And again, this is only the beggning of the ideia.... so, any thoughts, fell free to email.
#define NDIGITS 200
typedef int bigint [ NDIGITS ];
void initBigint ( bigint A )
{
register int i;
for ( i = 0; i < NDIGITS; i++ )
A[i] = 0;
}
void assignBigint ( bigint A, char *n, int len )
{
int i = 0;
initBigint ( A );
while ( (len - i)!= 0 )
{
// The '- ASCII' is required for the numbers in the ASCII table starts at 48, so (0 = 48, 1 = 49, etc... )
A[i] = n[ len - i - 1] - ASCII;
i++;
}
}
void printbigint (bigint A) {
int i, non_zero;
// This is to define where the number begins
non_zero = 0;
for (i=NDIGITS-1; i>=0; i--) {
if (A[i] || non_zero) {
non_zero = 1;
printf ("%d", A[i]);
}
}
if (!non_zero) printf ("0");
}
// C = A + B
void addBigint ( bigint A, bigint B, bigint C )
{
int carry = 0;
register int i;
assignBigint ( C, "0" , 1);
for ( i = 0; i < NDIGITS; i++ )
{
C[i] = A[i] + B[i] + carry;
carry = 0;
if ( C[i] >= BASE )
{
carry = C[i] / BASE;
C[i] %= BASE;
}
}
}
void copybigint ( bigint SRC, bigint DST )
{
register int i;
for ( i = 0; i < NDIGITS; i++ )
DST[i] = SRC[i];
}
/*
* MULTIPLICATION AREA
*/
void shiftleft( bigint A, int n )
{
register int i;
for( i = NDIGITS - 1; i >= n; i-- )
A[i] = A[i - n];
while( i >= 0 ) A[i--] = 0;
}
// B = A * n
void multonedigit( bigint A, bigint B, int n )
{
register int i;
int carry = 0;
initBigint( B );
for ( i = 0; i < NDIGITS; i++ )
{
B[i] = ( A[i] * n );
B[i] += carry;
carry = 0;
if( B[i] >= BASE )
{
carry = B[i] / BASE;
B[i] %= BASE;
}
}
if( carry != 0 ) printf( "Overflow" );
}
// C = A * B
void multbigint ( bigint A, bigint B, bigint C )
{
register int i;
bigint P, D;
initBigint( P );
initBigint( C );
initBigint( D );
for ( i = 0; i < NDIGITS; i++ )
{
multonedigit( B, P, A[i] );
shiftleft( P, i);
addBigint( D, P, C );
copybigint( C, D );
}
}
// LETS MAKE SOME BIG-ASS FATS!
void bigfat( char *num, bigint P )
{
register int i;
bigint A, B, C;
char *n = ( char * )malloc( strlen( num ) * sizeof( char ));
assignBigint( A, num, strlen( num ));
assignBigint( C, "0", 1 );
for( i = 1; i < atoi( num ); i++)
{
sprintf(n, "%d", i );
assignBigint( B, n, strlen( n ));
multbigint( A, B, C );
copybigint( C, A );
}
copybigint( A, P );
}
// just to know how many digits... ^^
int digcount( bigint A )
{
register int i;
int non_zero = 0;
int count = 0;
for( i = NDIGITS - 1; i > 0; i -- )
{
if( A[i] || non_zero )
{
non_zero = 1;
count++;
}
}
return( count + 1 );
}
int main( void )
{
bigint F;
register int i;
char s1[NDIGITS];
int limit = 120;
printf( "Digits limit: %d\n", NDIGITS );
//printf( "Fatorial list of: " ); fflush( stdin ); scanf( "%d", &limit );
for ( i = 1; i <= limit; i++ )
{
sprintf ( s1, "%d", i );
bigfat ( s1, F );
printf( "(%s)! (%3d): ", s1, digcount( F )); printbigint( F ); puts( "" );
}
return 0;
}