由于编程语言提供的基本数值数据类型表示的数值范围有限,不能满足较大规模的高精度数值计算,因此需要利用其他方法实现高精度数值的计算。实现高精度数值计算,虽然不能利用编程语言提供的基本数值数据类型,但是可以利用字符串存储高精度数,计算的结果同样保存在字符串中,将高精度数运算转化为字符串运算。以下列举出高精度数相关运算。
1.大数加法
/* * 高精度数 * 结果存储在字符串a中,字符串a初始为0 * 计算结束,将字符串a翻转即为高精度数a,b的和 */ void add(char *a, char *b) { strrev(a); strrev(b); //reverse string b int la = strlen(a); //cal the length of a int lb = strlen(b); //cal the length of b int i = 0, j = 0, k = 0, s = 0, inc = 0; while(i < la && j < la) { s = (a[i] & 0XF) + (b[j] & 0XF) + inc; a[k++] = (s % 10) + '0'; //add b to a inc = s / 10; //store the carry i++; j++; } while(i < la) //length of a is greater than b { s = (a[i] & 0XF) + inc; a[k++] = (s % 10) + '0'; inc = s / 10; i++; } while(j < lb) //length of b is greater than a { s = (b[j] & 0XF) + inc; a[k++] = (s % 10) + '0'; inc = s / 10; j++; } if(inc != 0) //at last,if the carry is not 0,store it into a a[k++] = inc + '0'; strrev(a); }
2.大数减法
大数减法相对加法较为复杂,但是只要注意借位操作的正确性,还是能够较为轻松写出正确的大数减法运算的。
//高精度数减法 string sub(string num1, string num2) { string ans; int *a, *b, i, max, len, len1, len2, k; len1 = num1.length(); len2 = num2.length(); len = len1; max = len; a = new int[len]; b = new int[len]; for(i = 0; i <= len - 1; i++) { a[i] = 0; b[i] = 0; } k=0; for(i = len1 - 1; i >= 0; i--) a[k++] = num1[i] - '0'; k = 0; for(i = len2 - 1; i >= 0; i--) b[k++] = num2[i] - '0'; for(i = 0; i <= len - 1; i++) { if(a[i] < b[i]) { a[i + 1]--; a[i] = a[i] + 10; a[i] = a[i] - b[i]; } else a[i] = a[i] - b[i]; } while(a[len] == 0 && len > 0 || len >= max) len--; for(i = len; i >= 0; i--) ans.append(1, a[i] + '0'); return ans; }
3.大数乘法
大数乘法利用了大数加法的思想,需要注意的是进位的操作。
/* * 返回两个大数相乘的结果 */ string multiple(string a, string b) { string result = "0", str; int i, j, remain, tmp, m, n; for(i = a.length() - 1; i >= 0; i--) { str = ""; remain = 0; //at first the carry is 0 for(j = b.length() - 1; j >= 0; j--) { tmp = (a[i] & 0XF) * (b[j] & 0XF) + remain; remain = tmp / 10; //store the carry str = (char)(tmp % 10 + '0') + str; } if(remain != 0) { str = (char)(remain + '0') + str; } tmp = 0; m = result.length() - (a.length() - i); n = str.length() - 1; remain = 0; while(m >= 0 && n >= 0) //add str to result { tmp = (result[m] & 0XF) + (str[n] & 0XF) + remain; remain = tmp / 10; result[m] = (char)(tmp % 10 + '0'); m--; n--; } while(m >= 0) { tmp = (result[m] & 0XF) + remain; remain = tmp / 10; result[m] = (char)(tmp % 10 + '0'); m--; } while(n >= 0) { tmp = (str[n] & 0XF) + remain; remain = tmp / 10; result = (char)(tmp % 10 + '0') + result; n--; } if(remain != 0) { result = (char)(remain + '0') + result; } } return result; }