High-precision subtraction (implemented in C language)
Introduction
As we all know, integers are stored in three different sizes of data in C and C++: int, long, and long long. The maximum data size can be Up to 2^64, but in actual use, we will inevitably encounter extremely large number operations that explode long long. At this time, we need to use high precision Algorithms to implement operations on huge numbers.
The essence of high precision is to read numbers in the form of strings, and then store each bit into the int array, and simulate the operation process of each bit to achieve the final operation effect.
Continuing from the previous chapter, we continue to explain the C language implementation of high-precision subtraction today:
Code implementation
#include<stdio.h>
const int N = 100001;
int cmp(int a[], int b[], int len1, int len2)
{//Size comparison function
if (len1 > len2)//Compare the length first
return 0;
else if (len1 < len2)//return the result directly if the length is different
return 1;
else//If the length is the same, compare the size of each bit in turn
{
for (int i = len1 - 1; i >= 0; i--)
{
if (a[i] > b[i])
return 0;
if (a[i] < b[i])
return 1;
}
}
return 0;//If it is completely consistent, return 0 to avoid infinite recursion caused by calls in the subtraction function
}
int minus(int a[], int b[], int c[], int len1, int len2)
{//High-precision subtraction function
if (cmp(a, b, len1, len2))//The subtraction function only calculates large decreases, and the opposite is true for small decreases, and then adds a negative sign when outputting
return minus(b, a, c, len2, len1);
int t = 0; //t identifies whether it is borrowed
for (int i = 0; i < len1; i + + )
{
c[i] = (a[i] - b[i] + t + 10) % 10;//c[i] represents the result of this one-bit operation
if (a[i] - b[i] + t < 0) t = -1;//calculate whether to borrow
else t = 0;
}
int len3 = len1;
while (c[len3 - 1] == 0)//Remove leading 0s and return the number of digits in the result
{
if (len3 == 1) return len3;
len3--;
}
return len3;
}
int main()
{
char str1[N], str2[N];//-----------------------------
int a[N] = { 0 }, b[N] = { 0 }, c[N] = { 0 };
char x;
int len1 = 0, len2 = 0;
do
{
scanf("%c", & amp;x);
str1[len1 + + ] = x;
} while (x != '\\
');
do// The data reading part will not be described in detail.
{
scanf("%c", & amp;x);
str2[len2 + + ] = x;
} while (x != '\\
');
len1--; len2--;
for (int i = len1 - 1; i >= 0; i--)
a[i] = str1[len1 - i - 1] - '0';
for (int i = len2 - 1; i >= 0; i--)
b[i] = str2[len2 - i - 1] - '0';//---------------
int len3 = minus(a, b, c, len1, len2);//Execute high-precision subtraction function
if (cmp(a, b, len1, len2))//size comparison function
printf("-");//If the result is a negative number, put a negative sign first
for (int i = len3 - 1; i >= 0; i--)
printf("%d", c[i]);
return 0;
}
Analysis of ideas
Since we have already explained the reading of data in the article on high-precision addition, we will not go into details in this article. If you have not read the previous article, you can click on the link below:
High-precision addition (implemented in C language) – herbal tea coltea
The idea of high-precision subtraction is basically the same as that of high-precision addition. The difference is that addition considers carry, subtraction considers carry, and the number of digits in the subtraction result changes greatly.
We calculate each bit separately, get the result, and store it in a new array c. At the same time, we use a temporary variable t to identify whether to borrow a bit.
However, the result of subtracting a large number from a decimal is a negative number, which is very inconvenient in actual operation, so we declare an additional cmp function to compare the sizes of the two. If the minuend is relatively small, then we can use the subtraction method To subtract the minuend from a number, output a negative sign before outputting the result to achieve the same effect.
In terms of data reading, high-precision addition, subtraction, multiplication and division are basically the same, so we jump directly to the first key part, the size comparison function:
int cmp(int a[], int b[], int len1, int len2)
{//Size comparison function
if (len1 > len2)//Compare the length first
return 0;
else if (len1 < len2)//return the result directly if the length is different
return 1;
else//If the length is the same, compare the size of each bit in turn
{
for (int i = len1 - 1; i >= 0; i--)
{
if (a[i] > b[i])
return 0;
if (a[i] < b[i])
return 1;
}
}
return 0;//If it is completely consistent, return 0 to avoid infinite recursion caused by calls in the subtraction function
}
In the data reading, we already know the digits of the two numbers, so we can determine the size of the two who is bigger by comparing the digits.
If the lengths of the two are the same, then compare the size of each bit in turn, that is, compare the lexicographic order of the two.
If the two are completely consistent, then we return 0, the reason will be explained later.
With the size comparison function, we can ensure that the decimal is subtracted from the large number during calculation. In this way, we avoid the trouble of negative numbers and can more easily implement high-precision subtraction functions:
int minus(int a[], int b[], int c[], int len1, int len2)
{//High-precision subtraction function
if (cmp(a, b, len1, len2))//The subtraction function only calculates large decreases, and the opposite is true for small decreases, and then adds a negative sign when outputting
return minus(b, a, c, len2, len1);
int t = 0; //t identifies whether it is borrowed
for (int i = 0; i < len1; i + + )
{
c[i] = (a[i] - b[i] + t + 10) % 10;//c[i] represents the result of this one-bit operation
if (a[i] - b[i] + t < 0) t = -1;//calculate whether to borrow
else t = 0;
}
int len3 = len1;
while (c[len3 - 1] == 0)//Remove leading 0s and return the number of digits in the result
{
if (len3 == 1) return len3;
len3--;
}
return len3;
}
As you can see, the first step is to judge the size of the two. If the minuend is smaller than the minuend, we directly change the order of the input parameters to change the positions of the two.
If cmp returns 1 when the two are completely consistent, then the minus function will continue to call cmp after changing the positions. function to determine the size of the two, it will return 1 every time, resulting in infinite recursion. This is why we specify that 0 is returned when they are completely consistent.
Among them, we use c[i] = (a[i] - b[i] + t + 10) % 10; to calculate the ith digit of the result. The reason why To + 10, it is the process of borrowing 10 from the previous digit when the simulation result is negative, and if (a[i] - b[i] + t ) is not a negative number, then there will be no impact because of the existence of .
The next line if (a[i] - b[i] + t < 0) is also easy to understand, if (a[i] - b[i] + t) is a negative number, then we need to borrow a bit from the previous bit, then we mark t=-1 to affect the calculation of the next bit.
Finally, we need to remove the leading 0. First, because the operands are all positive integers, the maximum number of digits in the result is the same as the minuend, so we judge the result starting from the highest number of digits in the minuendc, if it is 0, then subtract 1 from the returned length len3, and it is worth noting that, If the result only has 1 bits, it cannot be subtracted, because this means that the result is 0.
At this time, we have completed the high-precision subtraction operation and stored the result in the array c, but don’t forget to judge whether the result is positive or negative:
if (cmp(a, b, len1, len2))//size comparison function
printf("-");//If the result is a negative number, put a negative sign first
If the minuend is smaller than the subtrahend, we need to add the negative sign in advance.
That's it, you're done.
End
So the above is an introduction to the high-precision subtraction algorithm. This article is written by herbal tea coltea. The ideas come from AcWing, the course of the big guy yxc.