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

/// <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';
}

/// <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;
        }
    }
}

/// <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;
}

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

/// <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]++;
}

/// <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;
}

/// <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;
        }
}

/// <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;
        }
}

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;
}

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;
}

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;
}

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;
}