# High-precision

• Core idea: String analog array, large integer (larger than long range) operation.
• Read in:
```    void init(int a[])
{
string s;
cin>>s;
a[0]=s.lenth();
for(int i=1;i<=a[0];++i)
a[i]=s[a[0]-i]-'0';
}
```
• Carry, borrow processing

Additive carry:

```c[i]=a[i]+b[i];
if(c[i]>=10)
{
c[i]%=10;
++c[i+1];
}
```

Subtractive borrowing:

```if(a[i]<b[i])
{
--a[i+1];
a[i]+=10;
}
c[i]=a[i]-b[i];
```

Multiplicative carry:

```c[i+j-1]=a[i]*b[j]+x+c[i+j-1];
x=c[i+j-1]/10;
c[i+j-1]%=10;
```

Quotient and Remainder: Depending on the circumstances

• Code

High Precision Addition (Template: A+B problem High Precision)

```#include<cstdio>
#include<cstring>
using namespace std;

char a1[505],b1[505];
int len1,len2,len3;
int a[505],b[505],c[505];

int main()
{
scanf("%s%s",a1,b1);
len1=strlen(a1);
len2=strlen(b1);
for(int i=0;i<len1;++i)
a[len1-i]=a1[i]-'0';
for(int i=0;i<len2;++i)
b[len2-i]=b1[i]-'0';
len3=1;
int x=0;
while(len3<=len1||len3<=len2)
{
c[len3]=a[len3]+b[len3]+x;
x=c[len3]/10;
c[len3]%=10;
len3++;
}
c[len3]=x;
if(c[len3]==0)len3--;
for(int i=len3;i>=1;--i)
printf("%d",c[i]);
return 0;
}
```

High Precision Subtraction (Template: High Precision Subtraction)

```#include<cstdio>
#include<cstring>
#define maxn 10005
using namespace std;

char a1[maxn],b1[maxn],m[maxn];
int len1,len2,len3,flag;
int a[maxn],b[maxn],c[maxn];

int main()
{
scanf("%s%s",a1,b1);
if(strlen(a1)<strlen(b1)||(strlen(a1)==strlen(b1)&&strcmp(a1,b1)<0))
{
flag=1;
strcpy(m,a1);
strcpy(a1,b1);
strcpy(b1,m);
}//Commutative array
len1=strlen(a1);
len2=strlen(b1);
for(int i=0;i<len1;++i)a[len1-i]=a1[i]-'0';
for(int i=0;i<len2;++i)b[len2-i]=b1[i]-'0';
len3=1;
int x=0;
while(len3<=len1||len3<=len2)
{
if(a[len3]<b[len3])
{
a[len3]+=10;
a[len3+1]--;
}//Borrow position
c[len3]=a[len3]-b[len3];
len3++;
}
while(c[len3]==0&&len3>1)len3--;
if(len3==1&&c[1]==0)
{
printf("0");
return 0;
}
if(flag)
printf("-");
for(int i=len3;i>=1;--i)
printf("%d",c[i]);
return 0;
}
```

High Precision Multiplication (Template: A*B problem)

```#include<cstdio>
#include<cstring>
#define maxn 5005
using namespace std;

char a1[maxn],b1[maxn];
int len1,len2,len3;
int a[maxn],b[maxn],c[maxn];

int main()
{
scanf("%s%s",a1,b1);
len1=strlen(a1);
len2=strlen(b1);
for(int i=0;i<len1;++i)a[len1-i]=a1[i]-'0';
for(int i=0;i<len2;++i)b[len2-i]=b1[i]-'0';
for(int i=1;i<=len1;++i)
{
int x=0;
for(int j=1;j<=len2;++j)
{
c[i+j-1]+=a[i]*b[j]+x;
x=c[i+j-1]/10;
c[i+j-1]%=10;
}
c[i+len2]=x;
}
len3=len1+len2;
while(c[len3]==0&&len3>1)len3--;
for(int i=len3;i>=1;--i)
printf("%d",c[i]);
return 0;
}
```

High Precision Division (High Precision Division by Low Precision) (Template: A/B problem)

```#include<cstdio>
#include<cstring>
#define maxn 10005
using namespace std;

int len1,len2;
int b,a[maxn],c[maxn];
char a1[maxn];

int main()
{
scanf("%s%d",a1,&b);
len1=strlen(a1);
for(int i=0;i<len1;++i)a[i+1]=a1[i]-'0';
int x=0;
for(int i=1;i<=len1;++i)
{
c[i]=(x*10+a[i])/b;
x=(x*10+a[i])%b;
}
len2=1;
while(c[len2]==0&&len2<len1)len2++;
for(int i=len2;i<=len1;++i)
printf("%d",c[i]);
return 0;
}
```

High Precision Division (High Precision Division by High Precision) (Template: A/B problem II)

```#include<cstdio>
#include<cstring>
#include<iostream>
#define maxn 1005
using namespace std;

int a[maxn],b[maxn],c[maxn];

void read(int a[])
{
string s;
cin>>s;
a[0]=s.length();
for(int i=1;i<=a[0];++i)
a[i]=s[a[0]-i]-'0';
}//Read in

void print(int a[])
{
if(a[0]==0)
{
printf("0\n");
return;
}
for(int i=a[0];i>0;--i)
printf("%d",a[i]);
printf("\n");
return;
}//output

int cmp(int a[],int b[])
{
if(a[0]>b[0])return 1;
if(a[0]<b[0])return -1;
for(int i=a[0];i>0;--i)
{
if(a[i]>b[i])return 1;
if(a[i]<b[i])return -1;
}
return 0;
}//Compare the sizes of arrays a and B

void jian(int a[],int b[])
{
int flag;
flag=cmp(a,b);
if(flag==0)
{
a[0]=0;
return;
}//Equal
if(flag==1)
{
for(int i=1;i<=a[0];++i)
{
if(a[i]<b[i])
{
a[i+1]--;
a[i]+=10;
}//Borrow position
a[i]-=b[i];
}
while(a[0]>0&&a[a[0]]==0)a[0]--;
return;
}
}//Analog subtraction

void numcpy(int p[],int q[],int del)
{
for(int i=1;i<=p[0];++i)
q[i+del-1]=p[i];
q[0]=p[0]+del-1;
}//Array replication

void chugao(int a[],int b[],int c[])
{
int tmp[maxn];
c[0]=a[0]-b[0]+1;
for(int i=c[0];i>=1;--i)
{
memset(tmp,0,sizeof(tmp));
numcpy(b,tmp,i);
while(cmp(a,tmp)>=0)
{
c[i]++;
jian(a,tmp);
}
}
while(c[0]>0&&c[c[0]]==0)c[0]--;
return;
}

int main()
{
read(a);read(b);
chugao(a,b,c);
print(c);
print(a);//Output Residual
return 0;
}
```

# * Stirling number correlation algorithm

Added by AjBaz100 on Thu, 01 Aug 2019 12:08:38 +0300