欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C/C++高精度(加減乘除)算法的實(shí)現(xiàn)

 更新時(shí)間：2022年12月15日 10:46:53   作者：CodeOfCC  
高精度的算法，一般的方式是用一個(gè)很長(zhǎng)的數(shù)組去記錄數(shù)據(jù)，數(shù)組的每一位記錄固定位數(shù)的數(shù)字，記錄順序是低位到高位。本文將通過(guò)實(shí)例為大家介紹下高精度算法的實(shí)現(xiàn)，感興趣的可以了解一下

前言

C/C++基本類型做算術(shù)運(yùn)算時(shí)長(zhǎng)度有限，但也基本滿足大部分場(chǎng)景的使用，有時(shí)需要計(jì)算大長(zhǎng)度數(shù)據(jù)就有點(diǎn)無(wú)能為力了，比如1000的階乘結(jié)果就有2000多位，用基本類型是無(wú)法計(jì)算的。

高精度的算法，一般的方式是用一個(gè)很長(zhǎng)的數(shù)組去記錄數(shù)據(jù)，數(shù)組的每一位記錄固定位數(shù)的數(shù)字，記錄順序是低位到高位。計(jì)算方式則通常采用模擬立豎式計(jì)算。計(jì)算方式有一些優(yōu)化方法，比如FFT快速傅里葉變換優(yōu)化乘法，牛頓迭代優(yōu)化除法。

本方法采用的，是上述的一般方式，用數(shù)組從低到高位記錄數(shù)據(jù)，計(jì)算方式采用模擬立豎式計(jì)算。

一、必要的參數(shù)

1、計(jì)算位數(shù)

需要設(shè)定數(shù)組每個(gè)元素記錄的位數(shù)即計(jì)算的進(jìn)制（十進(jìn)制、百進(jìn)制、千進(jìn)制）。計(jì)算位數(shù)越大，計(jì)算性能越好，在32/64位程序中，位數(shù)的范圍可以是[1,9]。

2、計(jì)算進(jìn)制

與計(jì)算位數(shù)直接對(duì)應(yīng)，比如1位等于10進(jìn)制，2位等于百進(jìn)制。

3、數(shù)組類型

根據(jù)計(jì)算位數(shù)定義能裝載數(shù)據(jù)的整型，盡量不浪費(fèi)空間又不溢出，比如2位以內(nèi)可以用int8，4位可以用int16等。

代碼實(shí)現(xiàn)如下：

#include<stdint.h>
#include<stdio.h>
//計(jì)算位數(shù)，范圍[1,9]
#define NUM_DIGIT 9
//數(shù)組類型
#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]時(shí)用int32就可以裝載數(shù)據(jù)，但是實(shí)測(cè)發(fā)現(xiàn)用int32在32位程序中，對(duì)除法性能有影響，用int64反而正常，這是比較奇怪的現(xiàn)象。
#define _NUM_T int64_t
#else
    static_assert(1, "NUM_DIGIT must > 0 and <=9");
#endif
//計(jì)算進(jìn)制
    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

上述代碼只要設(shè)置NUM_DIGIT(計(jì)算位數(shù))就可以，其他值（計(jì)算進(jìn)制、數(shù)組類型）都會(huì)自動(dòng)生成。

二、輔助函數(shù)

1、初始化函數(shù)

由整型、字符串初始化高精度數(shù)組的方法。

2、比較函數(shù)

比較兩個(gè)高精度數(shù)的大小等于。

3、輸出函數(shù)

將高精度數(shù)組打印輸出。

代碼實(shí)現(xiàn)如下：

    /// <summary>
    /// 通過(guò)字符串初始化
    /// </summary>
    /// <param name="a">[in]高精度數(shù)組</param>
    /// <param name="value">[in]字符串首地址</param>
    /// <param name="len">[in]字符串長(zhǎng)度</param>
    /// <returns>數(shù)據(jù)長(zhǎng)度</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>
    /// 通過(guò)無(wú)符號(hào)32整型初始化
    /// </summary>
    /// <param name="a">[in]高精度數(shù)組</param>
    /// <param name="value">[in]整型值</param>
    /// <returns>數(shù)據(jù)長(zhǎng)度</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>
    /// 通過(guò)無(wú)符號(hào)64整型初始化
    /// </summary>
    /// <param name="a">[in]高精度數(shù)組</param>
    /// <param name="value">[in]整型值</param>
    /// <returns>數(shù)據(jù)長(zhǎng)度</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>
    /// 比較兩個(gè)高精度數(shù)的大小
    /// </summary>
    /// <param name="a">[in]第一個(gè)數(shù)</param>
    /// <param name="aLen">[in]第一個(gè)數(shù)的長(zhǎng)度</param>
    /// <param name="b">[in]第二個(gè)數(shù)</param>
    /// <param name="bLen">[in]第二個(gè)數(shù)的長(zhǎng)度</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>
    /// 打印輸出結(jié)果
    /// </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]);
    }

三、實(shí)現(xiàn)加減乘除

1、加法

由于數(shù)組存儲(chǔ)數(shù)據(jù)的順序是由低位到高位的，所以只需要兩個(gè)數(shù)從數(shù)組0位開(kāi)始相加，結(jié)果除以計(jì)算位數(shù)，余數(shù)保存在第一個(gè)數(shù)數(shù)組當(dāng)前位，商累加到第一個(gè)數(shù)數(shù)組的下一位，然后下標(biāo)加1重復(fù)前面的計(jì)算，直到全部元素計(jì)算完。

代碼實(shí)現(xiàn)如下：

    /// <summary>
    /// 加法(累加)
    ///結(jié)果會(huì)保存在a中
    /// </summary>
    /// <param name="a">[in]被加數(shù)</param>
    /// <param name="aLen">[in]被加數(shù)長(zhǎng)度</param>
    /// <param name="b">[in]加數(shù)</param>
    /// <param name="bLen">[in]加數(shù)長(zhǎng)度</param>
    /// <returns>結(jié)果長(zhǎng)度</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、減法

減法的原理和加法是類似的，兩個(gè)數(shù)從數(shù)組0位開(kāi)始相減，結(jié)果大于等于0直接保存到第一個(gè)數(shù)數(shù)組當(dāng)前位，否則結(jié)果小于零結(jié)果+計(jì)算進(jìn)制保存到第一個(gè)數(shù)數(shù)組當(dāng)前位，同時(shí)下一位減等于1，然后下標(biāo)加1重復(fù)前面的計(jì)算，直到全部元素計(jì)算完。

代碼實(shí)現(xiàn)如下：

/// <summary>
    /// 減法(累減)
    ///結(jié)果會(huì)保存在a中
    /// </summary>
    /// <param name="a">[in]被減數(shù)，被減數(shù)必須大于等于減數(shù)</param>
    /// <param name="aLen">[in]被減數(shù)長(zhǎng)度</param>
    /// <param name="b">[in]減數(shù)</param>
    /// <param name="bLen">[in]減數(shù)長(zhǎng)度</param>
    /// <returns>結(jié)果長(zhǎng)度</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、乘法

依然是參考立豎式計(jì)算方法，兩層循環(huán)，遍歷一個(gè)數(shù)的元素去乘以另一個(gè)數(shù)的每個(gè)元素，結(jié)果記錄到新的數(shù)組中。

代碼實(shí)現(xiàn)如下：

/// <summary>
    /// 乘法
    /// </summary>
    /// <param name="a">[in]被乘數(shù)</param>
    /// <param name="aLen">[in]被乘數(shù)長(zhǎng)度</param>
    /// <param name="b">[in]乘數(shù)</param>
    /// <param name="bLen">[in]乘數(shù)長(zhǎng)度</param>
    /// <param name="c">[out]結(jié)果，數(shù)組長(zhǎng)度必須大于等于aLen+bLen+1，且全部元素為0</param>
    /// <returns>結(jié)果長(zhǎng)度</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、除法

基本的除法直接利用減法就可以實(shí)現(xiàn)，本方法使用的是模擬立豎式計(jì)算的方式，將移動(dòng)除數(shù)使其與被除數(shù)高位對(duì)其，乘以一定倍數(shù)讓除數(shù)與被除數(shù)值接近再進(jìn)行減法運(yùn)算。

代碼實(shí)現(xiàn)如下：

/// <summary>
    /// 除法
    /// </summary>
    /// <param name="a">[in]被除數(shù),被除數(shù)必須大于除數(shù)。小于商為0、余數(shù)為除數(shù)，等于商為1、余數(shù)為0，不需要在函數(shù)內(nèi)實(shí)現(xiàn)，在外部通過(guò)compare就可以做到。</param>
    /// <param name="aLen">[in]被除數(shù)長(zhǎng)度</param>
    /// <param name="b">[in]除數(shù)</param>
    /// <param name="bLen">[in]除數(shù)長(zhǎng)度</param>
    /// <param name="c">[out]商，數(shù)組長(zhǎng)度大于等于aLen，且全部元素為0</param>
    /// <param name="mod">[out]余數(shù)，數(shù)組長(zhǎng)度大于等于aLen</param>
    /// <param name="modLen">[out]余數(shù)長(zhǎng)度</param>
    /// <param name="temp">[in]臨時(shí)緩沖區(qū)，由外部提供以提高性能，數(shù)組長(zhǎng)度大于等于aLen+bLen+1</param>
    /// <returns>商長(zhǎng)度</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 以一般整數(shù)輸入)。

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、減法例子

兩個(gè)任意十一位數(shù)的減法；（小于二十位）

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 以一般整數(shù)輸入)。

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、除法例子

給定兩個(gè)非負(fù)整數(shù)A，B，請(qǐng)你計(jì)算 A / B的商和余數(shù)。

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++高精度(加減乘除)算法的實(shí)現(xiàn)的詳細(xì)內(nèi)容，更多關(guān)于C++高精度算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

相關(guān)文章

  • QT TCP實(shí)現(xiàn)簡(jiǎn)單的通信示例

    QT TCP實(shí)現(xiàn)簡(jiǎn)單的通信示例

    這篇文章主要為大家詳細(xì)介紹了QT TCP簡(jiǎn)單的通信示例，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
    2022-08-08
  • C++基于回溯法解決八皇后問(wèn)題示例

    C++基于回溯法解決八皇后問(wèn)題示例

    這篇文章主要介紹了C++基于回溯法解決八皇后問(wèn)題,簡(jiǎn)單描述了八皇后問(wèn)題,以及回溯法的原理與解決八皇后問(wèn)題的相關(guān)操作技巧,需要的朋友可以參考下
    2017-11-11
  • 減少C++代碼編譯時(shí)間的簡(jiǎn)單方法(必看篇)

    減少C++代碼編譯時(shí)間的簡(jiǎn)單方法(必看篇)

    下面小編就為大家?guī)?lái)一篇減少C++代碼編譯時(shí)間的簡(jiǎn)單方法(必看篇)。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧
    2017-01-01
  • C++中virtual繼承的深入理解

    C++中virtual繼承的深入理解

    本篇文章是對(duì)C++中的virtual繼承進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下
    2013-05-05
  • C++中幾種將整數(shù)轉(zhuǎn)換成二進(jìn)制輸出的方法總結(jié)

    C++中幾種將整數(shù)轉(zhuǎn)換成二進(jìn)制輸出的方法總結(jié)

    下面小編就為大家?guī)?lái)一篇C++中幾種將整數(shù)轉(zhuǎn)換成二進(jìn)制輸出的方法總結(jié)。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧
    2016-09-09
  • C語(yǔ)言攝氏度互相轉(zhuǎn)換華氏

    C語(yǔ)言攝氏度互相轉(zhuǎn)換華氏

    這篇文章主要介紹了C語(yǔ)言攝氏度互相轉(zhuǎn)換華氏，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2021-01-01
  • 求32位機(jī)器上unsigned int的最大值及int的最大值的解決方法

    求32位機(jī)器上unsigned int的最大值及int的最大值的解決方法

    本篇文章是對(duì)求32位機(jī)器上unsigned int的最大值及int的最大值的解決方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下
    2013-05-05
  • C語(yǔ)言實(shí)現(xiàn)漢諾塔(圖文詳解)

    C語(yǔ)言實(shí)現(xiàn)漢諾塔(圖文詳解)

    個(gè)人覺(jué)得漢諾塔這個(gè)遞歸算法比電子老鼠的難了一些，不過(guò)一旦理解了也還是可以的，其實(shí)網(wǎng)上也有很多代碼，可以直接參考。記得大一開(kāi)始時(shí)就做過(guò)漢諾塔的習(xí)題，但是那時(shí)代碼寫(xiě)得很長(zhǎng)很長(zhǎng)，也是不理解遞歸的結(jié)果。今天重新來(lái)實(shí)現(xiàn)一下
    2021-08-08
  • C++中繼承(inheritance)詳解及其作用介紹

    C++中繼承(inheritance)詳解及其作用介紹

    這篇文章主要介紹了C++中繼承(inheritance)詳解及其作用介紹，本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下
    2021-09-09
  • C語(yǔ)言實(shí)現(xiàn)天氣信息管理系統(tǒng)

    C語(yǔ)言實(shí)現(xiàn)天氣信息管理系統(tǒng)

    這篇文章主要介紹了C語(yǔ)言實(shí)現(xiàn)天氣信息管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
    2020-06-06

最新評(píng)論