factorial_bignum.c

#include <windows.h>

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

#define DIGITS 9
#define BASE 1000000000ULL
//#define DIGITS 18
//#define BASE 1000000000000000000ULL

//#define DIGITS 5
//#define BASE 100000ULL

//#define TYPE unsigned __int128
#define TYPE uint64_t

#define max(a,b) ((a)>(b)?(a):(b))

typedef struct bignum {
	int len;
   TYPE num[1];
}bignum;

int blocks;
int blocks2;
int blocks3;
int blocks4;

int tick;

bignum * addToStringumbers(bignum *a,bignum *b){
	if(a->len == 0) {
		return b;
	}
	{
		TYPE carry = 0;
		int len;
		bignum * result = malloc( sizeof( bignum ) + ((len=max(a->len,b->len)+1))*sizeof( TYPE ) );
		int i;
		blocks++;
		result->len = len;
		for( i=0; i < b->len; i++){
			TYPE op;
			if( i >= a->len )
				op = b->num[i]+carry;
			else
				op = a->num[i]+b->num[i]+carry;
			carry = (op / BASE);
			result->num[i] = ( op%BASE );
		}
		if(carry) result->num[i] = ( carry );
		else result->len--;

		return result;
	}
}

bignum *multiplyWithOneDigit(bignum *a,TYPE b,bignum *base){
	int len;
	bignum * result      = malloc( len = ( sizeof( bignum ) + (a->len + base->len)*sizeof(TYPE) ) );
	TYPE carry       = 0;
	int i;
	blocks2++;
	memcpy( result, base, len );
	for( i=0; i < a->len; i++) {
		TYPE op = a->num[i]* b+carry;
		carry = (op / BASE);
		result->num[result->len++] = (op%BASE);
	}
	if( carry )
		result->num[result->len++] = carry;
	return result;
}



bignum *multiplyStrings( bignum *a, bignum *b){
	bignum result0 = { 0 } ;
	bignum *result = &result0;
	bignum *result2;
	bignum *dummy = malloc( sizeof( bignum ) + (a->len+1)*sizeof( TYPE ) );
	blocks3++;
	int i;
	dummy->len = a->len+1;
	for( i=0; i <= a->len; i++) 
		dummy->num[i] = 0;

	for( i=0; i < b->len; i++) {
		bignum *dummy2;
		dummy->len = i;
		dummy2 = multiplyWithOneDigit(a,b->num[i], dummy);

		result2 = addToStringumbers(result, dummy2);
		if( result != &result0 ) { 
			blocks--;
			free( result );
		}
		if( result2 != dummy2 ) {
			blocks2--;
			free( dummy2 );
		}
		result = result2;
	}
	free( dummy );
	blocks3--;
	return result;
}



char *factorial( char *num ){
	bignum big1 = { 1, {1} };
	bignum *result = &big1;
	bignum thisNum = { 1, {0} };
	int i;
	int x = atoi( num );
	for( i=2; i<=x; i++){		
		bignum *result2;
		thisNum.num[0] = i;
		result2 = multiplyStrings(result, &thisNum);
		if( result != &big1 ) {
			blocks2--;
			free( result );
		}
		result = result2;
	
	}
	printf( "del:%d\n", timeGetTime() - tick );
	printf( "blocks: %d %d %d %d\n", blocks, blocks2, blocks3, blocks4 );
	{
		char *outbuf = malloc( (result->len+1) * DIGITS );
		int n;
		int ofs = 0;
		for( n = 0; n < result->len; n++ )
		{
			if( n )
				ofs += snprintf( outbuf+ofs, 256, "%0*lld", DIGITS, result->num[(result->len-1)-n] );
			else
				ofs += snprintf( outbuf+ofs, 256, "%*lld", DIGITS, result->num[(result->len-1)-n] );
		}
		return outbuf;
	}
}



bignum *makeBigNum( char *num ) {
	int len = strlen( num );
	int digits = (len+(DIGITS-1))/DIGITS;
	bignum *out = malloc( sizeof( bignum ) + (digits-1 )*sizeof( TYPE ) );
	int n;
	out->len = digits;
	for( n = 0; n < digits; n++ ) {
		if( (n*DIGITS) <= len ) {
			out->num[n] =
				  (num[(len-1) - (n*DIGITS) - 7] - '0') * 100000000ULL
				+ (num[(len-1) - (n*DIGITS) - 6] - '0') * 10000000ULL
				+ (num[(len-1) - (n*DIGITS) - 6] - '0') * 1000000ULL
				+ (num[(len-1) - (n*DIGITS) - 5] - '0') * 100000ULL
				+ (num[(len-1) - (n*DIGITS) - 4] - '0') * 10000ULL
            + (num[(len-1) - (n*DIGITS) - 3] - '0') * 1000ULL
            + (num[(len-1) - (n*DIGITS) - 2] - '0') * 100ULL
            + (num[(len-1) - (n*DIGITS) - 1] - '0') * 10ULL
            + (num[(len-1) - (n*DIGITS) - 0] - '0') * 1ULL;
		} else {
			out->num[n] = 0;
			switch( len - ( n*DIGITS) ) {
			case 9:
            out->num[n] += (num[(len-1) - (n*DIGITS) - 8] - '0') * 100000000ULL;
			case 8:
            out->num[n] += (num[(len-1) - (n*DIGITS) - 7] - '0') * 10000000ULL;
			case 7:
            out->num[n] += (num[(len-1) - (n*DIGITS) - 6] - '0') * 1000000ULL;
			case 6:
            out->num[n] += (num[(len-1) - (n*DIGITS) - 5] - '0') * 100000ULL;
			case 5:
            out->num[n] += (num[(len-1) - (n*DIGITS) - 4] - '0') * 10000ULL;
			case 4:
            out->num[n] += (num[(len-1) - (n*DIGITS) - 3] - '0') * 1000ULL;
			case 3:
            out->num[n] += (num[(len-1) - (n*DIGITS) - 2] - '0') * 100ULL;
			case 2:
            out->num[n] += (num[(len-1) - (n*DIGITS) - 1] - '0') * 10ULL;
			case 1:
            out->num[n] += (num[(len-1) - (n*DIGITS) - 0] - '0') * 1ULL;
			}
		}
	}
   return out;
}


int main( int argc, char **argv ) {
	tick = timeGetTime();
	printf( "%s\n", factorial( argv[1] ) );
	printf( "del:%d\n", timeGetTime() - tick );
   //bignum *n = makeBigNum( argv[1] );
}




/*

"use asm";

(function(){

    function multiplyStrings(a,b){
        var result = [];
	var dummy = [];


        for(var i=0; i < b.length; i++) {
   	    if( i ) dummy.push(0);
            var dummy2 = multiplyWithOneDigit(a,b[i], dummy.slice());
            result = addToStringumbers(result,dummy2);
        }
        return result;
    }

    function multiplyWithOneDigit(a,b,base){
        var result      = base;
        var carry       = 0;
        for(var i=0; i < a.length; i++) {
	   var op = a[i]*b+carry;
           carry = (op >> 16);
	   result.push(op&0xFFFF);
        }
	if( carry ) result.push(carry);
        return result;
    }


    function addToStringumbers(a,b){
        if(a.length == 0)
            return b;

        var carry = 0;
        var result = [];

        for(var i=0; i < b.length; i++){
	   if( i >= a.length )
 	      var op = b[i]+carry;
	   else
 	      var op = a[i]+b[i]+carry;
   	   carry = (op>>16);
           result.push( op&0xFFFF );
        }
        if(carry) result.push( carry );

        return result;
    }

    function intToArray(i) {
	if( i < 65536 )
		return [parseInt(i)];
	else
		return [parseInt(i) & 0xFFFF, parseInt(i) >> 16];
       return tmp2;
    }

    function factorial(x){
        var result = [1];
        for(var i=2; i<=x; i++){
            result = multiplyStrings(result, intToArray(i));
        }

        var tmp = result.reverse();
	var tmp2 = tmp.map( (n,i)=>{
            var s = n.toString(16);
            if( i ) for( var n = s.length; n < 4; n++ ) s = "0" + s;
            return s } );
	return tmp2.join("");

    }

var now = Date.now();
    console.log(factorial(process.argv[2]));
console.log( "del:", Date.now() - now );

}());
*/