高精度计算算法

————彭晓林

算法需求分析：编程语言所带的计算精度不够高，从顶层浮点数转换到底层控制器寄存器值，由于精度问题导致信号误差过大导致信号精度问题（如AD转换数据，配给fpga寄存器数据等）。

此算法是我从网上代码修改而来，用来适应我现在项目中的代码。其中精度为 3 位65536 进制数据。

#include "stdafx.h"
#include<stdio.h>
#include<memory.h>
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;
#define MAX 8//至少是所表示位数精度的两倍
#define DEC 10
#define HEX 16
const unsigned int LARGE = 65536;//LARGER=65536^(G-1)
#define G 2 //65536^(G-1)进制
class BigInt{
public:
unsigned len;
unsigned int v[MAX];//至少是表示精度数据类型的两倍
int sign;//记录数值符号
int rec;//记录除数是否为0
BigInt();
~BigInt();
/**************************
重载了三个赋值运算
调用各运算时要先由Mov()函数将他们转化存储到数组v里面
**************************/
void Mov(BigInt& A);
void Mov(char*A);
void Mov(int A);
void Copy(BigInt& A,int bg,int n);
BigInt Add(BigInt& A);
BigInt Sub(BigInt& A);
BigInt Mul(BigInt& A);
BigInt Div(BigInt& A,BigInt& L);
//比较函数
int Cmp(BigInt& A);
int Cmp(BigInt& A,int b,int l);//b是A.v数组中开始比较的位数，l是结束比较的位置
void Display();
};
BigInt::BigInt(){
len=1;
for(int i=0;i<MAX;i++){
v[i]=0;
}
}
BigInt::~BigInt(){
}
int BigInt::Cmp(BigInt& A){
if(len>A.len)return 1;
if(len<A.len)return -1;
for(int i=len-1;i>=0;i--){
if(v[i]>A.v[i])return 1;
if(v[i]<A.v[i])return -1;
}
return 0;
}
int BigInt::Cmp(BigInt&A,int b,int l){
if(len>l-b+1)return 1;
if(len<l-b+1)return -1;
int j=l;
for(int i=len-1;i>=0;i--,j--){
if(v[i]>A.v[j]){return 1;}
if(v[i]<A.v[j])return -1;
}
return 0;
}
void BigInt::Mov(int A){
v[0]=A;
int i,k;
k=A;
i=0;
while(k>0){
v[i]=k-k/LARGE*LARGE;
k=k/LARGE;
i++;
}
len=i;
}
void BigInt::Mov(BigInt& A){
len=A.len;
int i = 0;
for(i=0;i<len;i++){
v[i]=A.v[i];
}
while(i<MAX){
v[i]=0;
i++;
}
}
void BigInt::Mov(char *A){
int A_len=strlen(A);
int k,i,j,t;
len=A_len/(G-1);
if(A_len%(G-1))len++;
for(i=0,j=A_len-1;i<len&&j>=0;i++){
k=1;
t=1;
while(j>=0&&k<G){
v[i]+=(A[j]-'0')*t;
t*=10;
j--;
k++;
}
}
}
BigInt BigInt::Add(BigInt& A){
BigInt X;
X.Mov(*this);
int sum=0;
int carry=0;
if(X.len<A.len){
X.len=A.len;
}
for(int i=0;i<=X.len;i++){
sum=A.v[i];
sum=sum+X.v[i]+carry;
X.v[i]=sum%LARGE; //10^(G-1)进制
carry=sum/LARGE;
}
if(X.v[X.len]){
X.len++;
}
return X;
}
BigInt BigInt::Sub(BigInt& A){
BigInt X;
BigInt T;
X.sign=0;
X.Mov(*this);
T=X;
if(X.Cmp(A)<0){
X.sign=1;
BigInt Y;
Y.Mov(X);
X.Mov(A);
A.Mov(Y);
T=X;
}
int carry=0;
for(int i=0;i<X.len;i++){
if((T.v[i]>=A.v[i]+carry)){
X.v[i]=T.v[i]-carry-A.v[i];
carry=0;
}
else{
X.v[i]=LARGE+T.v[i]-A.v[i]-carry;
carry=1;
}
}
while(X.v[X.len-1]==0&&X.len>1)X.len--;
return X;
}
BigInt BigInt::Mul(BigInt& A){
BigInt X;
int rec;
int carry=0;
int i,j;
X.len=len+A.len;
for(i=0;i<X.len;i++){
X.v[i]=0;
}
for(i=0;i<len;i++){
for(j=0;j<A.len;j++){
X.v[i+j]+=v[i]*A.v[j];
}
}
for(i=0;i<X.len;i++){
rec=X.v[i]+carry;
X.v[i]=rec%LARGE;
carry=rec/LARGE;
}
while(X.len>1&&X.v[X.len-1]==0){
X.len--;
}
return X;
}
BigInt BigInt:: Div(BigInt& A,BigInt& X){//X保存余数;
BigInt S;//S保存商;
BigInt Y;
X.Mov(*this);
X.rec=0;
S.Mov(0);
if(A.Cmp(S)==0){
X.rec=1;
return X;
}
if(X.Cmp(A)<0){
S.Mov(0);
}
else{
S.len=X.len-A.len+1;
int l=A.len;
int i,j,t,k,g,c,h;
int carry;
c=0;
//模拟除法，避免高精度乘法，用减法运算，不过用高精度乘法应该会更快一点
for(i=X.len-1,j=S.len-1;i>=A.len-1&&j>=0;i--,j--){
t=0;h=2;
X.v[i]+=c*LARGE;
while(A.Cmp(X,i-A.len+1,i)<=0){
if(A.Cmp(X,i-A.len+1,i)>0)break;
carry=0;
for(k=0,g=i-A.len+1;k<A.len;k++,g++){
if((X.v[g]>=A.v[k]+carry)){
X.v[g]=X.v[g]-carry-A.v[k];
carry=0;
}
else{
X.v[g]=LARGE+X.v[g]-A.v[k]-carry;
carry=1;
}
}
t++;
}
Y.Mov(X);
c=X.v[i];
X.v[i]=0;
X.len--;
S.v[j]=t;
}
while(S.v[S.len-1]==0&&S.len>1)S.len--;
X.Mov(Y);
while(X.v[X.len-1]==0&&X.len>1)X.len--;
}
return S;
}
void BigInt::Display(){
for(int i=len-1;i>=0;i--){
printf("%d ",v[i]);//printf("%0(G-1)d",v[i]);当G=3时为100进制，则printf("%02d",v[i];
}
printf("\n");
}
class TEST{
public:
void add(BigInt& A,BigInt B){
BigInt C = A.Add(B);
C.Display();
}
void cmp(BigInt& A,BigInt B){
int i=A.Cmp(B);
if(i==1)printf("A>B\n");
if(i==0)printf("A==B\n");
if(i==-1)printf("A<B\n");
}
void sub(BigInt& A,BigInt B){
BigInt C = A.Sub(B);
if(C.sign)printf("-");
C.Display();
}
void mul(BigInt& A,BigInt& B){
BigInt C = A.Mul(B);
C.Display();
}
void div(BigInt& A,BigInt& B){
BigInt X;
BigInt C = A.Div(B,X);
if(C.rec==1){
printf("除数为0\n");
}
else{
printf("商:\n");
C.Display();
printf("余数:\n");
X.Display();
}
}
};
int main(){
int g,h;
TEST test;
while(1){
BigInt a;
a.v[0] = 0;
a.v[1] = 0;
a.v[2] = 65535;
a.len = 3;
BigInt b;
b.v[0] = 0;
b.v[1] = 65535;
b.v[2] = 0;
b.len = 3;
a.Display();
b.Display();
printf("test A + B\n");
test.add(a,b);
printf("test A - B\n");
test.sub(a,b);
printf("test A * B\n");
test.mul(a,b);
printf("test A/B\n");
test.div(a,b);

}
return 0;
}