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

c++高精度细剖

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

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

一、高精度计算概述

1.1 定义与需求

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

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:计算两个......