news 2026/5/18 22:49:09

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

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
C++高精度算法的简单实现

一、基本原理

1、存储方式

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

2、计算方式

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

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

二、辅助方法

1、字符串转高精度

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

1

2

3

4

5

6

7

8

9

10

11

12

/// <summary>

/// 通过字符串初始化

/// </summary>

/// <param name="a">[in]高精度数组</param>

/// <param name="value">[in]字符串首地址</param>

staticvoidloadStr(int* a,constchar* value)

{

//记录长度

a[0] =strlen(value);

for(inti = 1; i <= a[0]; i++)

a[i] = value[a[0] - i] -'0';

}

2、整型转高精度

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

/// <summary>

/// 通过无符号整型初始化

/// </summary>

/// <param name="a">[in]高精度数组</param>

/// <param name="value">[in]整型值</param>

staticvoidloadInt(int* a, uint64_t value)

{

for(size_ti = 1; i < 8096; i++)

{

a[i] = value % 10;

value /= 10;

if(!value)

{

//记录长度

a[0] = i;

return;

}

}

}

3、比较

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

/// <summary>

/// 比较两个高精度数的大小

/// </summary>

/// <param name="a">[in]第一个数</param>

/// <param name="b">[in]第二个数</param>

/// <returns>1是a>b,0是a==b,-1是a<b</returns>

staticintcompare(int* a,int* b)

{

if(a[0] > b[0])return1;

if(a[0] < b[0])return-1;

for(inti = a[0]; i > 0; i--)

if(a[i] > b[i])return1;

elseif(a[i] < b[i])return-1;

return0;

}

4、打印

1

2

3

4

5

6

7

8

9

/// <summary>

/// 打印输出结果

/// </summary>

staticvoidprint(int* a) {

if(!a[0])

printf("0");

for(inti = a[0]; i > 0; i--)

printf("%d", a[i]);

}

三、算法实现

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

1、加法

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

/// <summary>

/// 加法(累加)

///结果会保存在a中

/// </summary>

/// <param name="a">[in]被加数</param>

/// <param name="b">[in]加数</param>

staticvoidacc(int* a,int* b)

{

intlen = 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(inti = 1; i <= len; i++) {

inttemp = a[i] + b[i];

a[i] = temp % 10;

a[i + 1] += temp / 10;

}

if(a[len + 1])a[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

/// <summary>

/// 减法(累减)

///结果会保存在a中

/// </summary>

/// <param name="a">[in]被减数，被减数必须大于等于减数</param>

/// <param name="b">[in]减数</param>

staticvoidsubc(int* a,int* b) {

memset(b + b[0] + 1, 0, (a[0] - b[0]) *sizeof(int));

for(inti = 1; i <= a[0]; i++)

{

inttemp = a[i] - b[i];

a[i] = temp;

if(temp < 0)

{

//借位

a[i + 1] -= 1;

a[i] += 10;

}

}

//记录长度

for(inti = a[0]; i > 0; i--)

if(a[i])

{

a[0] = i;

return;

}

a[0] = 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

/// <summary>

/// 乘法

/// </summary>

/// <param name="a">[in]被乘数</param>

/// <param name="b">[in]乘数</param>

/// <param name="c">[out]结果，数组长度必须大于等于aLen+bLen+1</param>

staticvoidmul(int* a,int* b,intc[]) {

c[a[0] + b[0]] = 0;

memset(c, 0,sizeof(int) * (a[0] + b[0] + 1));

for(inti = 1; i <= a[0]; i++)

{

intj;

intd = 0;

//被乘数的一位去乘以乘数的每一位

for(j = 1; j <= b[0]; j++)

{

inttemp = 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(inti = a[0] + b[0]; i > 0; i--)

if(c[i])

{

c[0] = i;

return;

}

}

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

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

staticvoiddivi(int* a,int* b,int* c,int* mod,int* temp) {

//相差的阶数

intdigit = 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(inti = a[0] - b[0] + 1; i > 0; i--)

if(c[i])

{

c[0] = i;

return;

}

}

四、使用示例

1、加法

计算累加

1

2

3

4

5

6

7

8

9

10

11

12

13

14

intmain() {

int64_t n;

intnum[1024];

intnum2[1024];

std::cin >> n;

loadInt(num, 0);

for(int64_t i = 1; i <= n; i++)

{

loadInt(num2, i);

acc(num, num2);

}

print(num);

return0;

}

结果：

2、减法

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

1

2

3

4

5

6

7

8

9

10

11

intmain()

{

inta1[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);

return0;

}

结果：

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

3、乘法

计算阶乘

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

intmain() {

int64_t n;

intnum[8192];

intnum2[8192];

intnum3[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);

return0;

}


版权声明: 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！
网站建设 2026/5/18 22:49:08

如何用UABEA解锁Unity游戏资源：跨平台编辑器的完整指南

如何用UABEA解锁Unity游戏资源&#xff1a;跨平台编辑器的完整指南 【免费下载链接】UABEA c# uabe for newer versions of unity 项目地址: https://gitcode.com/gh_mirrors/ua/UABEA 想要修改游戏角色皮肤、替换背景音乐或探索游戏内部资源吗&#xff1f;UABEA&#x…

作者头像 李华
网站建设 2026/5/18 22:45:29

机器人钱包BotWallet：自动化交易私钥安全与高可用架构实战

1. 项目概述&#xff1a;一个面向自动化交易场景的“机器人钱包”最近在折腾自动化交易和链上交互&#xff0c;发现一个挺有意思的开源项目叫kialongacting968/botwallet。从名字就能看出来&#xff0c;这玩意儿是个“机器人钱包”。但别被名字骗了&#xff0c;它可不是一个简单…

作者头像 李华
网站建设 2026/5/18 22:45:25

IDEA 定义返回值快捷键

IDEA 定义返回值快捷键 在 IntelliJ IDEA 中&#xff0c;当你想要为一个方法调用快速生成变量来接收返回值时&#xff0c;最常用、最高效的快捷键是 Ctrl Alt V。 此外&#xff0c;根据你的具体需求&#xff08;是想补全语句、生成变量还是修改设置&#xff09;&#xff0c;还…

作者头像 李华
网站建设 2026/5/18 22:44:24

3步轻松搞定：Windows上安装Android应用的终极指南

3步轻松搞定&#xff1a;Windows上安装Android应用的终极指南 【免费下载链接】APK-Installer An Android Application Installer for Windows 项目地址: https://gitcode.com/GitHub_Trending/ap/APK-Installer 你是否曾经想过在Windows电脑上直接运行Android应用&…

作者头像 李华
网站建设 2026/5/18 22:43:10

AI视觉的痛点难点深度剖析（总论）

重磅预告&#xff1a;本专栏将独家连载系列丛书《智能体视觉技术与应用》部分精华内容&#xff0c;该书是世界首套系统阐述“因式智能体”视觉理论与实践的专著&#xff0c;特邀美国 TypeOne 公司首席科学家、斯坦福大学博士 Bohan 担任技术顾问。Bohan先生师从美国三院院士、“…

作者头像 李华