C language practice (4) -- multiplication and division of large numbers

---

Preface

Use C Language to achieve multiplication of large numbers .

One 、 What is a large number operation ？

Large number operation , seeing the name of a thing one thinks of its function , Is to do a series of operations on large numbers . In mathematics , There is no upper limit on the value , But in the computer , Due to the limitation of word length , The range that a computer can represent is limited , For large numbers , The computer cannot calculate it directly , Need to use the so-called high-precision algorithm , namely Use arrays to store integers , And simulate the method of manual calculation for four operations .

Two 、 Realization thought —— Simulate manual calculation

Premise ： We cannot directly store very large operands as integers , Because the data type has the limitation of byte size . So we Use strings to store large numbers , Each element in a string is a single digit of a large number . The number of elements in a string can be unlimited , Therefore, it is very convenient to store large numbers .

1. Multiplication

Multiplication ： In hand calculation , We use the vertical method . That is, each bit of an operand （ From junior to senior ） Multiply all bits of another operand , And add up the results . So we can simulate the operation ：
First step ： Each element in the two strings Convert to integer and store in reverse order （ That is, the single digits are placed in the first element of the array ） In an array of integers （ Hypothetical array a,b）;
The second step ： Create a product group （sum）, The maximum length of the array is the above array a And b The product of length , Note that the array must be initialized to 0！！！
The third step ： use a Each element of the array is multiplied by b All elements of the array （ hypothesis a Array index from i=0 Start ,b Array index from j=0 Start ）, Store the results in sum【i+j】 in ;
Step four ： Contraproduct array （sum） To organize , From low to high , Dot into one

2. division

division ： In hand calculation , We also use vertical calculation , That is, take the first of the divisor n Digit number （n Is the number of digits of the divisor ） Divide by the divisor , If the number is greater than the divisor, divide , The remainder and the remaining digits of the dividend are combined , Repeat the above operation ; If the number is less than the divisor , Then expand this number , That is, take the first of the divisor n+1 Digit number , Repeat the above operation .
In short ： Use subtraction , But optimize , Before dividend n The number of subtractions between a digit number and a divisor , To multiply by 10 Of m-n Power , To correctly express quotient .(m Is the number of digits of the dividend )
First step ： Store the dividend and divisor in a string ;
The second step ： Judge the relationship between the divisor and the dividend . If the divisor is small , The direct exporter is 0, The remainder is the dividend ; If dividend Not less than Divisor , Then perform the following operations ;
The third step ： Create loop . If the dividend is not less than the divisor , Before the divisor n Digit number （n Is the number of digits of the divisor ） Create a bit string tem, And will tem Compare size with divisor . If tem Greater than the divisor , Then use tem Subtract each bit of the divisor from each bit of the , If the result is negative, you need to borrow , Loop execution , And record the number of subtractions ; If tem Less than the divisor , Then expand tem, Before the divisor n+1 Bit is created as a string tem, then tem Circularly subtract from the divisor ;
Step four ： Enlarged tem In circular subtraction , There are two sequential states .1.tem The number of digits is one more than the divisor ;2.tem There are as many digits as divisors Note that the code handling is different in both cases , Please observe carefully ！

3、 ... and 、 Code implementation

1. Multiplication function

The code is as follows ：

void Multiply(int n1[], int n2[], int sum[], int m, int n)
{
    
	int i = 0, j = 0;
	// take n1 Each bit of the is in turn associated with n2 Multiply all bits of 
	// The results are accumulated and stored in sum in 
	for (i = 0; i < m; i++)
	{
    
		// The maximum length of the product is m+n
		for (j = 0; j < n; j++)
		{
    
			sum[i + j] += n1[i] * n2[j];
		}
	}
	// Yes sum Every one of us has a meeting 10 Into the 1
	for (i = 0; i < m + n; i++)
	{
    
		if (sum[i] > 9)
		{
    
			sum[i + 1] += sum[i] / 10;
			sum[i] %= 10;
		}
	}
	// Record the last non-zero position 
	int flag = m + n;
	while (sum[flag] == 0)
	{
    
		flag--;
	}
	if (flag == 0)
	{
    
		printf("0");
	}
	else
	{
    
		// Output results 
		printf(" Product as ：");
		for (i = flag; i >= 0; i--)
		{
    
			printf("%d", sum[i]);
		}
	}
}

2. Division function

The code is as follows ：

void Divide(char s1[],char s2[])
{
    
	// Get the digits of two numbers 
	int m = strlen(s1);
	int n = strlen(s2);

	// Divisor less than divisor 
	if (m<n||(m==n&&strcmp(s1,s2)==-1))
	{
    
		printf(" merchant ：0  remainder ：%s",s1);
		return;
	}

	// The divisor is greater than the divisor 
	else
	{
    
		int m = strlen(s1);
		int n = strlen(s2);
		int sum[Max] = {
    0};
		int count = 0;
		char tem[Max] = {
     0 };
		// The dividend is not less than the divisor 
		while (((strcmp(s1, s2) != -1) && m == n)||m>n)
		{
    
			count = 0;
			int i = 0, j = 0;
			// From the first non-zero position of the dividend , Will be back n Bits are stored in tem in 
			for (i=0;i<n;i++)
			{
    
				tem[i] = s1[i];
			}

			// If the same number of digits tem Not less than s2 Just subtract 
			if (strcmp(tem, s2) != -1)
			{
    
				// use tem Go round and subtract the divisor s2
				while (strcmp(tem, s2) != -1)
				{
    
					for (i = n-1; i >=0; i--)
					{
    
						tem[i] = tem[i] - s2[i] + '0';
						if (tem[i] < '0')
						{
    
							tem[i] += 10;
							tem[i - 1] -= 1;
						}
						// Record how many times you have lost 
					}
					count++;
				}
				// take s1 Before n The bit assignment is tem
				for (i = 0; i < n; i++)
				{
    
					s1[i] = tem[i];
				}
				// Store the reduced times 
				sum[m - n] += count;
			}

			// Same digit tem Less than s2, Just expand tem
			else
			{
    
				//tem Digit ratio s2 More than a 
				tem[n] = s1[n];
				// use tem Go round and subtract the divisor s2
				int l1 = strlen(tem);
				while (((strcmp(tem, s2) != -1) && l1 == n) || l1 > n)
				{
    

					//tem Than s2 More than a 
					if (l1==n+1)
					{
    
						for (i = l1 - 1, j = n - 1; j >= 0; i--, j--)
						{
    
							tem[i] = tem[i] - s2[j] + '0';
							if (tem[i] < '0')
							{
    
								tem[i] += 10;
								tem[i - 1] -= 1;
							}
							// Record how many times you have lost 
						}
						count++;
						if (tem[0] == '0')
						{
    
							for (i = 1; i < n + 1; i++)
							{
    
								tem[i - 1] = tem[i];
							}
							tem[n] = '\0';
						}
					}

					//tem And s2 Same number of digits 
					else if(l1==n)
					{
    
						for (i = n - 1; i >= 0; i--)
						{
    
							tem[i] = tem[i] - s2[i] + '0';
							if (tem[i] < '0')
							{
    
								tem[i] += 10;
								tem[i - 1] -= 1;
							}
						}
						// Record how many times you have lost 
						count++;
					}
					l1 = strlen(tem);
				}
				// take s1 Before n+1 The bit assignment is tem
				s1[0] = '0';
				for (i = 1; i < n+1; i++)
				{
    
					s1[i] = tem[i-1];
				}
				// Store the reduced times 
				sum[m - n-1] += count;
			}

			// Arrangement s1, Remove the... Before the string 0
			// Find the first non-zero position 
			i = 0;
			while (s1[i] == '0')
			{
    
				i++;
			}
			// take s1 Move array forward i A unit of 
			for (j = i; j < m; j++)
			{
    
				s1[j - i] = s1[j];
			}
			// After the array i The first element is assigned to \0
			for (j = m - i; j < m; j++)
			{
    
				s1[j] = 0;
			}
			// Record the current s1 Number of digits 
			m = strlen(s1);
		}

		//sum It's business ,s1 It's the remainder 
		printf(" merchant ：");
		int flag = Max-1;
		int i = 0;
		while (sum[flag] == 0)
		{
    
			flag--;
		}
		for (i = flag; i >= 0; i--)
		{
    
			printf("%d", sum[i]);
		}
		printf("\n remainder ：");
		if (s1[0] != 0)
		{
    
			printf("%s", s1);
		}
		else
		{
    
			printf("0");
		}
	}
}

3. The main function

The code is as follows ：

int main()
{
    
	char s1[Max], s2[Max];
	// Note that when creating a product group , To initialize the array to 0
	int n1[Max], n2[Max], sum[Max * Max]={
    0};
	// Enter two large numbers as strings 
	printf(" Please enter two large numbers ：\n");
	while (1)
	{
    
		scanf("%s %s", s1, s2);
		if (s1[0] != '0' && s2[0] != '0')
			break;
		else
		{
    
			printf(" Large numbers are not allowed 0 start , Please re-enter two large numbers ：");
		}
	}
	// Get the length of two strings 
	int m = strlen(s1);
	int n = strlen(s2);
	// Convert each bit of the string into an integer and store it in reverse order 
	int i = 0, j = 0;
	for (i = 0; i < m; i++)
	{
    
		n1[i] = s1[m - i - 1] - '0';
	}
	for (j = 0; j < n; j++)
	{
    
		n2[j] = s2[n - j - 1] - '0';
	}
	printf(" Please select ：1. Multiplication  2. division \n");
	int input = 0;
	scanf("%d", &input);
	if (input == 1)
	{
    
		Multiply(n1, n2, sum, m, n);
	}
	else if (input == 2)
	{
    
		Divide(s1,s2);
	}
	return 0;
}

Four 、 The actual effect

summary

When implementing large number division , Hybrid implementation of large number subtraction , This makes the code very bloated .
The code can first implement the large number subtraction function , Then we can divide large numbers . This will simplify the division of large numbers , Beautify the look and feel .