标题:高精度压位乘法
只看楼主
点线面
Rank: 8Rank: 8
来 自:NO.-1
等 级:蝙蝠侠
帖 子:525
专家分:980
注 册:2011-1-3
得分:2 
回复 9楼 犬虫门心
解决方法,最坏情况纯字符串操作,最好情况直接用数字类型,要想速度与储存空间平衡,字符串+数字类型

小代码,大智慧
2011-02-20 22:17
犬虫门心
Rank: 8Rank: 8
来 自:西安
等 级:蝙蝠侠
帖 子:209
专家分:753
注 册:2011-1-25
得分:0 
以下是引用点线面在2011-2-20 22:17:25的发言:

解决方法,最坏情况纯字符串操作,最好情况直接用数字类型,要想速度与储存空间平衡,字符串+数字类型
输入时,只能使用字符串,这样才能保证能输入足够大的数;而处理时,无论输入的数的大小,都应用上面我所说的那种方案进行。
其实,这样(如果我说的就是所谓的压4位)并非最大效率,因为4位二进制能表示的数有16个,但这样用只能用10个。不过,这样也有好处,算法相对容易些。
今天早上看到这个帖子的,白天陪孩子出去玩,满脑子都是这个问题!楼主害我啊!哈哈哈哈

当一名对得起学生学费的老师,一直是我的目标!我会更努力的!
2011-02-20 22:25
卧龙孔明
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:59
帖 子:3872
专家分:684
注 册:2006-10-13
得分:2 
学会google,其它不说。

My Blog: www.aiexp.info
虽然我的路是从这里开始的,但是这里不再是乐土.感谢曾经影响过,引导过,帮助过我的董凯,飞燕,leeco,starwing,Rockcarry,soft_wind等等等等.别了,BCCN.
2011-02-20 22:51
犬虫门心
Rank: 8Rank: 8
来 自:西安
等 级:蝙蝠侠
帖 子:209
专家分:753
注 册:2011-1-25
得分:0 
以下是引用卧龙孔明在2011-2-20 22:51:38的发言:

学会google,其它不说。
先生意思在下知道了。先学习去了。

当一名对得起学生学费的老师,一直是我的目标!我会更努力的!
2011-02-21 00:02
BlueGuy
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:29
帖 子:4476
专家分:4055
注 册:2009-4-18
得分:2 
加油~~

我就是真命天子,顺我者生,逆我者死!
2011-02-21 00:20
vandychan
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
等 级:贵宾
威 望:18
帖 子:2296
专家分:6418
注 册:2010-8-20
得分:2 
应该会好起来的

到底是“出来混迟早要还”还是“杀人放火金腰带”?
2011-02-21 00:38
清风拂晓
Rank: 8Rank: 8
来 自:火星
等 级:蝙蝠侠
威 望:1
帖 子:356
专家分:889
注 册:2010-8-13
得分:2 
#include<stdio.h>
#include<string.h>

#define MAX 100
/* the size of multiplicator */
#define ANS_MAX200
/* the size of answer */

intchange_char2int(char);
/* changecharacter type to integer type */

voidhigh_multiply(char * a,char * b,char * ans);
/* precisionnumber multiply precision number */

void main(void)
{

char a[MAX],b[MAX];
/* a:1st number
b:2ndnumber */

char ans[ANS_MAX];
/* the answer array,character type */

printf("Input the 1st number:\n");

gets(a);

printf("Input the 2nd number:\n");

gets(b);

high_multiply(a,b,ans);


/*print answer*/

printf("\n%s * %s = %s\n",a,b,ans);
}

intchange_char2int(char c)
{

if ((c>='0')&&(c<='9'))

return (c-'0');

else

{

printf ("Error!\n");

return -1;

}
}

void high_multiply(char * a,char * b,char * ans)
{

intans_tmp[ANS_MAX]; /* the temporarily answer array */

int i,j,key=0;

inta_len=strlen(a),b_len=strlen(b);

intt,ans_len=ANS_MAX-1;

for(i=0;i<ANS_MAX;i++)

ans_tmp=0;
/* initialize the answer array */


for(i=b_len-1;i>-1;i--)

{

inttemp_b=change_char2int(b);

t=ans_len--;

for(j=a_len-1;j>-1;j--)

{

inttemp_a=change_char2int(a[j]);

ans_tmp[t]+=temp_a*temp_b;

ans_tmp[t-1]+=ans_tmp[t]/10;

ans_tmp[t]%=10;

t--;

}

}


/* change theanswer array to character type */

for(i=0,j=0;i<ANS_MAX;i++)

{

if(ans_tmp==0&&key==0) continue;

key=1;

ans[j++]=ans_tmp+'0';

}

if (key==0)ans[j++]='0';

ans[j]='\0';
}
注:(代码在 Turbo C 2.0 环境下编译通过)

这只是个例子,和你问题的有点不一样

[ 本帖最后由 清风拂晓 于 2011-2-21 09:44 编辑 ]

清风拂暮(木)
2011-02-21 09:31
waterstar
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:5
帖 子:984
专家分:2810
注 册:2010-2-12
得分:2 
看了挺多,找了挺多,还是不明白怎么压位的。

冰冻三尺,非一日之寒;士别三日,不足刮目相看!
2011-02-21 10:01
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
得分:0 
看了卧龙写的高精度乘法优化,模仿自己写了一个且测试通过,待会儿我会发上来.

[ 本帖最后由 sunyh1999 于 2011-2-22 10:47 编辑 ]

欢迎来到我的博客:http://blog..cn/noisunyuhong
2011-02-22 10:24
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
得分:0 
回复 9楼 犬虫门心
您没有理解我意思,我的意思是:如果一个0-9的数占一个int的空间,不仅浪费空间而且运算速度慢.如果将一个int存入一个四位数,就会不浪费空间且速度加快4倍

欢迎来到我的博客:http://blog..cn/noisunyuhong
2011-02-22 10:51



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-332466-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.045842 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved