C语言——高精度除法

2023-12-22 22:07:56

一、引子

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来除以lowDecimalResult[]用来存储商的小数部分。

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

  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;
}

文章来源:https://blog.csdn.net/stewie6/article/details/135035876
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。