Implementation of C and C++ High precision algorithm
- 2020-06-23 01:31:38
- OfStack
When doing ACM, we often encounter the calculation of large Numbers, such as addition, subtraction, multiplication and division, power and factorial. At this time, the given data type is often not enough to represent the final result, so a high-precision algorithm is needed. The essence of high-precision algorithm is to break large Numbers into blocks of fixed length, and then perform corresponding operations on each block. Here, consider 4-digit Numbers as 1 block, and the input large Numbers are all positive integers (other bits can also be considered, but it should be noted that the corresponding operation in each block should not exceed the numeric range of the data type; If there is a negative integer read in judgment 1 under the sign in the decision operation).
1. Add with high accuracy
Take 3479957928375817 + 897259321544245 as an example:
| 3479 | 9579 | 2837 | 5817 |
|---|---|---|---|
| +897 | +2593 | +2154 | +4245 |
| = | = | = | = |
| 4376 | 12172 | 4991 | 10062 |
| 进位0 | 进位1 | 进位0 | 进位1 |
| 4377 | 2172 | 4992 | 0062 |
The C language implementation code is as follows:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 200
// Integer powers function
int Pow(int a, int b)
{
int i = 0, result = 1;
for(i = 0; i < b; ++i)
{
result *= a;
}
return result;
}
//High Precision Of Addition
int main()
{
char stra[N], strb[N]; // An array of strings that stores two large Numbers as characters;
int i = 0, step = 4, carry = 0; //step Is the block length, carry Is carry bit;
int lengtha, lengthb, maxlength, resultsize; //maxlength said stra and strb2 The longer one;
int numa[N], numb[N],numc[N]; // Store the addend, addend, and in turn;
memset(numa, 0, sizeof(numa));
memset(numb, 0, sizeof(numb));
memset(numc, 0, sizeof(numc)); // Initialize to zero;
scanf("%s%s", stra, strb);
lengtha = strlen(stra);
lengthb = strlen(strb); // Calculate the length of two large Numbers
// Character and digit conversion 4 position 1 An integer number of blocks
for(i = lengtha-1; i >= 0; --i)
{
numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);
}
for(i = lengthb-1; i >= 0; --i)
{
numb[(lengthb-1-i)/step] += (strb[i]-'0')*Pow(10,(lengthb-1-i)%step);
}
maxlength = lengtha > lengthb ? lengtha : lengthb;
// Add them block by block and carry them
for(i = 0; i <= maxlength/step; ++i)
{
numc[i] = (numa[i] + numb[i])%Pow(10, step) + carry; // The calculation and
carry = (numa[i] + numb[i])/Pow(10, step); // Calculation of carry
}
// Calculate the total number of blocks in the final sum
resultsize = numc[maxlength/step] > 0 ? maxlength/step : maxlength/step - 1;
printf("%d", numc[resultsize]);
for(i = resultsize-1; i >= 0; --i)
{
printf("%04d", numc[i]); // Right alignment, zero complement output;
}
printf("\n");
return 0;
}
2. High-precision subtraction
Similar to addition, the difference is to pay attention to the sign and the number of display changes. Take 99999037289799-100004642015000 as an example:
Let's first decide which of the minuend and the subtractive is greater. Obviously, the subtractive is greater here, so the output is negative. After subtracting a decimal from a large number, (if a block subtracts to a negative number, borrow from the higher block) is shown in the following table
| 100 | 0046 | 4201 | 5000 |
|---|---|---|---|
| -99 | -9990 | -3728 | -9799 |
| 1 | 56 | 473 | 5201 |
| 借位0 | 借位1 | 借位0 | 借位1 |
| 0 | 56 | 472 | 5201 |
The C language implementation code is as follows:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 200
// Integer powers function
int Pow(int a, int b)
{
int i = 0, result = 1;
for(i = 0; i < b; ++i)
{
result *= a;
}
return result;
}
//High Precision Of Subtraction
int main()
{
char stra[N], strb[N]; // An array of strings that stores two large Numbers as characters;
int i = 0, step = 4, borrow = 0, mark = 0; //step Is the block length, borrow To borrow a , mark Is the symbol bit of the result;
int lengtha, lengthb, maxlength, resultsize; //maxlength said stra and strb2 The longer one;
int numa[N], numb[N],numc[N], *maxnum, *minnum; // Store minuend, subtractive, and;
memset(stra, 0, sizeof(stra));
memset(strb, 0, sizeof(strb));
memset(numa, 0, sizeof(numa));
memset(numb, 0, sizeof(numb));
memset(numc, 0, sizeof(numc)); // Initialize to zero;
scanf("%s%s", stra, strb);
lengtha = strlen(stra);
lengthb = strlen(strb); // Calculate the length of two large Numbers
maxlength = lengtha >= lengthb ? lengtha : lengthb;
// Character and digit conversion 4 position 1 An integer number of blocks
for(i = lengtha-1; i >= 0; --i)
{
numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);
}
for(i = lengthb-1; i >= 0; --i)
{
numb[(lengthb-1-i)/step] += (strb[i]-'0')*Pow(10,(lengthb-1-i)%step);
}
// Find the larger number
maxnum = numa;
minnum = numb;
mark = 1;
for(i = (maxlength-1)/step; i >= 0; --i)
{
if(numa[i] > numb[i])
{
maxnum = numa;
minnum = numb;
mark = 1;
break;
}
else if(numa[i] < numb[i])
{
maxnum = numb;
minnum = numa;
mark = -1;
break;
}
}
// I'm going to subtract and borrow
for(i = 0; i <= maxlength/step; ++i)
{
numc[i] = (maxnum[i] - minnum[i] + Pow(10, step) + borrow)%Pow(10,step); // Calculate poor
borrow = (maxnum[i] - minnum[i] + Pow(10, step) + borrow)/Pow(10, step) - 1; // Calculate a borrow
}
// Calculate the total number of blocks in the final sum
resultsize = maxlength/step;
while(!numc[resultsize]) --resultsize;
printf("%d", mark*numc[resultsize]);
for(i = resultsize-1; i >= 0; --i)
{
printf("%04d", numc[i]); // Right alignment, zero complement output;
}
printf("\n");
return 0;
}
3. High-precision multiplication
Multiplication can be regarded as multiplying the multiplier by the multiplicand then adding it. Take 4296556241 x 56241 as an example:
| 被乘数 | 42 | 9655 | 6241 |
|---|
| 乘数 | 5 | 6 | 2 | 4 | 1 |
|---|
| 被乘数x乘数 | 42 | 9655 | 6241 |
|---|---|---|---|
| 1 | 42 | 9655 | 6241 |
| 4 | 168*10 | 38620*10 | 24964*10 |
| 2 | 84*100 | 19310*100 | 12482*100 |
| 6 | 252*1000 | 57930*1000 | 37446*1000 |
| 5 | 210*10000 | 48275*10000 | 31205*10000 |
| 累加和 | 2362122 | 543006855 | 351000081 |
| 进位（从低位向高位） | 241 | 54304 | 35100 |
| 积 | 241 | 6426 | 1955 | 0081 |
|---|
The C language implementation code is as follows:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 200
// Integer powers function
int Pow(int a, int b)
{
int i = 0, result = 1;
for(i = 0; i < b; ++i)
{
result *= a;
}
return result;
}
//High Precision Of Multiplication
int main()
{
char stra[N], strb[N]; // An array of strings that stores two large Numbers as characters;
int i = 0, j = 0, k = 0, step = 4, carry = 0; //step Is the block length, carry Is carry bit;
int lengtha, lengthb, resultsize, tmpsize, eachnum; //resultsize The total number of storage blocks, eachnum To store each of the multipliers 1 position
int numa[N], numb[N], numc[N], tmp[N]; // Store the multiplicand in turn & Product, multiplier;
memset(numa, 0, sizeof(numa));
memset(numb, 0, sizeof(numb));
memset(numc, 0, sizeof(numc)); // Initialize to zero;
scanf("%s%s", stra, strb);
lengtha = strlen(stra);
lengthb = strlen(strb); // Calculate the length of two large Numbers
// Converts the multiplicand character number to 4 position 1 An integer number of blocks
for(i = lengtha-1; i >= 0; --i)
{
numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);
}
// Converts a multiplier digit to a character digit 1 position 1 An integer number of blocks
for(i = lengthb-1; i >= 0; --i)
{
numb[lengthb-1-i] = strb[i]-'0';
}
resultsize = tmpsize = (lengtha-1)/step;
// Take each of the multipliers 1 Bits are multiplied block by block and carried;
for(i = 0; i < lengthb; ++i)
{
memcpy(tmp, numa, sizeof(numa)); // will numa Array assignment to tmp The array;
k = i/step; //k Each store 1 The number of times the block needs to move to the higher block;
if(k)
{
for(j = tmpsize; j >= 0; --j)
{
tmp[j+k] = tmp[j];
tmp[j] = 0;
}
tmpsize += k;
}
// Times the multiplier per 1 A bit extension into a block;
eachnum = numb[i]*Pow(10, i%step);
for(j = 0; j <= tmpsize; ++j)
{
tmp[j] *= eachnum;
}
// Addition of large Numbers
carry = 0; // Zero entry position;
for(j = 0; j <= resultsize; ++j)
{
numc[j] += tmp[j] + carry;
carry = numc[j]/Pow(10,step);
numc[j] %= Pow(10, step);
}
if(carry)
{
++resultsize;
numc[j] += carry;
}
}
// The output
printf("%d", numc[resultsize]);
for(i = resultsize-1; i >= 0; --i)
{
printf("%04d", numc[i]); // Right alignment, zero complement output;
}
printf("\n");
return 0;
}
4. High-precision division
There are two kinds of high-precision division, one is high-precision divided by low-precision, and the other is high-precision divided by high-precision. The former can be done by dividing each block by the low precision divisor. The latter is realized by high-precision subtraction, that is, subtracting the high-precision divisor every time until it is less than the divisor, then the number of subtractions is quotient and the remainder is remainder.
High precision divided by low precision
Take 9876342876/343 as an example:
| 被除数 | 98 | 7634 | 2876 |
|---|
| 除数 | 343 |
|---|
| 向低位块进位 | 98 | 137 | 190 |
|---|---|---|---|
| 商 | 0 | 2879 | 4002 |
| 余数 | 190 |
|---|
The C language code is as follows:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 200
// Integer powers function
int Pow(int a, int b)
{
int i = 0, result = 1;
for(i = 0; i < b; ++i)
{
result *= a;
}
return result;
}
//High Precision Of division
//(1) High precision divided by low precision
int main()
{
char stra[N]; // An array of strings that store high-precision dividends as characters;
int i = 0, step = 4, carry = 0; //step Is the block length, carry Is high to low carry position;
int lengtha, resultsize;
int numa[N], numb, numc[N], numd; // Store the dividend, divisor, and quotient in turn , Remainder;
memset(numa, 0, sizeof(numa));
memset(numc, 0, sizeof(numc)); // Initialize to zero;
scanf("%s%d", stra, &numb);
lengtha = strlen(stra); // Calculate the length of the dividend
// Character and digit conversion 4 position 1 An integer number of blocks
for(i = lengtha-1; i >= 0; --i)
{
numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);
}
carry = 0; // Carry position zero from high to low
resultsize = (lengtha-1)/step;
// Block by block, high to low carry
for(i = resultsize; i >= 0; --i)
{
numc[i] = (numa[i] + carry*Pow(10,step))/numb; // Computing,
carry = (numa[i] + carry*Pow(10,step))%numb; // Calculation of carry
}
numd = carry; // The remainder of the lowest block is the remainder of the whole division
// Calculate the total number of blocks in the final sum
while(!numc[resultsize]) --resultsize;
// The output,
printf("%d", numc[resultsize]);
for(i = resultsize-1; i >= 0; --i)
{
printf("%04d", numc[i]); // Right alignment, zero complement output;
}
// Output the remainder
printf("\n%d\n", numd);
return 0;
}
High precision divided by high precision
Take 176342876/3453452 as an example:
| 100 | 0046 | 4201 | 5000 |
|---|---|---|---|
| -99 | -9990 | -3728 | -9799 |
| 1 | 56 | 473 | 5201 |
| 借位0 | 借位1 | 借位0 | 借位1 |
| 0 | 56 | 472 | 5201 |
The C language code is as follows:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 200
// Integer powers function
int Pow(int a, int b)
{
int i = 0, result = 1;
for(i = 0; i < b; ++i)
{
result *= a;
}
return result;
}
//High Precision Of division
//(2) High precision divided by high precision
int main()
{
char stra[N], strb[N]; // An array of strings that stores two large Numbers as characters;
int i = 0, step = 4, borrow = 0; //step Is the block length, borrow Is carry bit;
int lengtha, lengthb, tmpnum, numbsize, numcsize, numdsize, maxsize, mark; //maxlength said stra and strb2 The longer one;
int numa[N], numb[N], numc[N], numd[N]; // Store dividend, divisor, quotient, remainder;
memset(stra, 0, sizeof(stra));
memset(strb, 0, sizeof(strb));
memset(numa, 0, sizeof(numa));
memset(numb, 0, sizeof(numb));
memset(numc, 0, sizeof(numc));
memset(numd, 0, sizeof(numd)); // Initialize to zero;
scanf("%s%s", stra, strb);
lengtha = strlen(stra);
lengthb = strlen(strb); // Calculate the length of two large Numbers
// Character and digit conversion 4 position 1 An integer number of blocks
for(i = lengtha-1; i >= 0; --i)
{
numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);
}
for(i = lengthb-1; i >= 0; --i)
{
numb[(lengthb-1-i)/step] += (strb[i]-'0')*Pow(10,(lengthb-1-i)%step);
}
memcpy(numd, numa, sizeof(numa));
numbsize = (lengthb-1)/step;
numcsize = 0;
numdsize = (lengtha-1)/step;
do
{
maxsize = numdsize > numbsize ? numdsize : numbsize;
// Calculate whether the remainder is less than the divisor
mark = 1;
for(i = maxsize; i >= 0; --i)
{
if(numd[i] > numb[i])
{
mark = 1;
break;
}
else if(numd[i] < numb[i])
{
mark = -1;
break;
}
}
// Determine if the remainder is less than the divisor
if(!(mark+1)) break;
borrow = 0; // Borrow position zero;
// I'm going to subtract and borrow
for(i = 0; i <= maxsize; ++i)
{
tmpnum = (numd[i] - numb[i] + Pow(10, step) + borrow)%Pow(10,step); // Calculate poor
borrow = (numd[i] - numb[i] + Pow(10, step) + borrow)/Pow(10,step) - 1; // Calculate a borrow
numd[i] = tmpnum;
}
while(!numd[numdsize]) --numdsize;
// Each reduction 1 Divisor, quotient plus 1 ;
borrow = 1;
for(i = 0; i <= numcsize; ++i)
{
numc[i] += borrow;
borrow = numc[i]/Pow(10,step);
numc[i] %= Pow(10,step);
}
if(borrow)
{
++numcsize;
numc[i] += borrow;
}
}while(1);
printf("%d", numc[numcsize]);
for(i = numcsize-1; i >= 0; --i)
{
printf("%04d", numc[i]); // Right alignment, zero complement output;
}
printf("\n");
printf("%d", numd[numdsize]);
for(i = numdsize-1; i >= 0; --i)
{
printf("%04d", numd[i]); // Right alignment, zero complement output;
}
printf("\n");
return 0;
}