Computational hierarchy -- the problem of large numbers multiplying decimals

Preface

Ideas ：
1. The first thing to think about is how to store large integers in memory ？ When the basic data type cannot be saved , First thought of using arrays to save .
2. Then we need to think about which form to save large numbers ？Binary、Decimal、Hexadecimal？ Save a large number of Decimal The form is more in line with the habit , It is also convenient for the later multiplication of levels .
3. Then calculate the number of digits occupied by the decimal number of the result of the storage hierarchy , Used to dynamically request array memory . With the knowledge of encoder and decoder, it is easy to think of the result 10 The logarithm of the base can get the number of digits required by the decimal system .

Computational hierarchy ：
The normal idea of multiplying two numbers , Such as 720*7,7 And 720 Multiply each bit starting with a bit of ,7 The result of multiplying each bit plus the carry of the previous multiplication , Divide 10 The remainder is the value of the standard , Divide 10 Rounding is to give the next carry . The result of each multiplication is saved in the array . Because it starts from a single bit and multiplies , Therefore, the array memory stores the low and high order data results from the low address to the high address , This is a bit like little endian.

100!

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h> // malloc
#include <string.h> // memset
#include <math.h> // log10
#include <time.h> // clock


void Factorial(int nNumber);

int main()
{
    
	int nNum = 0;
	while (1)
	{
    
		printf("Please input the number:");
		scanf("%d", &nNum);
		Factorial(nNum);
	}
	return 0;
}

void Factorial(int nNumber)
{
    
	int i = 0;   //  Multipliers for calculating hierarchy 
	int j = 0;   //  Index of each bit of the calculation result 
	int nTemp = 0;        //  Temporary product result 
	int nCarry = 0;       //  Save carry 
	int nLen = 0;         //  Save the required number of digits  

	int nMaxIndex = 0;       //  Save the highest index 

	char* chAry = NULL;    //  Pointer to the final calculated result 

	clock_t ckStart, ckStop;

	double nBitCount = 0;

	ckStart = clock();   //  Start counting 
	// 1. The number of digits required for the calculation result 
	// nNumber The number of decimal digits occupied by the result of the hierarchy is saved in nLen in , Such as 5!=120, Occupy 3 position 
	for (i = 1; i <= nNumber; i++)
	{
    
		nBitCount = nBitCount + log10(i);
	}
	nLen = (int)ceil(nBitCount);

	// 2. To apply for space 
	//  Each digit stores 0-9, For everyone char Type data is enough to store 
	chAry = (char*)malloc(nLen + 1);
	memset(chAry, 0, nLen + 1);
	chAry[0] = 1;

	// 3.Algorithm
	//  After the multiplication, the last carry is accumulated , Then calculate the remainder and carry 
	for (i = 1; i <= nNumber; i++)      // i For from 1 The number of products to start 
	{
    
		nCarry = 0;
		for (j = 0; j <= nMaxIndex; j++)
		{
    
			nTemp = chAry[j] * i;
			nTemp += nCarry;            //  Add the last carry 
			chAry[j] = nTemp % 10;      //  Save the remainder  
			nCarry = nTemp / 10;        //  Save carry for next cycle 

			if ((nMaxIndex == j) && (nCarry !=0))   //  The highest bit product has carry 
			{
    
				nMaxIndex++;
			}
		}

	}

	ckStop = clock();

	

	// 4. Output results in reverse order 
	printf("Factorial(%d)=", nNumber);
	for ((nLen == 0) ? (i = 0) : (i = nLen - 1); i >= 0; i--)
	{
    
		printf("%d", chAry[i]);
	}
	printf("\r\n");

	printf("Takes %f ms\r\n", ((double)(ckStop - ckStart)));

	// 5. Release space 
	if (chAry != NULL)
	{
    
		free(chAry);
		chAry = NULL;
	}
}

seckill 10000!

Every time 4 Position in one int Type array , Do the multiplication as a whole .

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h> // malloc
#include <string.h> // memset
#include <math.h> // log10
#include <time.h> // clock


void Factorial(int nNumber);

int main()
{
    
	int nNum = 0;
	while (1)
	{
    
		printf("Please input the number:");
		scanf("%d", &nNum);
		Factorial(nNum);
	}
	return 0;
}

void Factorial(int nNumber)
{
    
	int i = 0;   //  Multipliers for calculating hierarchy 
	int j = 0;   //  Index of each bit of the calculation result 
	int nTemp = 0;        //  Temporary product result 
	int nCarry = 0;       //  Save carry 
	int nLen = 0;         //  Save the required number of digits  

	int nMaxIndex = 0;       //  Save the highest index 

	int* nAry = NULL;    //  Pointer to the final calculated result 

	clock_t ckStart, ckStop;

	double nBitCount = 0;

	ckStart = clock();   //  Start counting 
	// 1. The number of digits required for the calculation result 
	// nNumber The number of decimal digits occupied by the result of the hierarchy is saved in nLen in , Such as 5!=120, Occupy 3 position 
	for (i = 1; i <= nNumber; i++)
	{
    
		nBitCount = nBitCount + log10(i);
	}
	nLen = (int)ceil(nBitCount)/4;

	// 2. To apply for space 
	nAry = (int*)malloc((nLen + 1)*sizeof(int));
	memset(nAry, 0, (nLen + 1)*sizeof(int));
	nAry[0] = 1;

	// 3.Algorithm
	//  After the multiplication, the last carry is accumulated , Then calculate the remainder and carry 
	for (i = 1; i <= nNumber; i++)      // i For from 1 The number of products to start 
	{
    
		nCarry = 0;
		for (j = 0; j <= nMaxIndex; j++)
		{
    
			nTemp = nAry[j] * i;
			nTemp += nCarry;            //  Add the last carry 
			nAry[j] = nTemp % 10000;      //  Save the remainder  
			nCarry = nTemp / 10000;        //  Save carry for next cycle 

			if ((nMaxIndex == j) && (nCarry != 0))   //  The highest bit product has carry 
			{
    
				nMaxIndex++;
			}
		}

	}

	ckStop = clock();



	// 4. Output results in reverse order 
	printf("Factorial(%d)=", nNumber);
	printf("%d", (nLen == 0) ? 1 : nAry[nMaxIndex]);
	for (i = nMaxIndex - 1; i >= 0; i--)
	{
    
		printf("%04d", nAry[i]);
	}
	printf("\r\n");

	printf("Takes %f ms\r\n", ((double)(ckStop - ckStart)));

	// 5. Release space 
	if (nAry != NULL)
	{
    
		free(nAry);
		nAry = NULL;
	}
}

---