high-precision-algorithm

high-precision-algorithm

Charles Lv7
  2023-01-10 14:56:41 2023-01-10 14:56:41 Created   2023-07-30 10:52:49 2023-07-30 10:52:49 Updated      1.3k Words  6 Mins  

high-precision-algorithm

高精度

​ 在一般的科学计算中，会经常算到小数点后几百位或者更多，当然也可能是几千亿几百亿的大数字。一般这类数字我们统称为高精度数，高精度算法是用计算机对于超大数据的一种模拟加、减、乘、除、乘方、阶乘、开方等运算。 对于一个很大的数字N >= 10^ 100，很显然这样的数字无法在计算机中正常存储。于是， 我们想到了办法，将这个数字拆开，拆成一位一位的或者是四位四位的存储到一个数组中，用一个数组去表示一个数字。这样这个数字就被称谓是高精度数。 对于高精度数，也要像平常数一样做加减乘除以及乘方的运算，于是就有了高精度算法。

1.高精度加法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void high_precision_add(string num1, string num2, string& res) {
    int l1 = num1.size(), l2 = num2.size();
    int len = l1 > l2 ? l1 : l2;
    int a[N] = {0}, b[N] = {0};
    for (int i = l1 - 1; i >= 0; i--)
        a[l1 - i - 1] = num1.at(i) - '0';
    for (int i = l2 - 1; i >= 0; i--)
        b[l2 - i - 1] = num2.at(i) - '0';
    for (int i = 0; i < len; i++) {
        a[i] += b[i];
        a[i + 1] += a[i] / 10;
        a[i] %= 10;
    }
    if (a[len])
        len++;
    while (!a[len - 1] && len > 1)
        len--;
    for (int i = len - 1; i >= 0; i--) {
        res += (a[i] + '0');
    }
}

2.高精度乘法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void high_precision_multiply(string num1, string num2, string& res) {
    int l1 = num1.size(), l2 = num2.size();
    int a[N] = {0}, b[N] = {0}, c[N] = {0};
    for (int i = l1 - 1; i >= 0; i--)
        a[l1 - i - 1] = num1.at(i) - '0';
    for (int i = l2 - 1; i >= 0; i--)
        b[l2 - i - 1] = num2.at(i) - '0';
    for (int i = 0; i < l1; i++) {
        for (int j = 0; j < l2; j++) {
            c[i + j] += a[i] * b[j];
            if (a[i] > 9) {
                a[i + 1] += a[i] / 10;
                a[i] %= 10;
            }
        }
    }
    int len = l1 + l2;
    for (int i = 0; i < len; i++) {
        if (c[i] > 9) {
            c[i + 1] += c[i] / 10;
            c[i] %= 10;
        }
    }
    while (!c[len - 1] && len > 1)
        len--;
    for (int i = len - 1; i >= 0; i--) {
        res += (c[i] + '0');
    }
}

3.高精度减法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
void high_precision_sub(string num1, string num2, string& res) {
    int l1 = num1.size(), l2 = num2.size(), flag = 0;
    if (l1 < l2 || num1.compare(num2) < 0 && l1 == l2) {
        flag = 1;
    }
    int a[N] = {0}, b[N] = {0};
    if (!flag) {
        for (int i = l1 - 1; i >= 0; i--)
            a[l1 - i - 1] = num1.at(i) - '0';
        for (int i = l2 - 1; i >= 0; i--)
            b[l2 - i - 1] = num2.at(i) - '0';
    } else {
        for (int i = l2 - 1; i >= 0; i--)
            a[l2 - i - 1] = num2.at(i) - '0';
        for (int i = l1 - 1; i >= 0; i--)
            b[l1 - i - 1] = num1.at(i) - '0';
    }
    int len = l1 > l2 ? l1 : l2;
    for (int i = 0; i < len; i++) {
        a[i] -= b[i];
        if (a[i] < 0) {
            a[i + 1] -= 1;
            a[i] += 10;
        }
    }
    while (!a[len - 1] && len > 1)
        len--;
    if (flag) {
        res += '-';
    }
    for (int i = len - 1; i >= 0; i--) {
        res += (a[i] + '0');
    }
}

4.高精度除法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
void sub(string& num1, string& num2) {
    int l2 = num2.size();
    int low = 0;
    while (num1.at(low) == '0')
        low++;
    for (int i = low; i < l2; i++)
        num1.at(i) = num1.at(i) - num2.at(i) + '0';
    for (int i = l2 - 1; i > low; i--)
        if (num1.at(i) < '0') {
            num1.at(i) += 10;
            num1.at(i - 1)--;
        }
}
void high_precision_div(string num1, string num2, string& res) {
    int p = 0, re[N] = {0};
    int l1 = num1.size();
    int l2 = num2.size();
    if (l1 < l2 || (l1 == l2 && num1.compare(num2) < 0))
        res = "0";
    else {
        while (1) {
            re[p] = 0;
            while (num1.compare(num2) >= 0) {
                sub(num1, num2);
                re[p]++;
            }
            p++;
            if (l1 == l2)
                break;
            num2 = "0" + num2;
            l2++;
        }
        int low = 0;
        while (!re[low])
            low++;
        for (int i = low; i < p; i++)
            res += (re[i] + '0');
    }
}

模板题

阶乘之和

[NOIP1998 普及组] 阶乘之和

题目描述

用高精度计算出 S=1!+2!+3!+⋯+n!（n≤50）。

其中 ! 表示阶乘，定义为 n!=n×(n−1)×(n−2)×⋯×1。例如，5!=5×4×3×2×1=120。

输入格式

一个正整数 n。

输出格式

一个正整数 S，表示计算结果。

样例 #1

样例输入 #1

1
3
样例输出 #1
1
9

提示

【数据范围】

对于 100 的数据，1≤n≤50。

【其他说明】

注，《深入浅出基础篇》中使用本题作为例题，但是其数据范围只有 n≤20，使用书中的代码无法通过本题。

如果希望通过本题，请继续学习第八章高精度的知识。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <limits.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define M 100007
#define ll long long
int a[1005],b[1005],n;
int main() {
	int i,j;
	scanf("%d", &n);
	a[0]=b[0]=1;
	for (i=2; i<=n; i++) {
		for (j=0; j<100; j++) {
			b[j]*=i;
		}
		for (j=0; j<100; j++) {
			if (b[j]>9) {
				b[j+1] += b[j]/10;
				b[j]%=10;
			}
		}
		for (j=0; j<100; j++) {
			a[j]+=b[j];
			if (a[j]>9) {
				a[j+1] += a[j]/10;
				a[j]%=10;
			}
		}
	}
	for (i=100; i>=0&&a[i]==0; i--);
	for (j=i; j>=0; j--) printf("%d", a[j]);
	return 0;
}
  • Title: high-precision-algorithm
  • Author: Charles
  • Created at : 2023-01-10 14:56:41
  • Updated at : 2023-07-30 10:52:49
  • Link: https://charles2530.github.io/2023/01/10/high-precision-algorithm/
  • License: This work is licensed under CC BY-NC-SA 4.0.
recommend_articles
OO_pre_6 OO_pre_6 OO_pre_2 OO_pre_2 Ajax-note-2 Ajax-note-2
recommend_articles
OO_pre_6 OO_pre_6 OO_pre_2 OO_pre_2
Comments
On this page
high-precision-algorithm
  1. high-precision-algorithm
    1. 高精度
      1. 1.高精度加法
      2. 2.高精度乘法
      3. 3.高精度减法
      4. 4.高精度除法
    2. 模板题
      1. 输入格式
      2. 输出格式
      3. 样例 #1
        1. 样例输出 #1
      4. 提示
    3. AC代码