C语言——高精度除法

一、引子

1、引言

高精度除法相较于加减乘法更加复杂，它需要处理的因素更多，在这里我们先探讨高精度数除以低精度数，即大数除小数。这已满足日常所需，如需大数除以大数，可以使用专门的库，例如：

GNU Multiple Precision Arithmetic Library (GMP)

• 这是最知名的任意精度数学库，提供了丰富的功能来处理整数、有理数和浮点数的高精度运算。

MPIR

• 一个与GMP兼容的库，它被设计为GMP的直接替代品，在某些系统上可能提供更好的性能。

The GNU MPFR Library

• 基于GMP构建，提供了严格圆整的多精度浮点运算能力。

使用这些库中的任何一个都需要你下载和链接到你的C程序中。这些库的文档通常会指导你如何将它们集成到你的项目中。集成后，你可以使用库提供的函数来执行高精度的整数和小数运算。

2、介绍

这里我们要实现大数除以小数，实际原理其实是模拟我们手算除法：

与高精度加减乘法不同的是，高精度除法是从高位开始运算，一步一步运算到最低位的，所以不用将被除数字符串反转。

二、核心算法

核心算法是由刚才的手算除法得来的，如下：

#define MAX 505
#define DECIMAL_PART 50//小数部分保留五十位

int i = 0;
int remainder = 0;
int high[MAX] = { 0 };

for (i = 0; i < high_len; i++)//高精度除法核心算法，模拟我们手算除法，从最高位开始除
{
	long long division = remainder * 10LL + high[i];//余数乘十，加上整数部分i位的数字作为被除数
	IntegerResult[i] = (int)division / low;//结果是被除数除以除数，这里是有余数的整数除法
	remainder = (int)division % low;//取余，下一步乘十后作为下一位的除数
}

for (i = 0; i < DECIMAL_PART + 1; i++)//小数部分计算,多计算一位，以便后面进行四舍五入
{
	remainder *= 10;//余数乘十作为被除数
	DecimalResult[i] = remainder / low;//计算小数部分i位的结果
	remainder %= low;//取余，下一步乘十后作为下一位的除数
}

核心算法分为两部分，一部分是求商的整数部分，一部分是求商的小数部分。

(1)商的整数部分代码是手动实现的长除法过程，模仿我们在纸上做除法时的步骤。这里使用数组high[]来表示高精度的被除数，low是低精度的除数，IntegerResult[]用来存储商的整数部分。

让我们逐步分析这段代码的工作原理：

1. for循环：循环遍历高精度数high[]的每一位，从数字最高位开始进行运算。

2. long long division = remainder * 10LL + high[i];：

   • remainder是前一次除法后剩下的余数，初始化为0，因为我们从最高位开始除，最开始没有余数。
   • remainder * 10LL将余数乘以10，因为在长除法中，每向下一位，都相当于余数乘以10再加上新的一位。这里的10LL是一个long long类型的常量，确保运算结果能够存储在long long类型变量中，以避免溢出。
   • + high[i]是将当前处理的这一位数加到余数乘以10之后的值上，形成新的被除数。

3. IntegerResult[i] = division / low;：

   • 这行代码执行实际的除法运算。division是新的被除数，low是除数，计算出的商被存储在结果数组IntegerResult[i]的当前位置。

4. remainder = division % low;：

   • 这里计算新的余数，为下一位计算做准备。division % low计算了division除以low之后的余数。

循环中的每次迭代都处理高精度数的一位，并将其与前一位剩下的余数结合起来，进行除法运算。最终，这个for循环会填满整个IntegerResult[]数组，数组中的每个元素都是对应位上的商。

这个过程一直继续，直到所有的高精度数位都被处理完毕。我们通过不断将余数乘以10并加上下一位来逐位处理整个高精度数，这与手工执行长除法的过程相同。最后得到的IntegerResult[]数组就是除法操作的结果，而循环结束后剩下的remainder就是最终的余数。

(2)商的小数部分代码依旧是手动实现的长除法过程，模仿我们在纸上做除法时的步骤。这里使用remainder来除以low，DecimalResult[]用来存储商的小数部分。

接着我们逐步分析这段代码的工作原理：

1. for循环：保留50位小数，多计算一位，为了后面的四舍五入，从数字最高位开始进行运算。

2. remainder *= 10;：

   • remainder整数商计算好后的余数，乘十后作为被除数，因为原被除数小数部分为0，所以相对于商的整数部分不用加其他的。

3. DecimalResult[i] = remainder / low;：

   • 这行代码执行实际的除法运算。remainder是新的被除数，low是除数，计算出的商被存储在结果数组DecimalResult[i]的当前位置。

4. remainder %= low;：

   • 这里计算新的余数，为下一位计算做准备。remainder %= low;计算了remainder除以low之后的余数。

最后商的小数部分也就求出了。

三、代码实现

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX 505
#define DECIMAL_PART 50//小数部分保留五十位

void StringTranstoDigit(char numch[], int num[],int length)//字符数组转成整型数组
{
	int i = 0;
	for (i = 0; i < length; i++)
	{
		num[i] = numch[i] - '0';
	}
}

void highDivLow(char highch[], int high_len, int low, int IntegerResult[],int DecimalResult[])//高精度除法
{
	if (low == 0)//除数为零的情况
	{
		fprintf(stderr,"divisor can not be zero!\n");//输出错误信息
		exit(EXIT_FAILURE);//退出程序，运行过程中失败
	}
	int i = 0;
	int remainder = 0;
	int high[MAX] = { 0 };

	StringTranstoDigit(highch,high,high_len);//字符转整型

	for (i = 0; i < high_len; i++)//高精度除法核心算法，模拟我们手算除法，从最高位开始除
	{
		long long division = remainder * 10LL + high[i];//余数乘十，加上整数部分i位的数字作为被除数
		IntegerResult[i] = (int)division / low;//结果是被除数除以除数，这里是有余数的整数除法
		remainder = (int)division % low;//取余，下一步乘十后作为下一位的除数
	}

	for (i = 0; i < DECIMAL_PART + 1; i++)//小数部分计算,多计算一位，以便后面进行四舍五入
	{
		remainder *= 10;//余数乘十作为被除数
		DecimalResult[i] = remainder / low;//计算小数部分i位的结果
		remainder %= low;//取余，下一步乘十后作为下一位的除数
	}

	if (DecimalResult[DECIMAL_PART] >= 5)//四舍五入
	{
		DecimalResult[DECIMAL_PART - 1]++;
	}
	for (i = DECIMAL_PART; i > 0; i--)//处理四舍五入后的进位，小数部分进位
	{
		int carry = 0;
		carry = DecimalResult[i] / 10;
		DecimalResult[i] %= 10;
		DecimalResult[i - 1] += carry;
	}
	if (DecimalResult[0] >= 10)//小数进整数位
	{
		IntegerResult[high_len - 1] = DecimalResult[0] / 10;
		DecimalResult[0] %= DecimalResult[0];
	}
}

void Print(int num[],int numdec[],int length)//打印整数和小数部分
{
	int i = 0;
	while (i < length - 1 && num[i] == 0)//去除前导零
	{
		i++;
	}
	for (; i < length ; i++)//打印整数部分
	{
		printf("%d",num[i]);
	}
	printf(".");//小数点
	for (i = 0; i < DECIMAL_PART; i++)//打印小数部分
	{
		printf("%d",numdec[i]);
	}
}

int main()
{
	char high[MAX] = { 0 };//高精度数，被除数
	scanf("%s",high);

	int low = 0;//低精度数，除数
	scanf("%d",&low);


	int IntegerResult[MAX] = { 0 };//结果整数部分
	int DecimalResult[DECIMAL_PART + 1] = { 0 };//结果小数部分

	int high_len = (int)strlen(high);//被除数长度

	highDivLow(high, high_len, low, IntegerResult,DecimalResult);//高精度除法

	Print(IntegerResult,DecimalResult,high_len);//打印
	return 0;
}