详解C/C++高精度算法的简单实现

目录
  • 前言
  • 一、基本原理
  • 二、辅助方法
    • 1、字符串转高精度
    • 2、整型转高精度
    • 3、比较
    • 4、打印
  • 三、算法实现
    • 1、加法
    • 2、减法
    • 3、乘法
    • 4、除法
  • 四、使用示例
    • 1、加法
    • 2、减法
    • 3、乘法
    • 4、除法
  • 总结

前言

由于上一章《C/C++ 高精度(加减乘除)算法实现》是基于工程项目考虑实现的,也做了一定的优化,实现过程较为复杂。不利于移植和使用,且比较难以理解,时间一长代码也容易忘记,所以重新编写了一个简化的版本,方便以后需要时拷贝使用。

一、基本原理

1、存储方式

采用数字记录高精度数字,数组的第一个元素存储数据长度,比如记录数字为1024示例如下:

2、计算方式

采用模拟立竖式计算,比如加法的计算流程,如下图所示1024+9000:

这里只给出加法的计算说明,其他的以此类推,减法与加法基本一致。乘法和除法略有不同,通过示例图表示也复杂,还不如通过代码去理解,本质的方法就是模拟笔算的立竖式计算。

二、辅助方法

1、字符串转高精度

长度记录在数组第一个元素中

/// <summary>
/// 通过字符串初始化
/// </summary>
/// <param name="a">[in]高精度数组</param>
/// <param name="value">[in]字符串首地址</param>
static void loadStr(int* a,const char* value)
{
    //记录长度
    a[0] = strlen(value);
    for (int i = 1; i <= a[0]; i++)
        a[i] = value[a[0] - i] - '0';
}

2、整型转高精度

/// <summary>
/// 通过无符号整型初始化
/// </summary>
/// <param name="a">[in]高精度数组</param>
/// <param name="value">[in]整型值</param>
static void loadInt(int* a, uint64_t value)
{
    for (size_t i = 1; i < 8096; i++)
    {
        a[i] = value % 10;
        value /= 10;
        if (!value)
        {
            //记录长度
            a[0] = i;
            return;
        }
    }
}

3、比较

/// <summary>
/// 比较两个高精度数的大小
/// </summary>
/// <param name="a">[in]第一个数</param>
/// <param name="b">[in]第二个数</param>
/// <returns>1是a>b,0是a==b,-1是a<b</returns>
static int compare(int* a, int* b)
{
    if (a[0] > b[0])return 1;
    if (a[0] < b[0])return -1;
    for (int i = a[0]; i > 0; i--)
        if (a[i] > b[i])return 1;
        else if (a[i] < b[i])return -1;
    return 0;
}

4、打印

/// <summary>
/// 打印输出结果
/// </summary>
static void print(int* a) {
    if (!a[0])
        printf("0");
    for (int i = a[0]; i > 0; i--)
        printf("%d", a[i]);
}

三、算法实现

原理就不做具体介绍了,四种计算的核心都是模拟立竖式计算。

1、加法

为了保证代码相对简单,当b长度较小时可能会做一些多余的计算,不影响结果。

/// <summary>
/// 加法(累加)
///结果会保存在a中
/// </summary>
/// <param name="a">[in]被加数</param>
/// <param name="b">[in]加数</param>
static    void acc(int* a, int* b)
{
    int len = a[0] > b[0] ? a[0] : b[0];
    memset(a + a[0] + 1, 0, (len - a[0] + 1) * sizeof(int));
    memset(b + b[0] + 1, 0, (len - b[0] + 1) * sizeof(int));
    for (int i = 1; i <= len; i++) {
        int temp = a[i] + b[i];
        a[i] = temp % 10;
        a[i + 1] += temp / 10;
    }
    if (a[len + 1])a[0]++;
}

2、减法

/// <summary>
/// 减法(累减)
///结果会保存在a中
/// </summary>
/// <param name="a">[in]被减数,被减数必须大于等于减数</param>
/// <param name="b">[in]减数</param>
static    void subc(int* a, int* b) {
    memset(b + b[0] + 1, 0, (a[0] - b[0]) * sizeof(int));
    for (int i = 1; i <= a[0]; i++)
    {
        int temp = a[i] - b[i];
        a[i] = temp;
        if (temp < 0)
        {
            //借位
            a[i + 1] -= 1;
            a[i] += 10;
        }
    }
    //记录长度
    for (int i = a[0]; i > 0; i--)
        if (a[i])
        {
            a[0] = i;
            return;
        }
    a[0] = 0;
}

3、乘法

/// <summary>
/// 乘法
/// </summary>
/// <param name="a">[in]被乘数</param>
/// <param name="b">[in]乘数</param>
/// <param name="c">[out]结果,数组长度必须大于等于aLen+bLen+1</param>
static    void mul(int* a, int* b, int c[]) {
    c[a[0] + b[0]] = 0;
    memset(c, 0, sizeof(int) * (a[0] + b[0] + 1));
    for (int i = 1; i <= a[0]; i++)
    {
        int j;
        int d = 0;
        //被乘数的一位去乘以乘数的每一位
        for (j = 1; j <= b[0]; j++)
        {
            int temp = a[i] * b[j] + c[j + i - 1] + d;
            c[j + i - 1] = temp % 10;
            d = temp / 10;
        }
        if (d)
        {
            c[j + i - 1] = d;
        }
    }
    //记录长度
    for (int i = a[0] + b[0]; i > 0; i--)
        if (c[i])
        {
            c[0] = i;
            return;
        }
}

4、除法

采用了升阶+减法实现

/// <summary>
/// 除法
/// 依赖减法subc
/// </summary>
/// <param name="a">[in]被除数,被除数必须大于除数</param>
/// <param name="b">[in]除数</param>
/// <param name="c">[out]商,数组长度大于等于aLen-bLen+1</param>
/// <param name="mod">[out]余数,数组长度大于等于aLen</param>>
/// <param name="temp">[in]临时缓冲区,由外部提供以提高性能,数组长度大于等于aLen-bLen+1</param>
static void divi(int* a, int* b, int* c, int* mod, int* temp) {
    //相差的阶数
    int digit = a[0] - b[0] + 1;
    memcpy(mod, a, (a[0] + 1) * sizeof(int));
    memset(c, 0, sizeof(int) * (digit + 1));
    memset(temp, 0, sizeof(int) * digit);
    while (digit)
    {
        //升阶
        memcpy(temp + digit, b + 1, sizeof(int) * b[0]);
        temp[0] = b[0] + digit - 1;
        //减法
        while (compare(mod, temp) != -1)
        {
            subc(mod, temp);
            c[digit]++;
        }
        digit--;
    }
    //记录长度
    for (int i = a[0] - b[0] + 1; i > 0; i--)
        if (c[i])
        {
            c[0] = i;
            return;
        }
}

四、使用示例

1、加法

计算累加

int main() {
    int64_t n;
    int num[1024];
    int num2[1024];
    std::cin >> n;
    loadInt(num, 0);
    for (int64_t i = 1; i <= n; i++)
    {
        loadInt(num2, i);
        acc(num, num2);
    }
    print(num);
    return 0;
}

结果:

2、减法

两个任意n位数的减法,数字1大于数字2。

int main()
{
    int a1[8096], a2[8096];
    std::string s1, s2;
    std::cin >> s1 >> s2;
    loadStr(a1, s1.c_str());
    loadStr(a2, s2.c_str());
    subc(a1, a2);
    print(a1);
    return 0;
}

结果:

#数字1
752425289999999999999652142141414141414146666676667677682324000001302461646520
#数字2
587891851201874512000000000154515100202121555555555555555555555545477910232111
#计算结果
164533438798125487999652141986899041212025111121112122126768444455824551414409

3、乘法

计算阶乘

int main() {
    int64_t n;
    int num[8192];
    int num2[8192];
    int num3[8192];
    int* p1 = num;
    int* p2 = num3;
    std::cin >> n;
    loadInt(num, 1);
    for (int64_t i = 1; i <= n; i++)
    {
        loadInt(num2, i);
        mul(p1, num2, p2);
        int* temp = p1;
        p1 = p2;
        p2 = temp;
    }
    print(p1);
    return 0;
}

结果:

#阶乘数
1000
#计算结果
402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

4、除法

给定两个非负整数A,B,请你计算 A / B的商和余数。

int main()
{
    int a1[8096], a2[8096], c[8096], mod[8096], temp[8096];
    std::string s1, s2;
    std::cin >> s1 >> s2;
    loadStr(a1, s1.c_str());
    loadStr(a2, s2.c_str());
    divi(a1, a2, c, mod, temp);
    print(c);
    std::cout << std::endl;
    print(mod);
    return 0;
}

结果:

#被除数
12458848948151231366666666666666665454545123156415641561231561213648
#除数
88484851521548496564154848456486789
#商
140802055198308817458997123299946
#余数
25178368711335236611547594127800254

总结

以上就是今天要讲的内容,本文提供的是较为简化的实现,且每个方法基本是独立的,可单独拿来使用,用法也比较简单,由于采用数组第一个元素存储长度,接口就变得很简洁,使用起来也方便了很多。

到此这篇关于详解C/C++高精度算法的简单实现的文章就介绍到这了,更多相关C/C++高精度算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C/C++高精度算法的实现

    做ACM题的时候,经常遇到大数的加减乘除,乘幂,阶乘的计算,这时给定的数据类型往往不够表示最后结果,这时就需要用到高精度算法.高精度算法的本质是把大数拆成若干固定长度的块,然后对每一块进行相应的运算.这里以考虑4位数字为一块为例,且输入的大数均为正整数(也可以考虑其他位,但要注意在每一块进行相应运算时不能超出数据类型的数值范围:有负整数的话读入时判断一下正负号在决定运算). 1. 高精度加法 以3479957928375817 + 897259321544245为例: 3479 9579 283

  • 使用C++的string实现高精度加法运算的实例代码

    对于超大数字的运算,用long long int仍然不能解决,这时候就需要考虑通过模拟运算和数组存储来实现高精度运算. 本文讨论借助C++的string来实现高精度的运算. 首先输入的量直接存储为string,设为s1和s2. 接下来设计一个反转函数,用于把整个字符串反转(为了方便后续计算). string reverseStr(string input){ string output = ""; for(int i = 0; i < input.length(); i++){

  • C/C++高精度运算(大整数运算)详细讲解

    目录 前言 什么是大整数 大整数的表示 大整数的运算 1.高精度加法 2.高精度减法 3.高精度乘以低精度 4.高精度除以低精度 大整数的表示 补充:使用示例 总结 前言 高精度的运算在算法题尤为常见,在处理一些大型数据的项目中也需要用到.虽然Boost库中有处理高精度问题的模板,但是标准库中并没有.为了方便学习,本文提供了高精度运算的模板,供大家参考. 什么是大整数 众所周知,最大的整型long long的范围是[-9223372036854775808~9223372036854775807

  • c++实现高精度加法

    最近遇到一个c++实现高精度加法的问题,高精度问题往往十复杂但发现其中的规律后发现并没有那么复杂,这里我实现了一个整数的高精度加法,主要需要注意以下几点: 1:将所需输入的数据以字符数组的形式输入,建立字符数组,建立相应的整数数组,然后一一映射,以此来实现数据的输入,需要注意的是,当实现字符向数字映射时,应该减去相应的ASCII偏移值,即48. 2:为了模拟我们在纸上手算的进位模拟运算,我们将字符数组反向填入整数数组,上图的后几行代码实现了这个操作. 3:实现进位加法,这是整个代码的核心部分,需

  • C++高精度算法的使用场景详解

    目录 描述 1. 高精度加法 1. 思路 2. 代码 2. 高精度减法 1. 思路 2. 代码 3. 如果出现被减数的位数小于减数时呢 描述 如果要计算的数超过了long long怎么解决? —>使用高精度加减乘除,简单理解就是 很大的数进行加减乘除. 1. 高精度加法 1. 思路 创建对应的数组变量及其他变量 输入字符串 将读入的数据转化为整数类型,并逆序(反转)存储到数组中 将两个数组做累加(注意进位) 判断最高位是否为0,大于0代表进位了,则让长度加1 倒序输出 2. 代码 #includ

  • C/C++高精度(加减乘除)算法的实现

    目录 前言 一.必要的参数 二.辅助函数 三.实现加减乘除 1.加法 2.减法 3.乘法 4.除法 四.使用例子 1.加法例子 2.减法例子 3.乘法例子 4.除法例子 前言 C/C++基本类型做算术运算时长度有限,但也基本满足大部分场景的使用,有时需要计算大长度数据就有点无能为力了,比如1000的阶乘结果就有2000多位,用基本类型是无法计算的. 高精度的算法,一般的方式是用一个很长的数组去记录数据,数组的每一位记录固定位数的数字,记录顺序是低位到高位.计算方式则通常采用模拟立竖式计算.计算方

  • c++加法高精度算法的简单实现

    c++高精度算法,对于新手来说还是一大挑战,只要克服它,你就开启了编程的新篇章,算法. 我发的这个代码并不是很好,占用内存很多而且运行时间很长(不超过1秒),但是很好理解,很适合新手 高精算法的本质就是把数组编程字符串,然后将字符串像竖式一样加起来: a+b高精度算法 #include <iostream> #include <cmath> #include <cstring> using namespace std; int main() { char a[10001

  • 详解C/C++高精度算法的简单实现

    目录 前言 一.基本原理 二.辅助方法 1.字符串转高精度 2.整型转高精度 3.比较 4.打印 三.算法实现 1.加法 2.减法 3.乘法 4.除法 四.使用示例 1.加法 2.减法 3.乘法 4.除法 总结 前言 由于上一章<C/C++ 高精度(加减乘除)算法实现>是基于工程项目考虑实现的,也做了一定的优化,实现过程较为复杂.不利于移植和使用,且比较难以理解,时间一长代码也容易忘记,所以重新编写了一个简化的版本,方便以后需要时拷贝使用. 一.基本原理 1.存储方式 采用数字记录高精度数字,

  • 详解python 支持向量机(SVM)算法

    相比于逻辑回归,在很多情况下,SVM算法能够对数据计算从而产生更好的精度.而传统的SVM只能适用于二分类操作,不过却可以通过核技巧(核函数),使得SVM可以应用于多分类的任务中. 本篇文章只是介绍SVM的原理以及核技巧究竟是怎么一回事,最后会介绍sklearn svm各个参数作用和一个demo实战的内容,尽量通俗易懂.至于公式推导方面,网上关于这方面的文章太多了,这里就不多进行展开了~ 1.SVM简介 支持向量机,能在N维平面中,找到最明显得对数据进行分类的一个超平面!看下面这幅图: 如上图中,

  • 详解Java实现分治算法

    目录 一.前言 二.分治算法介绍 三.分治算法经典问题 3.1.二分搜索 3.2.快速排序 3.3.归并排序(逆序数) 3.4.最大子序列和 3.5.最近点对 四.结语 一.前言 在学习分治算法之前,问你一个问题,相信大家小时候都有存钱罐的经历,父母亲人如果给钱都会往自己的宝藏中存钱,我们每隔一段时间都会清点清点钱.但是一堆钱让你处理起来你可能觉得很复杂,因为数据相对于大脑有点庞大了,并且很容易算错,你可能会将它先分成几个小份算,然后再叠加起来计算总和就获得这堆钱的总数了 当然如果你觉得各个部分

  • 详解非极大值抑制算法之Python实现

    一.概述 这里不讨论通用的NMS算法(参考论文<Efficient Non-Maximum Suppression>对1维和2维数据的NMS实现),而是用于目标检测中提取分数最高的窗口的.例如在行人检测中,滑动窗口经提取特征,经分类器分类识别后,每个窗口都会得到一个分数.但是滑动窗口会导致很多窗口与其他窗口存在包含或者大部分交叉的情况.这时就需要用到NMS来选取那些邻域里分数最高(是行人的概率最大),并且抑制那些分数低的窗口. NMS在计算机视觉领域有着非常重要的应用,如视频目标跟踪.数据挖掘

  • 详解Python数据结构与算法中的顺序表

    目录 0. 学习目标 1. 线性表的顺序存储结构 1.1 顺序表基本概念 1.2 顺序表的优缺点 1.3 动态顺序表 2. 顺序表的实现 2.1 顺序表的初始化 2.2 获取顺序表长度 2.3 读取指定位置元素 2.4 查找指定元素 2.5 在指定位置插入新元素 2.6 删除指定位置元素 2.7 其它一些有用的操作 3. 顺序表应用 3.1 顺序表应用示例 3.2 利用顺序表基本操作实现复杂操作 0. 学习目标 线性表在计算机中的表示可以采用多种方法,采用不同存储方法的线性表也有着不同的名称和特

  • 详解基于django实现的webssh简单例子

    本文介绍了详解基于django实现的webssh简单例子,分享给大家,具体如下: 说明 新建一个 django 程序,本文为 chain. 以下仅为简单例子,实际应用 可根据自己平台情况 进行修改. 打开首页后,需要输入1,后台去登录主机,然后返回登录结果. 正常项目 可以post 主机和登录账户,进行权限判断,然后去后台读取账户密码,进行登录. djang后台 需要安装以下模块 安装后会有一个版本号报错,不影响 channels==2.0.2 channels-redis==2.1.0 amq

  • 详解小白之KMP算法及python实现

    在看子串匹配问题的时候,书上的关于KMP的算法的介绍总是理解不了.看了一遍代码总是很快的忘掉,后来决定好好分解一下KMP算法,算是给自己加深印象. 在将KMP字串匹配问题的时候,我们先来回顾一下字串匹配的暴力解法: 假设字符串str为: "abcgbabcdh",  字串substr为: "abcd" 从第一个字符开始比较,显然两个字符串的第一个字符相等('a'=='a'),然后比较第二个字符也相等('b'=='b'),继续下去,我们发现第4个字符不相等了('g'!

  • 详解vue3.0 diff算法的使用(超详细)

    前言:随之vue3.0beta版本的发布,vue3.0正式版本相信不久就会与我们相遇.尤玉溪在直播中也说了vue3.0的新特性typescript强烈支持,proxy响应式原理,重新虚拟dom,优化diff算法性能提升等等.小编在这里仔细研究了vue3.0beta版本diff算法的源码,并希望把其中的细节和奥妙和大家一起分享. 首先我们来思考一些大中厂面试中,很容易问到的问题: 1 什么时候用到diff算法,diff算法作用域在哪里? 2 diff算法是怎么运作的,到底有什么作用? 3 在v-f

  • 详解Visual Studio中Git的简单使用

    写程序必然需要版本控制,哪怕是个人项目也是必须的,VS2015开始默认提供了对Git的支持.考虑到现在Git很火,作为微软系的程序员也不得不学一点防身,以免被开源世界的家伙们嘲笑,但是我相信用惯了SVN和TFS的童鞋们,需要一点勇气去学习一些新东西,特别是Git已经形成潮流,并且极大的推动了开源代码的交流学习.再说只要10分钟就能学会--基本的使用-- 首先要区分下Git和GitHub,前者是指一种版本控制软件,各个大厂可以有自己的具体实现.后者其实是指GitHub这个网站,它使用Git来提供代

随机推荐