首页 > 编程语言 >c++高精度细剖

c++高精度细剖

时间：2024-08-22 09:53:04浏览次数：12  
标签：细剖 高精度 int c++ 算法 计算 sb sa

深入剖析C++中的高精度计算是一个广泛且深入的主题，它涵盖了多种技术和策略，用于处理超过标准整数或浮点数类型能表示范围的数值。在这里，我将提供一个概括性的框架，涵盖高精度计算的基本概念、常见方法、实现细节以及可能的应用场景，但请注意，由于篇幅限制，这里无法直接达到“十万字”的详细程度，但会尽量全面。

一、高精度计算概述

1.1 定义与需求

高精度计算是指能够处理超出标准数据类型（如int、long long、float、double等）范围或精度的数值运算。这在金融计算、科学模拟、密码学、大数分解等领域尤为重要。

1.2 挑战

  • 表示范围：标准数据类型有固定的表示范围，超出则会导致溢出。
  • 精度损失：浮点数运算存在精度损失，不适合高精度要求的应用。
  • 性能：高精度计算通常比标准数据类型运算慢，需要优化。

二、高精度数的表示

2.1 字符串表示

将数字以字符串形式存储，通过模拟手工计算过程（如加法、乘法等）来实现高精度运算。这种方法简单直观，但效率较低。

2.2 数组表示

使用数组（如vector<int>或int[]）的每一位存储数字的一个十进制位，这样可以方便地模拟手工计算过程，同时保持较高的效率。

三、高精度运算实现

3.1 加法

从最低位开始，逐位相加，并处理进位。

vector<int> add(vector<int>& num1, vector<int>& num2) {  
    vector<int> result;  
    int carry = 0;  
    int n1 = num1.size(), n2 = num2.size();  
    int i = 0;  
    while (i < n1 || i < n2 || carry) {  
        int sum = carry;  
        if (i < n1) sum += num1[n1 - 1 - i];  
        if (i < n2) sum += num2[n2 - 1 - i];  
        result.push_back(sum % 10);  
        carry = sum / 10;  
        i++;  
    }  
    reverse(result.begin(), result.end());  
    return result;  
}



3.2 减法

从最低位开始，逐位相减，并处理借位。

3.3 乘法

使用“列乘法”或“Karatsuba算法”等优化算法，减少乘法次数。

3.4 除法

模拟手工除法过程，从最高位开始，逐位试除。

四、性能优化

  • 使用更快的算法：如Karatsuba乘法、FFT乘法等。
  • 减少不必要的内存分配：通过预分配足够的空间来减少vector的扩容开销。
  • 并行计算：对于非常大的数，可以使用并行算法来加速计算。

五、应用场景

  • 大数运算：如计算大数的阶乘、幂运算等。
  • 密码学：RSA加密、大数分解等。
  • 科学计算：天文学、物理学中的高精度模拟。
  • 金融：高精度的金融计算，避免浮点数运算的精度问题。

六、结论

高精度计算在C++中是一个复杂但重要的领域，它要求开发者不仅要有扎实的编程基础，还要对算法和数据结构有深入的理解。通过合理的数据表示和高效的算法实现，可以使得高精度计算在满足精度要求的同时，尽可能地提高计算效率。由于篇幅限制，本文只能提供一个大致的框架和思路，具体实现细节和深入讨论还需要读者自行学习和探索。

七、具体实例与解决方法

7.1 高精度加法实例

实例描述：计算两个非常大的数（如超过long long范围）的和。

解决方法：

  • 数据表示：采用vector<int>表示每个数位，最低位在vector的开始位置。
  • 算法实现：使用上述的add函数，从最低位开始逐位相加，并处理进位。
  • 优化：考虑预先分配足够的空间给结果vector，以避免在运算过程中频繁扩容。

例题：
【题目描述】
求两个不超过200位的非负整数的和。

【输入】
有两行，每行是一个不超过200位的非负整数，可能有多余的前导0。

【输出】
一行，即相加后的结果。结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342。

【输入样例】

22222222222222222222 33333333333333333333


【输出样例】

55555555555555555555


代码实现

#include <iostream>
​
using namespace std;
const int N = 2e2 + 5;
char sa[N], sb[N];
int a[N], b[N], c[N];
void CharToInt(char sa[], int a[]) {
    for (int i = 1; i <= a[0]; i++) {
        a[i] = sa[a[0] - i] - '0';
    }
}
void GJD_Add(int a[], int b[], int c[]) {
    for (int i = 1; i <= c[0]; i++) {
        c[i] = a[i] + b[i] + c[i];
        c[i + 1] = c[i] / 10;
        c[i] = c[i] % 10;
    }
}
void Delete_frontZero(int c[]) {
    while (c[0] >= 2 && c[c[0]] == 0) {
        c[0]--;
    }
}
void Show(int c[]) {
    for (int i = c[0]; i >= 1; i--) {
        cout << c[i];
    }
}
int main() {
    cin >> sa >> sb;//用字符数组接收高精度数
    a[0] = strlen(sa);//a[0]表示高精度数sa的位数
    b[0] = strlen(sb);//b[0]表示高精度数sb的位数
    CharToInt(sa, a);//把字符数组sa逆序转化位整形数组
    CharToInt(sb, b);//把字符数组sb逆序转化位整形数组
    c[0] = max(a[0], b[0]) + 1;//c长度
    GJD_Add(a, b, c);//模拟高精度加法
    Delete_frontZero(c);//删除前导0
    Show(c);//输出
    return 0;
}

7.2 高精度减法实例

实例描述：计算两个大数的差，其中一个数可能比另一个数小，需要处理借位。

解决方法：

  • 数据表示：同样使用vector<int>。
  • 算法实现：从最低位开始逐位相减，如果当前位不够减，则向前一位借位。
  • 特殊情况处理：如果第一个数小于第二个数，则交换两个数并标记结果为负数（或保持为正数但表示为补码形式）。

例题：
【题目描述】
求两个大的正整数相减的差。

【输入】
共2行，第1行是被减数a，第2行是减数b(a > b)。每个大整数不超过200位，不会有多余的前导零。

【输出】
一行，即所求的差。

【输入样例】

9999999999999999999999990000000000000


【输出样例】

9999999999999999999999990000000000000

代码实现

​#include<bits/stdc++.h>
using namespace std;
const int N = 2e2 + 5;
char sa[N], sb[N];
int a[N], b[N], c[N];
void CharToInt(char sa[], int a[]) {
    for (int i = 1; i <= a[0]; i++) {
        a[i] = sa[a[0] - i] - '0';
    }
}
void GJD_reduce(int a[], int b[], int c[]) {
    for (int i = 1; i <= c[0]; i++) {
        if (a[i] < b[i]) {
            a[i + 1]--;//借1
            c[i] = a[i] - b[i] + 10;//当10
        }
        else
            c[i] = a[i] - b[i];
    }
}
void Delete_frontZero(int c[]) {
    while (c[0] >= 2 && c[c[0]] == 0) {
        c[0]--;
    }
}
void Show(int c[]) {
    for (int i = c[0]; i >= 1; i--) {
        cout << c[i];
    }
}
int main() {
    cin >> sa >> sb;
    a[0] = strlen(sa);
    b[0] = strlen(sb);
    CharToInt(sa, a);
    CharToInt(sb, b);
    c[0] = max(a[0], b[0]);
    GJD_reduce(a, b, c);
    Delete_frontZero(c);
    Show(c);
    return 0;
}

7.3 高精度乘法实例

实例描述：实现两个大数的乘法。

解决方法：

  • 列乘法：按位相乘，并将结果按位累加。
  • Karatsuba算法：将大数分为两部分，利用三次乘法（而非四次）来减少计算量。
  • FFT乘法：利用快速傅里叶变换（FFT）将数转换为频域，进行乘法运算后再转换回时域，适用于非常大的数。

算法实现：
 

#include <iostream>
​
using namespace std;
const int N = 2e2 + 5;
char sa[N], sb[N];
int a[N], b[N], c[N];
void CharToInt(char sa[], int a[]) {
    for (int i = 1; i <= a[0]; i++) {
        a[i] = sa[a[0] - i] - '0';
    }
}
void GJD_Multiply(int a[], int b[], int c[]) {
    for (int i = 1; i <= a[0]; i++) {
        for (int j = 1; j <= b[0]; j++) {
            c[i + j - 1] += a[i] * b[j];
            c[i + j] += c[i + j - 1] / 10;
            c[i + j - 1] = c[i + j - 1] % 10;
        }
    }
}
void Delete_frontZero(int c[]) {
    while (c[0] >= 2 && c[c[0]] == 0) {
        c[0]--;
    }
}
void Show(int c[]) {
    for (int i = c[0]; i >= 1; i--) {
        cout << c[i];
    }
}
int main() {
    cin >> sa >> sb;
    a[0] = strlen(sa);
    b[0] = strlen(sb);
    CharToInt(sa, a);
    CharToInt(sb, b);
    c[0] = a[0] + b[0];
    GJD_Multiply(a, b, c);
    Delete_frontZero(c);
    Show(c);
    return 0;
}

7.4 高精度除法实例

实例描述：实现大数的除法，包括商和余数的计算。

解决方法：

  • 模拟手工除法：从被除数的最高位开始，逐位尝试除以除数，并更新余数。
  • 优化：通过长除法减少比较次数，或使用更高效的算法如牛顿迭代法求倒数后进行乘法操作。

【题目描述】
输入一个大于0的大整数N，长度不超过100位，要求输出其除以13得到的商和余数。

【输入】
一个大于0的大整数，长度不超过100位。

【输出】
两行，分别为整数除法得到的商和余数。

【输入样例】

2132104848488485


【输出样例】

164008065268345 0


代码实现：
 

#include <iostream>
​
using namespace std;
const int N = 2e5 + 5;
char sa[N];
int a[N], c[N],lena,k;
int Chufa13(int a[],int c[]) {
    int x = 0;
    c[0] = a[0];
    for (int i = 1;i<=a[0];i++){
        c[i] = (x * 10 + a[i]) / 13;
        x = (x * 10 + a[i]) %13;
    }
    return x;
}
void Reverse(int c[]) {
    int i, j;
    for (i = 1, j = c[0]; j > i;j--,i++) {
        swap(c[i], c[j]);
    }
}
void DeleteZero(int c[]) {
    while (c[0] >= 1&&c[c[0]]==0) {
        c[0]--;
    }
}
int main() {
    int flag = 0;
    cin >> sa;
    a[0] = strlen(sa);
    for (int i = 1; i <= a[0]; i++) {
        a[i] = sa[i-1]-'0';
    }
    int yushu=Chufa13(a, c);
    Reverse(c);
    DeleteZero(c);
    for (int i = c[0]; i >= 1;i--) {
        cout << c[i];
    }
    cout << endl;
    cout << yushu;
    return 0;
}

7.5 实际应用案例

7.5.1 金融计算

案例描述：高精度计算在金融领域常用于处理大额交易、精确计算利息、汇率转换等。

解决方法：

  • 使用高精度库（如GMP, MPIR等）直接处理大数运算。
  • 自定义高精度算法，确保计算的准确性和效率。
7.5.2 密码学

案例描述：RSA加密、大数分解等算法需要处理非常大的数。

解决方法：

  • 利用高效的大数乘法算法（如Karatsuba、FFT乘法）。
  • 实现大数模幂运算的快速算法（如二进制指数算法）。
7.5.3 科学计算

案例描述：天文学、物理学中的高精度模拟需要处理极大的数值范围和精度。

解决方法：

  • 采用高精度的浮点数库（如MPFR）或自定义高精度小数表示。
  • 结合并行计算技术，利用多核处理器加速计算过程。

7.6 性能优化与测试

7.6.1 性能优化
  • 算法优化：选择或设计更高效的算法。
  • 内存管理：减少内存分配和释放的次数，优化数据结构的使用。
  • 并行计算：利用多线程或多进程技术并行处理大数运算。
7.6.2 测试
  • 单元测试：对各个高精度函数进行单元测试，确保功能正确。
  • 性能测试：使用大量测试用例测试算法的性能，寻找瓶颈并优化。
  • 压力测试：模拟极端情况，测试系统的稳定性和可靠性。

7.7 结论与展望

结论：高精度计算在C++中是一个重要且复杂的领域，其实现需要扎实的编程基础和深厚的算法知识。通过合理的数据表示和高效的算法实现，可以满足各种高精度计算的需求。

展望：随着计算机硬件的发展和多核处理器的普及，未来高精度计算将更加注重并行化和优化算法的设计。同时，随着新算法和技术的不断涌现，高精度计算的应用领域也将不断拓展。

标签：细剖,高精度,int,c++,算法,计算,sb,sa
From： https://blog.csdn.net/szm111213/article/details/141409777

相关文章

  • C++ wsl2 ubuntu 环境配置
    目前学习C++，配合Ubuntu进行开发，IDE使用Clion，这里记录一下环境准备WSL2C++一般是用在linux下，这里就用Ubuntu进行开发，考虑到window系统，这里准备用wsl2.虚拟化wsl2要系统支持虚拟化，一般在bios中进行处理，成功之后，任务管理器-->性能适用于Linux的Windows子系统wsl更新ws......
  • C++——STL——vector容器
    vector的头文件#include<vector>vector的声明与初始化vector<类型>变量=赋值;//整型vector<int>a={1,2,3,4};//浮点型 vector<double>b={1.1,2.2,3.2,4.4};//字符型 vector<char>c={'a','b','c'......
  • 「字符串」前缀函数|KMP匹配：规范化next数组 / LeetCode 28（C++）
    概述为什么大家总觉得KMP难？难的根本就不是这个算法本身。在互联网上你可以见到八十种KMP算法的next数组定义和模式串回滚策略，把一切都懂得特别混乱。很多时候初学者的难点根本不在于这个算法本身，而是它令人痛苦的百花齐放的定义。有的next数组从0下标开始，有的从1开始；有的表......
  • 引发C++程序内存泄漏的常见原因分析与排查方法总结
    目录1、概述2、内存泄漏与程序的位数3、调用哪些接口去动态申请内存？4、引发内存泄漏的常见原因总结4.1、通过malloc/new等动态申请的内存，在使用完后，没有调用free/delete去释放（也可能是调用了上面讲到的HeapAlloc或VirtualAlloc等API接口）4.2、函数调用者调用内部申请内存......
  • 掌握C++中的std::list：高效处理插入与删除的最佳选择
    在C++标准模板库（STL）中，std::list是一个非常重要的容器，属于序列式容器。与std::vector和std::deque不同，std::list是一个双向链表（doublylinkedlist），其设计更适合于频繁的插入和删除操作，而不是随机访问。本文将深入探讨std::list的实现原理、使用场景以及与其他容器的对比......
  • 昇腾 - AscendCL C++应用开发 线程安全的队列
    昇腾-AscendCLC++应用开发线程安全的队列flyfishC++mutex各种各样的互斥锁mutex、timed_mutex、recursive_mutex、shared_mutexC++线程间同步的条件变量std::condition_variable和std::condition_variable_anyC++提供的智能指针unique_ptr、shared_ptr、wea......
  • C++智能指针配合STL模板类
    代码 #include<unordered_map>#include<set>#include<memory>classResID{public:usingSP=std::shared_ptr<ResID>;ResID()=default;ResID(conststd::string&id,conststd::string&type):m_id(id......
  • C++实现web token加密生成验证
    代码 #include"jwt-cpp/traits/boost-json/traits.h"#include<boost/json/src.hpp>//Youmayrequirethisifyouarenotbuildingitelsewhere#include<iostream>#include<sstream>voidtestToken(){ usingsec=std::chrono::......
  • C++ 有向图拓扑排序算法
    代码 #include<algorithm>#include<cassert>#include<functional>#include<map>#include<memory>#include<queue>#include<set>#include<unordered_set>#include<vector>namespacejc{templa......
  • 昇腾 - AscendCL C++应用开发 目标检测中的非极大值抑制NMS和计算候选边界框之间的交
    昇腾-AscendCLC++应用开发目标检测中的非极大值抑制（NMS，Non-MaximumSuppression）涉及计算候选边界框之间的交并比（IOU，IntersectionoverUnion）flyfish结构体BBox:定义了一个边界框的数据结构，包含中心坐标、宽高、置信度分数、类别索引和输出索引。函数IOU:计算两个......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99