seo查询官方网站,天津住房与城乡建设厅网站首页,dede个人网站,深圳企业网站定做文章目录 一、为什么需要高精度算法二、高精度算法的数据结构设计2.1 基础工具函数2.2 高精度加法实现2.3 高精度减法实现2.4 高精度乘法实现2.5 高精度除法实现 三、完整测试程序四、总结 一、为什么需要高精度算法
在编程中#xff0c;处理极大数值是常见需求#xff0c;例… 文章目录 一、为什么需要高精度算法二、高精度算法的数据结构设计2.1 基础工具函数2.2 高精度加法实现2.3 高精度减法实现2.4 高精度乘法实现2.5 高精度除法实现 三、完整测试程序四、总结 一、为什么需要高精度算法
在编程中处理极大数值是常见需求例如
密码学中的大数运算如 RSA 算法中的模幂运算科学计算中的高精度数值计算财务系统中的金额处理数学竞赛中的大数问题求解
C 的原生数据类型如long long有固定数值范围限制通常最大约 9×10^18无法处理任意大小的整数。高精度算法通过将大数字拆分为多个小单元处理以字符串或数组存储每一位数字模拟手工计算实现各种运算。
二、高精度算法的数据结构设计
在 C 中我们可以通过纯函数的方式实现高精度算法避免使用类封装使代码更加简洁直接。以下是各个核心功能的实现
2.1 基础工具函数
首先实现一些基础工具函数用于处理字符串表示的大数
#include iostream
#include string
#include vector
#include algorithm
#include stdexcept// 反转字符串
std::string reverse(const std::string s) {return std::string(s.rbegin(), s.rend());
}// 去除前导零
std::string removeLeadingZeros(const std::string num) {int i 0;while (i num.size() - 1 num[i] 0) {i;}return num.substr(i);
}// 判断是否为负数
bool isNegative(const std::string num) {return num[0] -;
}// 获取绝对值
std::string getAbs(const std::string num) {return isNegative(num) ? num.substr(1) : num;
}// 比较两个非负数字的大小
bool absGreaterOrEqual(const std::string a, const std::string b) {if (a.length() ! b.length()) {return a.length() b.length();}return a b;
}2.2 高精度加法实现
高精度加法的核心思路是模拟手工加法运算从低位到高位逐位相加并处理进位
// 高精度加法
std::string add(const std::string a, const std::string b) {// 处理符号if (isNegative(a) !isNegative(b)) {return subtract(b, getAbs(a));}if (!isNegative(a) isNegative(b)) {return subtract(a, getAbs(b));}if (isNegative(a) isNegative(b)) {return - add(getAbs(a), getAbs(b));}// 两个正数相加std::string result;int carry 0;int i a.size() - 1;int j b.size() - 1;while (i 0 || j 0 || carry 0) {int sum carry;if (i 0) sum a[i--] - 0;if (j 0) sum b[j--] - 0;result.push_back((sum % 10) 0);carry sum / 10;}return removeLeadingZeros(reverse(result));
}2.3 高精度减法实现
高精度减法比加法更复杂需要考虑借位和数字大小比较
// 高精度减法
std::string subtract(const std::string a, const std::string b) {// 处理符号if (isNegative(a) !isNegative(b)) {return - add(getAbs(a), b);}if (!isNegative(a) isNegative(b)) {return add(a, getAbs(b));}if (isNegative(a) isNegative(b)) {return subtract(getAbs(b), getAbs(a));}// 两个正数相减if (!absGreaterOrEqual(a, b)) {return - subtract(b, a);}std::string result;int borrow 0;int i a.size() - 1;int j b.size() - 1;while (i 0) {int diff (a[i] - 0) - borrow;if (j 0) diff - (b[j] - 0);if (diff 0) {diff 10;borrow 1;} else {borrow 0;}result.push_back(diff 0);i--;j--;}return removeLeadingZeros(reverse(result));
}2.4 高精度乘法实现
高精度乘法通常采用竖式乘法的思路时间复杂度为 O (n²)
// 高精度乘法
std::string multiply(const std::string a, const std::string b) {// 处理零的情况if (a 0 || b 0) {return 0;}// 处理符号bool isNegative (isNegative(a) !isNegative(b)) || (!isNegative(a) isNegative(b));std::string absA getAbs(a);std::string absB getAbs(b);// 结果数组长度为两数位数之和std::vectorint result(absA.size() absB.size(), 0);// 竖式乘法核心逻辑for (int i absA.size() - 1; i 0; i--) {for (int j absB.size() - 1; j 0; j--) {int product (absA[i] - 0) * (absB[j] - 0);int sum product result[i j 1];result[i j 1] sum % 10;result[i j] sum / 10;}}// 转换结果数组为字符串std::string resultStr;for (int num : result) {if (!(resultStr.empty() num 0)) {resultStr.push_back(num 0);}}return (isNegative ? - : ) resultStr;
}2.5 高精度除法实现
高精度除法是最复杂的运算这里采用试商法实现
// 高精度除法
std::string divide(const std::string a, const std::string b) {// 处理除数为零的情况if (b 0) {throw std::runtime_error(Division by zero);}// 处理零的情况if (a 0) {return 0;}// 处理符号bool isNegative (isNegative(a) !isNegative(b)) || (!isNegative(a) isNegative(b));std::string absA getAbs(a);std::string absB getAbs(b);// 处理被除数小于除数的情况if (!absGreaterOrEqual(absA, absB)) {return 0;}// 试商法核心逻辑std::string quotient;std::string remainder;for (char c : absA) {remainder c;remainder removeLeadingZeros(remainder);int count 0;while (absGreaterOrEqual(remainder, absB)) {remainder subtract(remainder, absB);count;}quotient std::to_string(count);}quotient removeLeadingZeros(quotient);return (isNegative ? - : ) quotient;
}// 高精度取模
std::string mod(const std::string a, const std::string b) {if (b 0) {throw std::runtime_error(Modulo by zero);}if (a 0) {return 0;}bool isNegative isNegative(a);std::string absA getAbs(a);std::string absB getAbs(b);if (!absGreaterOrEqual(absA, absB)) {return a;}std::string quotient divide(absA, absB);std::string product multiply(quotient, absB);std::string remainder subtract(absA, product);return (isNegative ? - : ) remainder;
}三、完整测试程序
下面是一个完整的测试程序展示如何使用上述高精度算法
// 测试程序
int main() {try {// 测试加法std::cout 加法测试: 12345 67890 add(12345, 67890) std::endl;// 测试减法std::cout 减法测试: 98765 - 12345 subtract(98765, 12345) std::endl;// 测试乘法std::cout 乘法测试: 1234 * 5678 multiply(1234, 5678) std::endl;// 测试除法std::cout 除法测试: 123456789 / 12345 divide(123456789, 12345) std::endl;// 测试取模std::cout 取模测试: 123456789 % 12345 mod(123456789, 12345) std::endl;// 测试负数运算std::cout 负数测试: std::endl;std::cout -123 456 add(-123, 456) std::endl;std::cout 123 - (-456) subtract(123, -456) std::endl;std::cout -123 * (-456) multiply(-123, -456) std::endl;std::cout -12345 / 67 divide(-12345, 67) std::endl;} catch (const std::exception e) {std::cerr 错误: e.what() std::endl;return 1;}return 0;
}四、总结
高精度算法是处理大数运算的基础其核心在于
将大数字拆分为小单元处理模拟手工计算过程进位、借位、试商等合理处理符号和边界情况
理解高精度算法不仅有助于解决实际问题还能加深对数字运算本质的理解。在密码学、科学计算等领域高精度算法更是不可或缺的基础工具。
