[ create a new paste ] login | about

Link: http://codepad.org/e0qmukBz    [ raw code | output | fork ]

EnzoFerber - C, pasted on Nov 22:
// 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;
}


Output:
Digits limit: 200
(1)! (  1): 1
(2)! (  1): 2
(3)! (  1): 6
(4)! (  2): 24
(5)! (  3): 120
(6)! (  3): 720
(7)! (  4): 5040
(8)! (  5): 40320
(9)! (  6): 362880
(10)! (  7): 3628800
(11)! (  8): 39916800
(12)! (  9): 479001600
(13)! ( 10): 6227020800
(14)! ( 11): 87178291200
(15)! ( 13): 1307674368000
(16)! ( 14): 20922789888000
(17)! ( 15): 355687428096000
(18)! ( 16): 6402373705728000
(19)! ( 18): 121645100408832000
(20)! ( 19): 2432902008176640000
(21)! ( 20): 51090942171709440000
(22)! ( 22): 1124000727777607680000
(23)! ( 23): 25852016738884976640000
(24)! ( 24): 620448401733239439360000
(25)! ( 26): 15511210043330985984000000
(26)! ( 27): 403291461126605635584000000
(27)! ( 29): 10888869450418352160768000000
(28)! ( 30): 304888344611713860501504000000
(29)! ( 31): 8841761993739701954543616000000
(30)! ( 33): 265252859812191058636308480000000
(31)! ( 34): 8222838654177922817725562880000000
(32)! ( 36): 263130836933693530167218012160000000
(33)! ( 37): 8683317618811886495518194401280000000
(34)! ( 39): 295232799039604140847618609643520000000
(35)! ( 41): 10333147966386144929666651337523200000000
(36)! ( 42): 371993326789901217467999448150835200000000
(37)! ( 44): 13763753091226345046315979581580902400000000
(38)! ( 45): 523022617466601111760007224100074291200000000
(39)! ( 47): 20397882081197443358640281739902897356800000000
(40)! ( 48): 815915283247897734345611269596115894272000000000
(41)! ( 50): 33452526613163807108170062053440751665152000000000
(42)! ( 52): 1405006117752879898543142606244511569936384000000000
(43)! ( 53): 60415263063373835637355132068513997507264512000000000
(44)! ( 55): 2658271574788448768043625811014615890319638528000000000
(45)! ( 57): 119622220865480194561963161495657715064383733760000000000
(46)! ( 58): 5502622159812088949850305428800254892961651752960000000000
(47)! ( 60): 258623241511168180642964355153611979969197632389120000000000
(48)! ( 62): 12413915592536072670862289047373375038521486354677760000000000
(49)! ( 63): 608281864034267560872252163321295376887552831379210240000000000
(50)! ( 65): 30414093201713378043612608166064768844377641568960512000000000000
(51)! ( 67): 1551118753287382280224243016469303211063259720016986112000000000000
(52)! ( 68): 80658175170943878571660636856403766975289505440883277824000000000000
(53)! ( 70): 4274883284060025564298013753389399649690343788366813724672000000000000
(54)! ( 72): 230843697339241380472092742683027581083278564571807941132288000000000000
(55)! ( 74): 12696403353658275925965100847566516959580321051449436762275840000000000000
(56)! ( 75): 710998587804863451854045647463724949736497978881168458687447040000000000000
(57)! ( 77): 40526919504877216755680601905432322134980384796226602145184481280000000000000
(58)! ( 79): 2350561331282878571829474910515074683828862318181142924420699914240000000000000
(59)! ( 81): 138683118545689835737939019720389406345902876772687432540821294940160000000000000
(60)! ( 82): 8320987112741390144276341183223364380754172606361245952449277696409600000000000000
(61)! ( 84): 507580213877224798800856812176625227226004528988036003099405939480985600000000000000
(62)! ( 86): 31469973260387937525653122354950764088012280797258232192163168247821107200000000000000
(63)! ( 88): 1982608315404440064116146708361898137544773690227268628106279599612729753600000000000000
(64)! ( 90): 126886932185884164103433389335161480802865516174545192198801894375214704230400000000000000
(65)! ( 91): 8247650592082470666723170306785496252186258551345437492922123134388955774976000000000000000
(66)! ( 93): 544344939077443064003729240247842752644293064388798874532860126869671081148416000000000000000
(67)! ( 95): 36471110918188685288249859096605464427167635314049524593701628500267962436943872000000000000000
(68)! ( 97): 2480035542436830599600990418569171581047399201355367672371710738018221445712183296000000000000000
(69)! ( 99): 171122452428141311372468338881272839092270544893520369393648040923257279754140647424000000000000000
(70)! (101): 11978571669969891796072783721689098736458938142546425857555362864628009582789845319680000000000000000
(71)! (102): 850478
Timeout


Create a new paste based on this one


Comments: