高精度指数运算（POJ1001_Exponentiation）

前言

第一次写技术博客，请大家多多指教，谢谢！

 

问题描述
本题目是关于非常高精度数字的通用计算的问题。此题需要你写一个程序，精确的计算R的n次方，R是一个实数，范围0.0<R<99.999，n是一个整数，范围0<n<=25
输入为一对值R和n，R的值占据1~6位，n的值占据8~9位
输出为R^n的结果。不要输出没有意义的0。如果结果为整数，不要输出小数点。
Sample Input
95.123 12
0.4321 20
5.1234 15
6.7592  9
98.999 10
1.0100 12

Sample Output
548815620517731830194541.899025343415715973535967221869852721
.00000005148554641076956121994511276767154838481760200726351203835429763013462401
43992025569.928573701266488041146654993318703707511666295476720493953024
29448126.764121021618164430206909037173276672
90429072743629540498.107596019456651774561044010001
1.126825030131969720661201

 

问题分析

       这道题要高精度的乘方运算，并且不希望略去任何小数点的位数。那么，我们要思考的问题是，第一，计算机如何去存储任意精度和长度的数字？第二，怎样去模拟高精度的小数运算？

        对于第一个问题，因为一般的编程语言（如C和Java）只提供了最大64bit的数据长度，不能满足此题的需求，而有些动态语言如Python允许任意长度的整数存储，但是不提供对任意常数的小数的支持，因此我们必须自己来设计一种数据结构，存储任意长度实数。我首先想到的是使用数组来做存储，数据的长度根据输入的数据来确定，是否可行，需要结合高精度小数的计算方法来衡量。

        对于第二个问题，我们怎么来做高精度的小数的运算呢？我们知道，x86体系的CPU在计算整数乘法的时候有内建的指令支持，速度很快，而浮点数的乘法运算即使目前有CPU的指令级的支持，但对比乘法运算，依然要慢很多（这方面的内容大家可以google了解更多），因此在考虑计算方法的时候优先考虑使用整数运算来模拟小数的运算。

        如果我们从输入的数据中记录下小数点的位数，我们就可以根据乘方的次数计算出运算结果的小数点的位置。

        这样，就可以将小数的运算转换成整数的运算，即整数的大数运算问题。

        任何一个整数按十进制进行展开，可以化作：

        A0*10^0 + A1*10^1 + ... + An*10^n

        而整数的相乘，则可以化作多项式的乘法，而指数n的大小就是多项式相乘的次数。

        我们用数组来存储十进制多项式，数组的索引就是多项式的幂，而数组的元素就是多项式的系数。这样，数据结构和算法就算基本确定下来了。接下来直接贴出代码来描述计算的过程：

 

  int[] dstDigits = new int[numLength * exp]; //被乘数
		int[] midRst = new int[numLength * exp]; //存储中间结果
		int[] srcDigits = new int[numLength]; //乘数
		int dotPos = dotLength * exp; //小数点的位置
		
		dstDigits[0] = 1; // 被乘数初始化为1
		int highFlag = 0 + 1; //指示最高位
		for (int i = 0; i < numLength; i++) { // 初始化乘数多项式
			srcDigits[i] = (int)inteNum.charAt(numLength - i - 1) - '0';
		}
		
                // 开始运算
		for (int z = 0; z < exp; z++) {
			int times = highFlag;
			for (int dPos = 0; dPos < times; dPos++) {
				for (int sPos = 0; sPos < srcDigits.length; sPos++) {
					int pos = dPos + sPos;
					// update highFlag
					if (pos + 1 > highFlag) highFlag = pos + 1;
					midRst[pos] += dstDigits[dPos] * srcDigits[sPos];
					if (midRst[pos] / 10 > 0) {
						int tmp = midRst[pos];
						midRst[pos] = tmp % 10;
						midRst[pos + 1] += tmp / 10;
						// update highFlag
						if (pos + 1 + 1 > highFlag) highFlag = pos + 1 + 1;
					}
				}
			}
			for (int s = 0; s < highFlag; s++) {
				dstDigits[s] = midRst[s];
				midRst[s] = 0;
			}
		}
		
		// 结果的输出
		if (dotPos > highFlag) {
			int zeroCnt = dotPos - highFlag;
			System.out.print('.');
			for (int x = 0; x < zeroCnt; x++) {
				System.out.print('0');
			}
		}
		
		for (int i = highFlag; i > 0; i--) {	
			if (i == dotPos) System.out.print('.');
			System.out.print(dstDigits[i - 1]);
		}

 运行结果：

95.123 12

548815620517731830194541.899025343415715973535967221869852721

0.4321 20

.00000005148554641076956121994511276767154838481760200726351203835429763013462401

5.1234 15

43992025569.928573701266488041146654993318703707511666295476720493953024

6.7592  9

29448126.764121021618164430206909037173276672

 

98.999 10
90429072743629540498.107596019456651774561044010001

1.0100 12

1.126825030131969720661201