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

目录
  • 前言
  • 一、必要的参数
  • 二、辅助函数
  • 三、实现加减乘除
    • 1、加法
    • 2、减法
    • 3、乘法
    • 4、除法
  • 四、使用例子
    • 1、加法例子
    • 2、减法例子
    • 3、乘法例子
    • 4、除法例子

前言

C/C++基本类型做算术运算时长度有限,但也基本满足大部分场景的使用,有时需要计算大长度数据就有点无能为力了,比如1000的阶乘结果就有2000多位,用基本类型是无法计算的。

高精度的算法,一般的方式是用一个很长的数组去记录数据,数组的每一位记录固定位数的数字,记录顺序是低位到高位。计算方式则通常采用模拟立竖式计算。计算方式有一些优化方法,比如FFT快速傅里叶变换优化乘法,牛顿迭代优化除法。

本方法采用的,是上述的一般方式,用数组从低到高位记录数据,计算方式采用模拟立竖式计算。

一、必要的参数

1、计算位数

需要设定数组每个元素记录的位数即计算的进制(十进制、百进制、千进制)。计算位数越大,计算性能越好,在32/64位程序中,位数的范围可以是[1,9]。

2、计算进制

与计算位数直接对应,比如1位等于10进制,2位等于百进制。

3、数组类型

根据计算位数定义能装载数据的整型,尽量不浪费空间又不溢出,比如2位以内可以用int8,4位可以用int16等。

代码实现如下:

#include<stdint.h>
#include<stdio.h>
//计算位数,范围[1,9]
#define NUM_DIGIT 9
//数组类型
#if NUM_DIGIT<=0
    static_assert(1, "NUM_DIGIT must > 0 and <=9");
#elif NUM_DIGIT <=2
#define _NUM_T int8_t
#elif NUM_DIGIT <=4
#define _NUM_T int16_t
#elif NUM_DIGIT <=9
//NUM_DIGIT在[5,9]时用int32就可以装载数据,但是实测发现用int32在32位程序中,对除法性能有影响,用int64反而正常,这是比较奇怪的现象。
#define _NUM_T int64_t
#else
    static_assert(1, "NUM_DIGIT must > 0 and <=9");
#endif
//计算进制
    static const size_t _hex = NUM_DIGIT == 1 ? 10 : NUM_DIGIT == 2 ? 100 : NUM_DIGIT == 3 ? 1000 : NUM_DIGIT == 4 ? 10000 : NUM_DIGIT == 5 ? 100000 : NUM_DIGIT == 6 ? 1000000 : NUM_DIGIT == 7 ? 10000000 : NUM_DIGIT == 8 ? 100000000 : NUM_DIGIT == 9 ? 1000000000 : -1;
#define _MIN_NUM_SIZE 30/NUM_DIGIT

上述代码只要设置NUM_DIGIT(计算位数)就可以,其他值(计算进制、数组类型)都会自动生成。

二、辅助函数

1、初始化函数

由整型、字符串初始化高精度数组的方法。

2、比较函数

比较两个高精度数的大小等于。

3、输出函数

将高精度数组打印输出。

代码实现如下:

    /// <summary>
    /// 通过字符串初始化
    /// </summary>
    /// <param name="a">[in]高精度数组</param>
    /// <param name="value">[in]字符串首地址</param>
    /// <param name="len">[in]字符串长度</param>
    /// <returns>数据长度</returns>
    static size_t initByStr(_NUM_T* a, const char* value, size_t len)
    {
        size_t  shift = 10;
        size_t i, j, k = 0, n;
        n = len / NUM_DIGIT;
        for (i = 0; i < n; i++)
        {
            a[i] = (value[len - k - 1] - '0');
            for (j = 1; j < NUM_DIGIT; j++)
            {
                a[i] += (value[len - k - j - 1] - '0') * shift;
                shift *= 10;
            }
            shift = 10;
            k += NUM_DIGIT;
        }
        if (n = len - n * NUM_DIGIT)
        {
            a[i] = (value[len - k - 1] - '0');
            for (j = 1; j < n; j++)
            {
                a[i] += (value[len - k - j - 1] - '0') * shift;
                shift *= 10;
            }
            i++;
        }
        return i;
    }
    /// <summary>
    /// 通过无符号32整型初始化
    /// </summary>
    /// <param name="a">[in]高精度数组</param>
    /// <param name="value">[in]整型值</param>
    /// <returns>数据长度</returns>
    static size_t initByInt32(_NUM_T* a, uint32_t value)
    {
        size_t i;
        for (i = 0; i < 8096; i++)
        {
            a[i] = value % _hex;
            value /= _hex;
            if (!value)
            {
                i++;
                break;
            }
        }
        return i;
    }
    /// <summary>
    /// 通过无符号64整型初始化
    /// </summary>
    /// <param name="a">[in]高精度数组</param>
    /// <param name="value">[in]整型值</param>
    /// <returns>数据长度</returns>
    static size_t initByInt64(_NUM_T* a, uint64_t value)
    {
        size_t i;
        for (i = 0; i < 8096; i++)
        {
            a[i] = value % _hex;
            value /= _hex;
            if (!value)
            {
                i++;
                break;
            }
        }
        return i;
    }
    /// <summary>
    /// 比较两个高精度数的大小
    /// </summary>
    /// <param name="a">[in]第一个数</param>
    /// <param name="aLen">[in]第一个数的长度</param>
    /// <param name="b">[in]第二个数</param>
    /// <param name="bLen">[in]第二个数的长度</param>
    /// <returns>1是a>b,0是a==b,-1是a<b</returns>
    static int compare(const _NUM_T* a, size_t aLen, const  _NUM_T* b, size_t bLen)
    {
        if (aLen > bLen)
        {
            return 1;
        }
        else if (aLen < bLen)
        {
            return -1;
        }
        else {
            for (int i = aLen - 1; i > -1; i--)
            {
                if (a[i] > b[i])
                {
                    return 1;
                }
                else if (a[i] < b[i])
                {
                    return -1;
                }
            }
        }
        return 0;
    }
    /// <summary>
    /// 打印输出结果
    /// </summary>
    static void print(const _NUM_T* a, size_t aLen) {
        int i = aLen - 1, j = 0, n = _hex;
        char format[32];
        sprintf(format, "%%0%dd", NUM_DIGIT);
        printf("%d", a[i--]);
        for (; i > -1; i--)
            printf(format, a[i]);
    }

三、实现加减乘除

1、加法

由于数组存储数据的顺序是由低位到高位的,所以只需要两个数从数组0位开始相加,结果除以计算位数,余数保存在第一个数数组当前位,商累加到第一个数数组的下一位,然后下标加1重复前面的计算,直到全部元素计算完。

代码实现如下:

    /// <summary>
    /// 加法(累加)
    ///结果会保存在a中
    /// </summary>
    /// <param name="a">[in]被加数</param>
    /// <param name="aLen">[in]被加数长度</param>
    /// <param name="b">[in]加数</param>
    /// <param name="bLen">[in]加数长度</param>
    /// <returns>结果长度</returns>
    static    size_t acc(_NUM_T* a, size_t aLen, const _NUM_T* b, size_t bLen)
    {
        size_t i, n = bLen;
        const size_t max = _hex - 1;
        if (aLen < bLen)
        {
            memset(a + aLen, 0, (bLen - aLen + 1) * sizeof(_NUM_T));
        }
        else {
            a[aLen] = 0;
        }
        for (i = 0; i < bLen; i++) {
            uint64_t temp = (uint64_t)a[i] + (uint64_t)b[i];
            a[i] = temp % _hex;
            a[i + 1] += temp / _hex;
        }
        for (; i < aLen; i++) {
            uint64_t temp = a[i];
            if (temp <= max)
                break;
            a[i] = temp % _hex;
            a[i + 1] += temp / _hex;
        }
        n = aLen > bLen ? aLen : bLen;
        if (a[n])
            return n + 1;
        return n;
    }

2、减法

减法的原理和加法是类似的,两个数从数组0位开始相减,结果大于等于0直接保存到第一个数数组当前位,否则结果小于零结果+计算进制保存到第一个数数组当前位,同时下一位减等于1,然后下标加1重复前面的计算,直到全部元素计算完。

代码实现如下:

/// <summary>
    /// 减法(累减)
    ///结果会保存在a中
    /// </summary>
    /// <param name="a">[in]被减数,被减数必须大于等于减数</param>
    /// <param name="aLen">[in]被减数长度</param>
    /// <param name="b">[in]减数</param>
    /// <param name="bLen">[in]减数长度</param>
    /// <returns>结果长度</returns>
    static    size_t subc(_NUM_T* a, size_t aLen, const _NUM_T* b, size_t bLen) {
        size_t  m, n, i;
        if (aLen < bLen)
        {
            m = bLen;
            n = aLen;
        }
        else {
            n = bLen;
            m = aLen;
        }
        for (i = 0; i < n; i++)
        {
            int64_t temp = (int64_t)a[i] - (int64_t)b[i];
            a[i] = temp;
            if (temp < 0)
            {
                a[i + 1] -= 1;
                a[i] += _hex;
            }
        }
        for (; i < m; i++)
        {
            _NUM_T temp = a[i];
            if (temp < 0)
            {
                a[i + 1] -= 1;
                a[i] += _hex;
            }
            else
            {
                break;
            }
        }
        for (size_t i = aLen - 1; i != SIZE_MAX; i--)
            if (a[i])
                return i + 1;
        return 1;
    }

3、乘法

依然是参考立竖式计算方法,两层循环,遍历一个数的元素去乘以另一个数的每个元素,结果记录到新的数组中。

代码实现如下:

/// <summary>
    /// 乘法
    /// </summary>
    /// <param name="a">[in]被乘数</param>
    /// <param name="aLen">[in]被乘数长度</param>
    /// <param name="b">[in]乘数</param>
    /// <param name="bLen">[in]乘数长度</param>
    /// <param name="c">[out]结果,数组长度必须大于等于aLen+bLen+1,且全部元素为0</param>
    /// <returns>结果长度</returns>
    static    size_t multi(const _NUM_T* a, size_t aLen, const  _NUM_T* b, size_t bLen, _NUM_T c[]) {
        _NUM_T  d;
        size_t j;
        c[aLen + bLen] = 0;
        for (size_t i = 0; i < aLen; i++)
        {
            d = 0;
            for (j = 0; j < bLen; j++)
            {
                uint64_t temp = (uint64_t)a[i] * (uint64_t)b[j] + c[j + i] + d;
                d = temp / _hex;
                c[j + i] = temp % _hex;
            }
            if (d)
            {
                c[j + i] = d;
            }
        }
        for (size_t k = aLen + bLen; k != SIZE_MAX; k--)
            if (c[k])
                return k + 1;
        return 1;
    }

4、除法

基本的除法直接利用减法就可以实现,本方法使用的是模拟立竖式计算的方式,将移动除数使其与被除数高位对其,乘以一定倍数让除数与被除数值接近再进行减法运算。

代码实现如下:

/// <summary>
    /// 除法
    /// </summary>
    /// <param name="a">[in]被除数,被除数必须大于除数。小于商为0、余数为除数,等于商为1、余数为0,不需要在函数内实现,在外部通过compare就可以做到。</param>
    /// <param name="aLen">[in]被除数长度</param>
    /// <param name="b">[in]除数</param>
    /// <param name="bLen">[in]除数长度</param>
    /// <param name="c">[out]商,数组长度大于等于aLen,且全部元素为0</param>
    /// <param name="mod">[out]余数,数组长度大于等于aLen</param>
    /// <param name="modLen">[out]余数长度</param>
    /// <param name="temp">[in]临时缓冲区,由外部提供以提高性能,数组长度大于等于aLen+bLen+1</param>
    /// <returns>商长度</returns>
        static    size_t divide(const _NUM_T* a, size_t aLen, const  _NUM_T* b, size_t bLen, _NUM_T* c, _NUM_T* mod, size_t* modLen, _NUM_T* temp) {
        intptr_t  n, l;
        int equal;
        memcpy(mod, a, (aLen) * sizeof(_NUM_T));
        n = aLen - bLen;
        l = aLen;
        while (n > -1)
        {
            equal = compare(mod + n, l - n, b, bLen);
            if (equal == -1)
            {
                n--;
                if (!mod[l - 1])
                    l--;
                continue;
            }
            if (equal == 0)
            {
                c[n]++;
                n -= bLen;
                l -= bLen;
                continue;
            }
            uint64_t x;
            if ((l - n) > bLen)
            {
                x = ((mod[l - 1]) * _hex) / ((uint64_t)b[bLen - 1] + 1);
                if (x == 0)
                {
                    x = (mod[l - 2]) / ((uint64_t)b[bLen - 1] + 1);
                }
            }
            else
            {
                x = (mod[l - 1]) / ((uint64_t)b[bLen - 1] + 1);
            }
            if (x == 0)
                x = 1;
            c[n] += x;
            if (x == 1)
            {
                l = n + subc(mod + n, l - n, b, bLen);
            }
            else
            {
                _NUM_T num[_MIN_NUM_SIZE];
                size_t len = initByInt32(num, x);
                memset(temp, 0, (aLen + bLen + 1) * sizeof(_NUM_T));
                len = multi(b, bLen, num, len, temp);
                l = n + subc(mod + n, l - n, temp, len);
            }
        }
        intptr_t i = l - 1;
        for (; i > -1; i--)
            if (mod[i])
                break;
        if (i == -1)
        {
            mod[0] = 0;
            *modLen = 1;
        }
        else
        {
            *modLen = i + 1;
        }
        if (c[aLen - bLen] != 0)
            return aLen - bLen + 1;
        else
            return aLen - bLen;
    }

四、使用例子

1、加法例子

求 n 累加和(ja)。用高精度方法,求 s=1+2+3+……+n 的精确值(n 以一般整数输入)。

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

2、减法例子

两个任意十一位数的减法;(小于二十位)

int main()
{
    _NUM_T a1[8096], a2[8096];
    std::string s1, s2;
    std::cin >> s1 >> s2;
    size_t len1,len2;
    len1 =initByStr(a1, s1.c_str(), s1.size());
    len2 = initByStr(a2, s2.c_str(), s2.size());
    len1 =subc(a1, len1, a2, len2);
    print(a1,len1);
    return 0;
}

3、乘法例子

求 N!的值(ni)。用高精度方法,求 N!的精确值(N 以一般整数输入)。

int main(){
    int64_t n;
    size_t len, len2;
    _NUM_T num[8096];
    _NUM_T num2[8096];
    _NUM_T num3[8096];
    _NUM_T* p1 = num;
    _NUM_T* p2 = num3;
    std::cin >> n;
    len = initByInt32(num,1);
    for (int64_t i = 1; i <= n; i++)
    {
        len2 = initByInt64(num2, i);
        memset(p2, 0, 8096* sizeof(_NUM_T));
        len = multi(p1, len, num2, len2, p2);
        _NUM_T* temp = p1;
        p1 = p2;
        p2 = temp;
    }
    print(p1, len);
    return 0;
}

4、除法例子

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

int main()
{
    _NUM_T a1[8096], a2[8096],c[8096],mod[8096], temp[8096];
    std::string s1, s2;
    std::cin >> s1 >> s2;
    size_t len1,len2,ml;
    len1 =initByStr(a1, s1.c_str(), s1.size());
    len2 = initByStr(a2, s2.c_str(), s2.size());
    memset(c, 0, 8096 * sizeof(_NUM_T));
    len1 =divide(a1, len1, a2, len2,c, mod,&ml, temp);
    print(c,len1);
    std::cout<< std::endl ;
    print(mod, ml);
    return 0;
}

以上就是C/C++高精度(加减乘除)算法的实现的详细内容,更多关于C++高精度算法的资料请关注我们其它相关文章!

(0)

相关推荐

  • 使用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++高精度算法的实现

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

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

  • 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.除法例子 前言 C/C++基本类型做算术运算时长度有限,但也基本满足大部分场景的使用,有时需要计算大长度数据就有点无能为力了,比如1000的阶乘结果就有2000多位,用基本类型是无法计算的. 高精度的算法,一般的方式是用一个很长的数组去记录数据,数组的每一位记录固定位数的数字,记录顺序是低位到高位.计算方式则通常采用模拟立竖式计算.计算方

  • php 二维数组快速排序算法的实现代码

    php 二维数组快速排序算法的实现代码 二维数组排序算法与一维数组排序算法基本理论都是一样,都是通过比较把小的值放在左变的数组里,大的值放在右边的数组里在分别递归. 实例代码: <?php class Bubble { private function __construct() { } private static function sortt($data) { if (count ( $data ) <= 1) { return $data; } $tem = $data [0]['sco

  • php仿微信红包分配算法的实现方法

    本文实例讲述了php仿微信红包分配算法的实现方法.分享给大家供大家参考,具体如下: /** * 红包分配:把一定金额随机分配给指定人数 * * @param int $money 用于分配的金额 * @param int $num 分配人数 */ function RandomMoney($money, $num) { echo "$money元随机分成$num份分别是:<br/>"; $remain=$money; $use=0; for ($i=1; $i<$nu

  • Linux内核中红黑树算法的实现详解

    一.简介 平衡二叉树(BalancedBinary Tree或Height-Balanced Tree) 又称AVL树.它或者是一棵空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1.若将二叉树上结点的平衡因子BF(BalanceFactor)定义为该结点的左子树的深度减去它的右子树的深度,则平衡二叉树上所有结点的平衡因子只可能是-1.0和1.(此段定义来自严蔚敏的<数据结构(C语言版)>) 红黑树 R-B Tree,全称是Red-B

  • java几种排序算法的实现及简单分析

    本文实例讲述了java几种排序算法的实现及简单分析.分享给大家供大家参考.具体如下: package test; public class first { /*普通的插入排序*/ public void insertSort(int[] list) { int i, j; list[0] = -999; //相当于设置一个监视哨兵,不用判断是否越界, //但要求数组从第二个数开始即i=1开始存储 for (i = 1; i < list.length; i++) { j = i; while (

  • PHP二分查找算法的实现方法示例

    本文实例讲述了PHP二分查找算法的实现方法.分享给大家供大家参考,具体如下: 二分查找法需要数组是一个有序的数组 假设我们的数组是一个递增的数组,首先我们需要找到数组的中间位置. 1. 要知道中间位置就需要知道起始位置和结束位置,然后取出中间位置的值来和我们的值做对比. 2. 如果中间值大于我们的给定值,说明我们的值在中间位置之前,此时需要再次二分,因为在中间之前,所以我们需要变的值是结束位置的值,此时结束位置的值应该是我们此时的中间位置. 3. 反之,如果中间值小于我们给定的值,那么说明给定值

  • vue2.0中goods选购栏滚动算法的实现代码

    不多说,直接代码,以便以后重复利用: <script type="text/ecmascript-6"> import BScroll from 'better-scroll'; const ERR_OK = 0; export default { props: { sell: { type: Object } }, data() { return { goods: [], listHeight: [], scrollY: 0 }; }, computed: { curre

  • C/C++ MD5算法的实现代码

    在逆向程序的时候,经常会碰到加密的算法的问题,前面分析UC的逆向工程师的面试题2的时候,发现使用了MD5的加密算法(MD5算法是自己实现的,不是使用的算法库函数).尤其是在逆向分析网络协议的时候,一般的程序使用的加密算法都是使用的库函数提供的算法,有些程序使用的算法是自己实现的:相对来说使用函数库提供的加密函数的算法相对来说比较好识别,因为有算法常见函数在:但是如果不是使用的函数库提供的加密的函数而是自己去实现某些算法话,识别起来有一定的难度,这就需要你对函数的加密原理以及流程还算法的特征比较熟

  • 基于ID3决策树算法的实现(Python版)

    实例如下: # -*- coding:utf-8 -*- from numpy import * import numpy as np import pandas as pd from math import log import operator #计算数据集的香农熵 def calcShannonEnt(dataSet): numEntries=len(dataSet) labelCounts={} #给所有可能分类创建字典 for featVec in dataSet: currentLa

  • 应用OpenCV和Python进行SIFT算法的实现详解

    应用OpenCV和Python进行SIFT算法的实现 如下图为进行测试的gakki101和gakki102,分别验证基于BFmatcher.FlannBasedMatcher等的SIFT算法,对比其优劣.为体现出匹配效果对于旋转特性的优势,将图gakki101做成具有旋转特性的效果. 基于BFmatcher的SIFT实现 BFmatcher(Brute-Force Matching)暴力匹配,应用BFMatcher.knnMatch( )函数来进行核心的匹配,knnMatch(k-nearest

随机推荐