#include #include "string.h" #include "ctype.h" #include "stdlib.h" /* N-bonacci sequence calculation for a large number without recursion. In the sandbox, only up to 10,000 - 15,000 numbers can be calculated, but so much more. */ void SumTwoCharNums(char* cNums1, char* cNums2) { int iLen1 = strlen(cNums1); int iLen2 = strlen(cNums2); int iMaxLen = (iLen1 > iLen2)?iLen1:iLen2; int iDig = 0; int iDig1Chr = 0; int iDig2Chr = 0; int iExtraVal = 0; while(iDig < iMaxLen){ if(iDig >= iLen1){ memmove(cNums1+1, cNums1, iLen1); cNums1[0] = '0'; iLen1++; cNums1[iLen1] = 0; }; iDig1Chr = iLen1 - iDig - 1; iDig2Chr = iLen2 - iDig - 1; if(iDig >= iLen2){ cNums1[iDig1Chr] += iExtraVal; } else { cNums1[iDig1Chr] += (cNums2[iDig2Chr] - '0') + iExtraVal; }; iExtraVal = 0; if(cNums1[iDig1Chr] > '9'){ iExtraVal = 1; cNums1[iDig1Chr] -= 10; }; iDig++; }; if(iExtraVal){ memmove(cNums1+1, cNums1, iLen1); cNums1[0] = '1'; iLen1++; } cNums1[iLen1] = 0; } typedef struct{ char** caNumPmX; int iaNumPmSizeX; char* cNumP; int iNumsSize; } cCharNumsThrdNFib_t; #define FIBNUMSIZE_GROW_STEP 100 char* fCalcBigNbonachi( int iSrchFibId, int iNp, int iFree ) { static cCharNumsThrdNFib_t vFibNums; static int init = 0; if( (iNp < 1) && !iFree )return NULL; char **ait = NULL; if( init && !iFree ){ if(vFibNums.iaNumPmSizeX != iNp){ ait = vFibNums.caNumPmX; for( int in = 0; in < vFibNums.iaNumPmSizeX; in++ ){ free(*ait); *ait = NULL; ait++; }; free( vFibNums.caNumPmX ); vFibNums.iaNumPmSizeX = iNp; vFibNums.caNumPmX = (char**)calloc( sizeof( char* ), vFibNums.iaNumPmSizeX ); ait = vFibNums.caNumPmX; for( int in = 0; in < iNp; in++ ){ *ait = (char*)calloc( sizeof( char ), vFibNums.iNumsSize ); ait++; }; }; }; if( !init ){ memset( &vFibNums, 0, sizeof(vFibNums) ); vFibNums.iNumsSize = FIBNUMSIZE_GROW_STEP; vFibNums.iaNumPmSizeX = iNp; vFibNums.caNumPmX = (char**)calloc( sizeof( char* ), vFibNums.iaNumPmSizeX ); ait = vFibNums.caNumPmX; for( int in = 0; in < iNp; in++ ){ *ait = (char*)calloc( sizeof( char ), vFibNums.iNumsSize ); ait++; }; vFibNums.cNumP = (char*)calloc( sizeof( char ), vFibNums.iNumsSize ); init = 1; }; if( iFree ){ ait = vFibNums.caNumPmX; for( int in = 0; in < vFibNums.iaNumPmSizeX; in++ ){ free(*ait); *ait = NULL; ait++; }; free( vFibNums.caNumPmX ); free( vFibNums.cNumP ); memset( &vFibNums, 0, sizeof(vFibNums) ); init = 0; return NULL; }; ait = vFibNums.caNumPmX; for( int in = 0; in < iNp; in++ ){ memset( *ait, 0, vFibNums.iNumsSize ); **ait = '1'; ait++; }; memset( vFibNums.cNumP, 0, vFibNums.iNumsSize ); *(vFibNums.cNumP) = '0'; if( iSrchFibId < iNp + 1 ){ if( iSrchFibId < 1 )return NULL; return *(vFibNums.caNumPmX); }; int i = iNp, iLen, imLen, iNewSize; int err = 0; char *cRlc = NULL; while( i < iSrchFibId ){ imLen = 0; ait = vFibNums.caNumPmX; for( int in = 0; in < iNp; in++ ){ iLen = strlen( *ait ); if( iLen > imLen )imLen = iLen; ait++; }; if( imLen + iNp*2 + 1 > vFibNums.iNumsSize ){ iNewSize = vFibNums.iNumsSize + FIBNUMSIZE_GROW_STEP; while( imLen + iNp*2 + 1 > iNewSize ) iNewSize += FIBNUMSIZE_GROW_STEP; ait = vFibNums.caNumPmX; for( int in = 0; in < iNp; in++ ){ cRlc = (char*)realloc( *ait, iNewSize ); if(cRlc == NULL){ printf( " acNumPmX[%i] realloc" " to %i chars - false.\n", in, iNewSize ); err = 1; break; }else{ *ait = cRlc; }; ait++; }; if( err )break; cRlc = (char*)realloc( vFibNums.cNumP, iNewSize ); if(cRlc == NULL){ printf( " FibNums realloc" " to %i chars - false.\n", iNewSize ); err = 1; break; }else{ vFibNums.cNumP = cRlc; }; vFibNums.iNumsSize = iNewSize; }; memcpy( vFibNums.cNumP, *( vFibNums.caNumPmX ), vFibNums.iNumsSize ); ait = vFibNums.caNumPmX + 1; for( int in = 1; in < iNp; in++ ){ SumTwoCharNums( vFibNums.cNumP, *ait ); memcpy( *(ait - 1), *ait, vFibNums.iNumsSize ); ait++; }; ait = vFibNums.caNumPmX + (iNp - 1); memcpy( *ait, vFibNums.cNumP, vFibNums.iNumsSize ); i++; }; if( err )return NULL; return vFibNums.cNumP; } int main() { char *cNum; printf(" Nbonachi[Np = %i] id[%i] = %s\n", 1, 2000, (cNum = fCalcBigNbonachi( 4000, 1, 0 )) ?cNum:"NULL" ); printf(" Nbonachi[Np = %i] id[%i] = %s\n", 2, 2000, (cNum = fCalcBigNbonachi( 2000, 2, 0 )) ?cNum:"NULL" ); printf(" Nbonachi[Np = %i] id[%i] = %s\n", 3, 2000, (cNum = fCalcBigNbonachi( 2000, 3, 0 )) ?cNum:"NULL" ); printf(" Nbonachi[Np = %i] id[%i] = %s\n", 5, 2000, (cNum = fCalcBigNbonachi( 2000, 5, 0 )) ?cNum:"NULL" ); printf(" Nbonachi[Np = %i] id[%i] = %s\n", 7, 2000, (cNum = fCalcBigNbonachi( 2000, 7, 0 )) ?cNum:"NULL" ); printf(" Nbonachi[Np = %i] id[%i] = %s\n", 11, 2000, (cNum = fCalcBigNbonachi( 2000, 11, 0 )) ?cNum:"NULL" ); //free alloc pointers from static member fCalcBigNbonachi( 0, 0, 1 ); return 0; }

N-Bonacci - calculation of very large numbers (string ver)