您尚未登录。

楼主 #1 2018-12-01 09:12:41

bunny
会员
注册时间: 2020-05-23
已发帖子: 152
积分: 152

大数运算之乘法篇——计算20000的阶乘

直接上源码:

#include <stdio.h>
#include <stdlib.h>

char* real_mult(const char* a, const char* b) {
	int i, j, k, m, n, len_a, len_b;
	len_a = strlen(a);
	len_b = strlen(b);
	int* res_p;
	char* c;
	res_p = (int*)malloc((len_a + len_b) * sizeof(int));
	if (!res_p) {
        printf((const char*)"malloc int[%d] fail!\n", len_a + len_b);
        for ( ; ; );
	}
	for (i = len_a + len_b - 1; i >= 0; i--) {
		res_p[i] = 0;
	}
	for (i = 0; i < len_a; i++) {
		for (j = 0; j < len_b; j++) {
			k = i + j + 1;
			res_p[k] += (a[i] - '0') * (b[j] - '0');
		}
	}
	res_p[0] = 0;
	for ( ; k > 0; k--) {
		res_p[k - 1] += res_p[k] / 10;
		res_p[k] %= 10;
	}
	for (j = 0; j < len_a + len_b; j++) {
        if (res_p[j] != 0) {
            break;
        }
	}
	c = (char*)malloc((len_a + len_b + 1 - j) * sizeof(char));
	if (!c) {
        printf((const char*)"malloc char[%d] fail!\n", len_a + len_b + 1 - j);
        for ( ; ; );
	}
	for (i = 0; i < len_a + len_b - j; i++) {
		c[i] = (char)(res_p[i + j] + '0');
	}
	free(res_p);
	c[i] = '\0';
	return c;
}

char* mult1(char* a, const char* b) {
    char* c = real_mult((const char*)a, b);
    free(a);
    return c;
}

char* order(int n) {
    char temp[16];
    char* res = (char*)"1";
    for ( ; n > 1; n--) {
        sprintf((char*)temp, "%d", n);
        res = mult1(res, (const char*)temp);
    }
    return res;
}

int main(int argc, const char* argv[]) {
    char* c;
    c = order(20000);
    printf("%s\n", c);
    free(c);
    return 0;
}

测试结果比对:
TIM20181201091200.png

离线

#2 2018-12-01 09:19:09

晕哥
管理员
所在地: 微信 whycan_cn
注册时间: 2017-09-06
已发帖子: 9,223
积分: 9197

Re: 大数运算之乘法篇——计算20000的阶乘

咦,服务器上面跑了一下, 有错误:

root@ubuntu:/tmp# vi multi.c
root@ubuntu:/tmp# gcc -o multi multi.c
multi.c: In function ‘real_mult’:
multi.c:6:10: warning: implicit declaration of function ‘strlen’ [-Wimplicit-function-declaration]
  len_a = strlen(a);
          ^~~~~~
multi.c:6:10: warning: incompatible implicit declaration of built-in function ‘strlen’
multi.c:6:10: note: include ‘<string.h>’ or provide a declaration of ‘strlen’
root@ubuntu:/tmp#
root@ubuntu:/tmp#
root@ubuntu:/tmp#
root@ubuntu:/tmp#
root@ubuntu:/tmp# ./multi
free(): invalid pointer
Aborted
root@ubuntu:/tmp#

QQ20181201093345.png





离线

#3 2018-12-01 09:40:09

晕哥
管理员
所在地: 微信 whycan_cn
注册时间: 2017-09-06
已发帖子: 9,223
积分: 9197

Re: 大数运算之乘法篇——计算20000的阶乘

QQ20181201093927.png

把49行注释起来, 就不会出现内存释放错误, 20000阶乘就算出来了.





离线

楼主 #4 2018-12-01 11:40:26

bunny
会员
注册时间: 2020-05-23
已发帖子: 152
积分: 152

Re: 大数运算之乘法篇——计算20000的阶乘

win系统和linux还是有些细微差异吧

离线

#5 2019-11-18 03:22:41

凿子树
会员
注册时间: 2017-10-17
已发帖子: 19
积分: 19

Re: 大数运算之乘法篇——计算20000的阶乘

晕哥 说:

https://whycan.cn/files/members/3/QQ20181201093927.png

把49行注释起来, 就不会出现内存释放错误, 20000阶乘就算出来了.

------------------------
错不在这!
而是这里
FluxBB bbcode 错误点
改为这样:

char* order(int n)
{
    char temp[16];
    char* res = (char*)"1";    //删除
    char* res = (char*)malloc(32);    //改正后
    for ( ; n > 1; n--)
    {
        sprintf((char*)temp, "%d", n);
        res = mult1(res, (const char*)temp);
    }
    return res;
}

就可以了。

离线

#6 2019-11-18 06:24:49

awfans
会员
注册时间: 2018-04-03
已发帖子: 264
积分: 264

Re: 大数运算之乘法篇——计算20000的阶乘

牛, 这么叼的bug都被揪出来了.

离线

#7 2019-11-18 08:54:44

kekemuyu
会员
注册时间: 2018-12-13
已发帖子: 841
积分: 721

Re: 大数运算之乘法篇——计算20000的阶乘

我也来一个go版本:

package main

import (
	"fmt"
	"strconv"
	// "log"
)

//BigMulti 大数相乘
func BigMulti(a, b string) string {
	if a == "0" || b == "0" {
		return "0"
	}
	// string转换成[]byte,容易取得相应位上的具体值
	bsi := []byte(a)
	bsj := []byte(b)

	temp := make([]int, len(bsi)+len(bsj))
	//两数相乘,结果位数不会超过两乘数位数和,即temp的长度只可能为 len(num1)+len(num2) 或 len(num1)+len(num2)-1
	// 选最大的,免得位数不够
	for i := 0; i < len(bsi); i++ {
		for j := 0; j < len(bsj); j++ {
			// 对应每个位上的乘积,直接累加存入 temp 中相应的位置
			temp[i+j+1] += int(bsi[i]-'0') * int(bsj[j]-'0')
		}
	}

	//统一处理进位
	for i := len(temp) - 1; i > 0; i-- {
		temp[i-1] += temp[i] / 10 //对该结果进位(进到前一位)
		temp[i] = temp[i] % 10    //对个位数保留
	}

	// a 和 b 较小的时候,temp的首位为0
	// 为避免输出结果以0开头,需要去掉temp的0首位
	if temp[0] == 0 {
		temp = temp[1:]
	}
	//转换结果:将[]int类型的temp转成[]byte类型,
	//因为在未处理进位的情况下,temp每位的结果可能超过255(go中,byte类型实为uint8,最大为255),所以temp选用[]int类型
	//但在处理完进位后,不再会出现溢出
	res := make([]byte, len(temp)) //res 存放最终结果的ASCII码

	for i := 0; i < len(temp); i++ {
		res[i] = byte(temp[i] + '0')
	}

	return string(res)
}

func main() {

	x := "1"

	for i := 1; i <= 20000; i++ {
		x = BigMulti(strconv.Itoa(i), x)

	}
	fmt.Println(x)
}

结果(只贴了三行太长了):
181920632023034513482764175686645876607160990147875264891806221863456946103855753445383609582775872473917750238418991204167124538392657686572347546452493027570920462535787578952590049182341454271803607039252108504728338372929686158005240463884119952662237979106622334146339347439592562978748211316341864766545558666043618408722395194

和c对比可以发现,go编码无需担心内存出错问题,go自带gc,专心写代码逻辑即可,不用为了其它事情分心。所以go兼顾了开发效率和执行速度,迄今为止它是两者平衡最好的语言。

最近编辑记录 kekemuyu (2019-11-18 10:10:57)

离线

#8 2019-11-18 09:47:31

xgui
会员
注册时间: 2019-09-07
已发帖子: 224
积分: 224

Re: 大数运算之乘法篇——计算20000的阶乘

膜拜楼上诸位大神

离线

楼主 #9 2019-11-18 20:46:04

bunny
会员
注册时间: 2020-05-23
已发帖子: 152
积分: 152

Re: 大数运算之乘法篇——计算20000的阶乘

凿子树 说:

------------------------
错不在这!
而是这里
https://whycan.cn/files/members/334/1.png
改为这样:

char* order(int n)
{
    char temp[16];
    char* res = (char*)"1";    //删除
    char* res = (char*)malloc(32);    //改正后
    for ( ; n > 1; n--)
    {
        sprintf((char*)temp, "%d", n);
        res = mult1(res, (const char*)temp);
    }
    return res;
}

就可以了。

确实是这个BUG,疏忽了

离线

页脚

工信部备案:粤ICP备20025096号 Powered by FluxBB

感谢为中文互联网持续输出优质内容的各位老铁们。 QQ: 516333132, 微信(wechat): whycan_cn (哇酷网/挖坑网/填坑网) service@whycan.cn