首页 > 代码库 > 高精度浮点数运算

高精度浮点数运算

2024-07-31 23:29:51   226人阅读

/*
Name: 高精度浮点数运算 
Copyright: 
Author: 巧若拙 
Date: 08-11-14 10:17
Description: 
本程序实现了高精度浮点数的加法，减法，乘法，乘方和除法运算，有效数字精确到MAX。
为了便于进位，本程序采用了较为独特的数据结构，即把浮点数分成整数和小数部分，分别存储在两个不同的数组中。
其中整数部分数字存储在ValInt[MAX-lenInt...MAX) ，小数部分数字存储在ValDec[1...lenDec]，ValDec[0]用来存储进位或借位。
这样在计算中补齐0的时候不需要移动数组元素，只需移动下标即可，大大提升了效率。 
为了便于理解和编程，程序中每个数组元素只存储了一个数字，争取在下一版本中实现每个数组元素存储4个数字，以便提高效率。 
*/
#include<stdio.h>
#include<stdlib.h>


#define MAX 2000


typedef struct BigNums{
    char ValInt[MAX] ;//整数部分，数字存储在ValInt[MAX-lenInt...MAX) 
char ValDec[MAX] ;//小数部分，数字存储在ValDec[1...lenDec]，ValDec[0]用来存储进位或借位  
    int lenInt, lenDec;//分别表示整数和小数部分长度 
    char pos; //‘+‘表示是正数，‘-‘表示是负数 
} BigNums; //高精度计算结构体 


BigNums CreatBigNums(char str[]);
void PrintBigNums(BigNums A);
int ArrCmp(char A[], char B[], int lenA, int lenB);//比较两个数组的大小
int CompareBigNums(BigNums *A, BigNums *B);
void AddBigNums(BigNums *C, BigNums *A, BigNums *B);//高精度加法的驱动函数
void SubBigNums(BigNums *C, BigNums *A, BigNums *B);//高精度减法的驱动函数
void Add(BigNums *C, BigNums *A, BigNums *B);//C = A +  B，确保A,B都是正数
void Sub(BigNums *C, BigNums *A, BigNums *B);//C = A -  B，确保A,B都是正数，且A > B 
void AddFun(char C[], char A[], char B[], int left, int right);//C = A + B，确保A,B等长，且每个数组元素只存储一个数字
void SubFun(char C[], char A[], char B[], int left, int right);//C = A - B，确保A,B等长，且A > b
void DivBigNums(BigNums *C, BigNums *A, BigNums *B);//高精度除法的驱动程序 
void Div(BigNums *C, BigNums *A, BigNums *B);//高精度除法 
int ZeroArray(char A[], int left, int right);//判断数组元素是否全部为0 
void MulBigNums(BigNums *C, BigNums *A, BigNums *B);//高精度乘法的驱动程序 
void Mul(BigNums *C, BigNums *A, BigNums *B);//高精度乘法 
void PowBigNums(BigNums *C, BigNums *A, int n);//高精度幂运算 


char main(void)
{
    char str1[MAX], str2[MAX];
    BigNums A, B, C;
    int n;


//    while (scanf("%s%s", str1, str2) != EOF) 
//    {
//        A = CreatBigNums(str1); PrintBigNums(A);
//        B = CreatBigNums(str2); PrintBigNums(B);
//        AddBigNums(&C, &A, &B);
//        PrintBigNums(C);
//    } 
////    
//     while (scanf("%s%s", str1, str2) != EOF) 
//    {
//      //  printf("s1 = %s, s2 = %s\n", str1, str2);
//        A = CreatBigNums(str1); 
//        B = CreatBigNums(str2); 
//        SubBigNums(&C, &A, &B);
//        PrintBigNums(C);
//    } 
    
//    while (scanf("%s%s", str1, str2) != EOF) 
//    {
//      //  printf("s1 = %s, s2 = %s\n", str1, str2);
//        A = CreatBigNums(str1); 
//        B = CreatBigNums(str2); 
//        DivBigNums(&C, &A, &B);
//        PrintBigNums(C);
//    } 


// while (scanf("%s%s", str1, str2) != EOF) 
//    {
//        A = CreatBigNums(str1); 
//        B = CreatBigNums(str2); 
//        MulBigNums(&C, &A, &B);
//        PrintBigNums(C);
//    } 
    
    while (scanf("%s%d", str1, &n) == 2) 
    {
        A = CreatBigNums(str1);
        PowBigNums(&C, &A, n);
        PrintBigNums(C);
    } 


    return 0;
}




void PrintBigNums(BigNums A)
{
    int i;
    
    if (A.pos == ‘-‘)//输出负号 
    printf("-");
   
    for (i=MAX-A.lenInt; i<MAX; i++)
        printf("%d", A.ValInt[i]);
    
    if (A.lenDec > 0)
    {
        printf(".");
        for (i=1; i<=A.lenDec; i++)
        printf("%d", A.ValDec[i]);
    }
    printf("\n");
}


BigNums CreatBigNums(char str[])
{
    int i, j, n, f;
    BigNums A;
    
    i = 0;
    if(str[i] == ‘-‘)//判断是正数还是负数
{
A.pos = ‘-‘;
i++;
} 
else
{
A.pos = ‘+‘;
}

n = 0;
    while (str[i] != ‘.‘ && str[i] != ‘\0‘)//获取整数部分 
    {
        A.ValInt[n++] = str[i++] - ‘0‘;
    }
    
    A.ValDec[0] = 0; //A.ValDec[0] 用来存储进位或借位，初始化为0 
    f = 0;
    if (str[i] == ‘.‘)
    {
        i++;
        while (str[i] != ‘\0‘)//获取小数部分 
        {
            A.ValDec[++f] = str[i++] - ‘0‘;
        }
    }
    
    A.lenDec = f;
    while (A.lenDec > 0 && A.ValDec[A.lenDec] == 0)//消除小数部分多余的后缀0 
    {
        A.lenDec--;    
    }
    
    for (i=MAX-1,j=n-1; j>=0; i--,j--)//把整数部分移动到数组的右侧 
    A.ValInt[i] = A.ValInt[j];

for (j=0; j<=i; j++) //数组的其他部分初始化为0 
A.ValInt[j] = 0;


while (A.ValInt[i] == 0) //消除整数部分多余的前缀0 
i++;

A.lenInt = MAX - i;


    return A;
}


int CompareBigNums(BigNums *A, BigNums *B)
{
int i;
//先直接比较整数的长度 
if (A->lenInt > B->lenInt)
return 1;
else if (A->lenInt < B->lenInt)
return -1;
//比较整数部分 
for (i=MAX-A->lenInt; i<MAX; i++)
{
if (A->ValInt[i] > B->ValInt[i])
return 1;
else if (A->ValInt[i] < B->ValInt[i])
return -1;
}
//比较小数部分 
for (i=1; i<=A->lenDec && i<=B->lenDec; i++)
{
if (A->ValDec[i] > B->ValDec[i])
return 1;
else if (A->ValDec[i] < B->ValDec[i])
return -1;
}
//比较多余的小数部分 
if (A->lenDec > B->lenDec)
return 1;
else if (A->lenDec < B->lenDec)
return -1;
else
return 0;
}




void AddBigNums(BigNums *C, BigNums *A, BigNums *B)//高精度加法的驱动函数
{
if (A->pos == B->pos)
{
Add(C, A, B);
C->pos = A->pos;
}
else //异号则加法转换为减法 
{
if (CompareBigNums(A, B) > 0)
{
Sub(C, A, B);
C->pos = A->pos;
}
else
{
Sub(C, B, A);
C->pos = B->pos;
}
}
} 


void SubBigNums(BigNums *C, BigNums *A, BigNums *B)//高精度减法的驱动函数
{
if (A->pos != B->pos) //异号则减法转换为加法 
{
Add(C, A, B);
C->pos = A->pos;
}
else  
{
if (CompareBigNums(A, B) > 0) 
{
Sub(C, A, B);
C->pos = A->pos;
}
else
{
Sub(C, B, A);
C->pos = (B->pos == ‘+‘) ? ‘-‘ : ‘+‘;//C的符号与B相反 
}
}
} 


//C = A + B，确保A,B等长，且每个数组元素只存储一个数字，C[left]用来存储进位 
void AddFun(char C[], char A[], char B[], int left, int right)
{
int i;

for (i=right; i>left; i--)
{
C[i] += A[i] + B[i];
if (C[i] >= 10)//有进位
{
C[i-1] = 1; 
C[i] -= 10; //取个位数字，等效于%10 
} 
}
} 


//C = A - B，确保A,B等长，且A > B 
void SubFun(char C[], char A[], char B[], int left, int right)
{
int i;


for (i=right; i>left; i--)
{
C[i] += A[i] - B[i];
if (C[i] < 0)//有借位
{
C[i-1] = -1; 
C[i] += 10; 
} 
}
} 


void Add(BigNums *C, BigNums *A, BigNums *B)//C = A +  B，确保A,B都是正数
{
int lenInt = (A->lenInt > B->lenInt) ? A->lenInt : B->lenInt;
int lenDec = (A->lenDec > B->lenDec) ? A->lenDec : B->lenDec;
int carry, i, j, n;
char M[MAX] = {0};

//先处理小数部分 
for (i=A->lenDec+1; i<=lenDec; i++) //补足小数部分后缀0 
A->ValDec[i] = 0;
for (i=B->lenDec+1; i<=lenDec; i++) //补足小数部分后缀0 
B->ValDec[i] = 0;

AddFun(M, A->ValDec, B->ValDec, 0, lenDec);
carry = M[0]; //小数部分的进位，值为0或1
C->lenDec = lenDec;
while (C->lenDec > 0 && M[C->lenDec] == 0)//消除小数部分多余的后缀0 
    {
        C->lenDec--;
    } 
    C->ValDec[0] = 0; //复制数字到C->ValDec 
    for (i=1; i<=C->lenDec; i++)
    C->ValDec[i] = M[i];


    //再处理整数部分
for (i=0; i<=C->lenDec; i++) //M再次清零 
M[i] = 0;
for (i=MAX-1-A->lenInt; i>=MAX-lenInt; i--) //补足整数部分前缀0 
A->ValInt[i] = 0;
for (i=MAX-1-B->lenInt; i>=MAX-lenInt; i--) //补足整数部分前缀0 
B->ValInt[i] = 0;

M[MAX-1] = carry;
AddFun(M, A->ValInt, B->ValInt, MAX-1-lenInt, MAX-1); 

for (i=lenInt-1; i<MAX; i++)
C->ValInt[i] = M[i];


if (M[lenInt-1] == 1) //有进位
C->lenInt = lenInt + 1;
else
C->lenInt = lenInt;
} 


void Sub(BigNums *C, BigNums *A, BigNums *B)//C = A -  B，确保A,B都是正数，且A > B 
{
int lenInt = (A->lenInt > B->lenInt) ? A->lenInt : B->lenInt;
int lenDec = (A->lenDec > B->lenDec) ? A->lenDec : B->lenDec;
int borrow, i, j, n;
char M[MAX] = {0};

//先处理小数部分 
for (i=A->lenDec+1; i<=lenDec; i++) //补足小数部分后缀0 
A->ValDec[i] = 0;
for (i=B->lenDec+1; i<=lenDec; i++) //补足小数部分后缀0 
B->ValDec[i] = 0;

SubFun(M, A->ValDec, B->ValDec, 0, lenDec);
borrow = M[0]; //小数部分的借位，值为0或1
C->lenDec = lenDec;
while (C->lenDec > 0 && M[C->lenDec] == 0)//消除小数部分多余的后缀0 
    {
        C->lenDec--;
    } 
    C->ValDec[0] = 0; //复制数字到C->ValDec 
    for (i=1; i<=C->lenDec; i++)
    C->ValDec[i] = M[i];


    //再处理整数部分
for (i=0; i<=C->lenDec; i++) //M再次清零 
M[i] = 0;
for (i=MAX-1-A->lenInt; i>=MAX-lenInt; i--) //补足整数部分前缀0 
A->ValInt[0] = 0;
for (i=MAX-1-B->lenInt; i>=MAX-lenInt; i--) //补足整数部分前缀0 
B->ValInt[0] = 0;

M[MAX-1] = borrow;
SubFun(M, A->ValInt, B->ValInt, MAX-1-lenInt, MAX-1); 
while (M[MAX-lenInt] == 0)//清除多余前缀0
lenInt--; 

for (i=MAX-lenInt; i<MAX; i++)
C->ValInt[i] = M[i];

C->lenInt = lenInt;
} 


void MulBigNums(BigNums *C, BigNums *A, BigNums *B)//高精度乘法的驱动函数
{
if (A->pos == B->pos)
C->pos = ‘+‘;
else 
C->pos = ‘-‘;

Mul(C, A, B);
} 


void Mul(BigNums *C, BigNums *A, BigNums *B)//高精度乘法
{
    char pA[MAX] = {0};//存储A的数字（包括整数和小数）
char pB[MAX] = {0}; //存储B的数字（包括整数和小数）
    char pC[MAX+MAX] = {0};//存储乘积的数字（包括整数和小数）
int leftA, leftB, leftC;  
    int i, j, k;
    
//复制数字 
for (i=MAX-1,j=A->lenDec; j>0; j--)
pA[i--] = A->ValDec[j];
for (j=MAX-1,k=0; k<A->lenInt; j--, k++)
pA[i--] = A->ValInt[j];
leftA = i + 1; //指向pA的最高位
 
for (i=MAX-1,j=B->lenDec; j>0; j--)
pB[i--] = B->ValDec[j];
for (j=MAX-1,k=0; k<B->lenInt; j--, k++)
pB[i--] = B->ValInt[j];
leftB = i + 1; //指向pB的最高位

//乘法运算 
    for (i=MAX-1; i>=leftA; i--) //从低位到高位相乘，可确保低位数字小于10 
    {
    if (pA[i] == 0)
    continue;
    for (j=MAX-1; j>=leftB; j--)
    {
    pC[i+j] += pA[i] * pB[j];
    pC[i+j-1] += pC[i+j] / 10;
    pC[i+j] %= 10;
   
    }
    for (k=i+j; pC[k] >= 10; k--) //分解多位数 
        {
            pC[k-1] += pC[k] / 10;
    pC[k] %= 10;
        }
    }
    leftC = leftA + leftB - 1;
    
    //先复制小数部分，从左往右复制，可以舍弃右边超出精度的小数部分 
    C->lenDec = A->lenDec + B->lenDec; 
    C->ValDec[0] = 0;
    for (i=1,j=MAX+MAX-1-C->lenDec; j<MAX+MAX-1 && i<MAX; i++,j++)
    {
    C->ValDec[i] = pC[j];
    }
     //再取整数部分，这里假设不会超出数组最大空间
for (i=MAX-1, j=MAX+MAX-2-C->lenDec; j>=leftC; i--,j--)
C->ValInt[i] = pC[j];
C->lenInt = MAX -1 -i;
while (C->ValInt[MAX-C->lenInt] == 0) //消除整数部分多余前缀0 
C->lenInt--; 
}


int ZeroArray(char A[], int left, int right)//判断数组元素是否全部为0 
{
int i;

for (i=left; i<=right; i++)
{
if (A[i] != 0)
return 1;
}

return 0;
}


//void PowBigNums(BigNums *C, BigNums *A, int n) //递归算法 
//{
//    if (n == 1)
//    {
//     *C = *A;
//        return ;
//    }
//    if (n == 0)
//    {
//        C->ValInt[MAX-1] = 1;
// C->lenInt = 1;
//        C->lenDec = 0;
//        return;
//    }
//    
//    PowBigNums(C, A, n/2);
//    MulBigNums(C, C, C); 
//    
//    if (n % 2 == 1)
//        MulBigNums(C, C, A); 
//}


void PowBigNums(BigNums *C, BigNums *A, int n) //非递归高效算法 
{
    int stack[MAX] = {0};
    int i, top = 0;
    
    while (n > 0) //利用一个栈来存储n的状态：奇数还是偶数 
    {
    stack[top++] = n % 2;
        n /= 2;
    }
    
    C->ValInt[MAX-1] = 1;
C->lenInt = 1;
    C->lenDec = 0;
    for (i=top-1; i>=0; i--)
    {
    MulBigNums(C, C, C);  //a^n = a^(n/2)*a^(n/2)*f(a)
        if (stack[i] == 1)   //其中f(a) = 1(n%2==0)或f(a) = a(n%2==1)
            MulBigNums(C, C, A); 
    }
}


int ArrCmp(char A[], char B[], int lenA, int lenB)//比较两个数组的大小
{
int i;


if (lenA > lenB)
return 1;
else if (lenA < lenB)
return -1;

for (i=0; i<lenA; i++)
{
if (A[i] > B[i])
return 1;
else if (A[i] < B[i])
return -1;
}

return 0;
} 


void DivBigNums(BigNums *C, BigNums *A, BigNums *B)//高精度除法的驱动函数
{
if (B->lenDec == 0 && B->lenInt == 0)//除数不能为0 
{ 
C->lenDec = 0;
C->lenInt = 0;
return;
} 

if (A->pos == B->pos)
C->pos = ‘+‘;
else 
C->pos = ‘-‘;

Div(C, A, B);
} 


void Div(BigNums *C, BigNums *A, BigNums *B)//高精度除法
{
char pA[MAX+MAX] = {0};
char pB[MAX+MAX] = {0};
char pC[MAX+MAX] = {0};
int lenA = A->lenDec + A->lenInt;
int lenB;
int i, j, d, t, n, left;


pA[0] = 0;//按小数方式存储pA
for(i=1,j=MAX-A->lenInt; j<MAX; j++)
pA[i++] = A->ValInt[j];
for (j=1; j<=A->lenDec; j++)
pA[i++] = A->ValDec[j];

i = MAX - 1;
if (A->lenDec < B->lenDec)//补足因小数部分长度不等而产生的0
lenA += B->lenDec - A->lenDec; 
else
i -= A->lenDec - B->lenDec; 

for (j=B->lenDec; j>0; j--)//按整数方式存储pB 
pB[i--] = B->ValDec[j];
for (j=1; j<=B->lenInt; j++)
pB[i--] = B->ValInt[MAX-j];
lenB = MAX - 1 - i;

//先处理整数
t = 0;
while (lenA >= lenB)
{
i = 0;
while (ArrCmp(pA+1, pB+MAX-lenB, lenB, lenB) >= 0)//只比较长度等于lenB的前部分数字 
{
SubFun(pC, pA, pB+MAX-1-lenB, 0, lenB);
i++;

for (j=1; j<=lenB; j++)//复制pC到pA，并对pC清零 
{
pA[j] = pC[j];
pC[j] = 0;
}
}
C->ValInt[t++] = i;
lenB++;
} 
C->lenInt = t;
for (i=MAX-1,j=t-1; j>=0; i--,j--) //把数字移到正确位置 
C->ValInt[i] = C->ValInt[j];
while (C->ValInt[MAX-C->lenInt] == 0) //消除整数部分多余前缀0 
C->lenInt--;

//再处理小数部分
t = 0;
while (lenA < lenB)//被除数A小于除数B，需要乘以10 
{
C->ValDec[t++] = 0;
lenA++; //pA *= 10 
} 

while (ZeroArray(pA, 1, lenA) != 0 && t < MAX)
{
i = 0;
while (ArrCmp(pA+1, pB+MAX-lenB, lenB, lenB) >= 0)//只比较长度等于lenB的前部分数字 
{
SubFun(pC, pA, pB+MAX-1-lenB, 0, lenB);
i++;

for (j=1; j<=lenB; j++)//复制pC到pA，并对pC清零 
{
pA[j] = pC[j];
pC[j] = 0;
}
}
C->ValDec[t++] = i;
lenA++;
lenB++;
}

C->lenDec = t;
while (C->lenDec > 0 && C->ValDec[C->lenDec] == 0)//消除小数部分多余的后缀0 
    {
        C->lenDec--;
    } 
} 

高精度浮点数运算


联系
我们