| C/C++ 高精度（加减乘除）算法二进制优化 | 您所在的位置：网站首页 › 朴朴配送员长期兼职 › C/C++ 高精度（加减乘除）算法二进制优化 |
C/C++ 高精度（加减乘除）算法二进制优化
|
高级精度算法系列
第一章 简单实现 第二章 压位优化 第三章 二进制优化(本章) 文章目录 高级精度算法系列前言一、基本原理1、存储方式2、计算方式 二、关键实现1、整型转高精度数组（二进制）2、字符串转高精度数组（二进制）3、高精度数组（二进制）转字符串 三、完整代码四、性能对比总结 前言上一章《C/C++ 高精度（加减乘除）算法压位优化》实现了优化的高精度计算，采用int32的整型数组每个元素可以储存9个10进制数字，想要再进一步优化计算速度，可以改变数据存储方式，采用二进制存储数字。依然采用int32数组其元素通过二进制来存储数字，这样做不仅运算效率高，而且空间利用率也达到了最高。 一、基本原理 1、存储方式存储二进制顺序由低到高位存储 计算方式与10进制存储计算方式基本一致，下面给出int8的计算方式，int16、int32以此类推本质是一样的。 通过位操作既可以实现(元素类型int32为例)： /// /// 通过无符号整型初始化 /// /// [in]高精度数组 /// [in]整型值 static void loadInt(int* a, uint64_t value) { a[1] = (uint32_t)value; a[2] = value >> (sizeof(int) * 8); a[0] = a[2] ? 2 : 1; } 2、字符串转高精度数组（二进制）在这里提供一种方法，此方法需要先实现高精度加以及乘。 （1）初始化高精度数组值为0 （2）逐个获取字符串中的数字 （3）高精度数组乘等于10 （4）获取的数字与高精度数组相加（整型转高精度数组参考上一节） （5）字符串未读取完回到（2） 3、高精度数组（二进制）转字符串这里提供一种方法，需要上一章的实现作为辅助《C/C++ 高精度（加减乘除）算法压位优化》 （1）初始化压9位高进度数组值为0 （2）逐个获取高精度数组（二进制）的元素 （3）压9位高进度数组乘等于2^32（二进制数组元素类型int32为例） （4）获取的元素与压9位高进度数组相加 （5）元素未读取完回到（2） （6）压9位高进度数组转字符串 三、完整代码因为接口以及使用方法与第一章《C/C++ 高精度（加减乘除）算法简单实现》是完全一致的，所以这里只提供完整代码，使用示例请参考第一章。 基于int32数组二进制存储实现的高精度算法： https://download.csdn.net/download/u013113678/87720242 四、性能对比测试平台：Windows 11 测试设备：i7 8750h 测试方式：测试5次取均值 表1、测试用例 测试用例描述1整型范围数字计算500000次2长数字与整型范围数字计算500000次3长数字与长数字计算500000次基于上述用例编写程序进行测试，测试结果如下表 表2、测试结果 计算测试用例压9位优化（上一章）耗时二进制优化int32（本章）耗时加法测试用例10.002620s0.0024862s加法测试用例20.005711s0.0034712s加法测试用例30.005384s0.003857s累加测试用例10.002536s0.0027246s累加测试用例20.002592s0.0029876s累加测试用例30.006474s0.0043758s减法测试用例10.002078s0.0022704s减法测试用例20.004939s0.0032914s减法测试用例30.004929s0.0041246s累减测试用例10.002034s0.0020808s累减测试用例20.001942s0.0023542s累减测试用例30.004282s0.0044144s乘法测试用例10.004751s0.0038996s乘法测试用例20.028358s0.0117986s乘法测试用例30.064259s0.0185958s累乘测试用例1 只计算1000次0.000137s0.000062s累乘测试用例2 只计算1000次0.000187s0.0000816s累乘测试用例3 只计算1000次0.081988s0.0292832s除法测试用例10.024763s0.0196498s除法测试用例20.516090s0.3556564s除法测试用例30.073812s0.1716874s累除测试用例1 只计算1000次0.035722s0.0009416s累除测试用例2 只计算1000次0.060936s0.0131722s累除测试用例3 只计算500次25.126072s2.6210544s将上表数据进行分类相同类型取均值计算出提升速度如下图所示，仅作参考。 图1、速度提升
以上就是今天要讲的内容，二进制存储优化在对比压9位优化速度还有提升，而且存储方式与整型一样，很好的利用了空间。相比较与压9位算法，二进制算法对于乘法和除法的提升较大，尤其是长数据运算的提升更为明显。本章算法的二进制转换方法实现参考了c# 的BigInt，总的来说，这是一个性能比较好的高精度算法，比较适用于项目开发。 |
【本文地址】