| « | September 2025 | » | | 日 | 一 | 二 | 三 | 四 | 五 | 六 | | 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 | | | | | |
|
| 公告 |
本站技术贴除标明为“原创”的之外，其余均为网上转载，文中我会尽量保留原作者姓名，若有侵权请与我联系，我将第一时间做出修改。谢谢！
——既瑜 |
| 统计 |
blog名称:★既瑜★
日志总数:183
评论数量:636
留言数量:-25
访问次数:1411886
建立时间:2005年3月12日 |
OICQ：215768265
njucs2001@hotmail.com
erichoo1982@gmail.com |
|
W3CHINA Blog首页 管理页面 写新日志 退出
 [【技术文档】][转]分治法优化大整数乘法 C++实现 |
上大学算法分析实验课的内容.关于利用分治法大整数乘法.还没有解决大整数的存储方式,应该是要利用一维数组来解决.所以目前只是5位数的运算没有问题.程序不是很健全,但是算法的核心部分应该是已经都在这里了.
VC++6.0下测试通过.
#include <iostream.h>#include <math.h>
long mult(long x,long y,int n);int num(long x);
void main() //主函数{ long x,y; cout<<"input x and y:"<<endl; cin>>x>>y; cout<<mult(x,y,num(x))<<endl;}
long mult(long x,long y,int n){ long a,b,c,d,s; if (n=1) return x*y; else { a=long(x/pow(10,(n/2))); //取x的左半部分 b=long(x%long(pow(10,(n/2)))); //取x的右半部分 c=long(y/pow(10,(n/2))); //取y的左半部分 d=long(y%long(pow(10,(n/2)))); //取y的右半部分 s=mult(a,c,n)*pow(2,n)+(mult((a-b),(d-c),n)+mult(a,c,n)+mult(b,d,n))*pow(2,n/2)+mult(b,d,n); //书上的公式 return (s); }}
int num(long x) //判断输入的数字的位数{ int i=0; if(x-9<=0) return 1; else { while (x!=0) { i++; x=x/10; } return i; }}
Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=505113
|
阅读全文(27023) | 回复(8) | 编辑 | 精华 |
| 回复:[转]分治法优化大整数乘法 C++实现 |
|
liu(游客)发表评论于2012/9/26 11:29:55 |
以下引用孟宪龙(游客)在2012-5-8 10:29:18的评论:
s=mult(a,c,n)*pow(2,n)+(mult((a-b),(d-c),n)+mult(a,c,n)+mult(b,d,n))*pow(2,n/2)+mult(b,d,n);
没有对n进行任何操作，递归永远跳不出来！是 求s的正确写法 急···
|
个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除 |
| 回复:[转]分治法优化大整数乘法 C++实现 |
|
孟宪龙(游客)发表评论于2012/5/8 10:29:18 |
s=mult(a,c,n)*pow(2,n)+(mult((a-b),(d-c),n)+mult(a,c,n)+mult(b,d,n))*pow(2,n/2)+mult(b,d,n);
没有对n进行任何操作，递归永远跳不出来！
|
| 个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除 |
| 回复:[转]分治法优化大整数乘法 C++实现 |
|
xiaogang(游客)发表评论于2007/10/22 21:11:04 |
#include <iostream.h>#include <math.h>
long mult(long x,long y,int n);int num(long x);
void main() //主函数{ long x,y; cout<<"input x and y:"<<endl; cin>>x>>y; cout<<mult(x,y,num(x))<<endl;}
long mult(long int x, long int y, int n) //{X和Y为2个小于2n的整数，返回结果为X和Y的乘积XY}{ long int s; if( ( (x>=0) && (y>=0) ) || ( (x<0) && (y<0) ) ) s = 1; else s = -1;
x=abs(x); y=abs(y); //{X和Y分别取绝对值}
if(n==1) { if((x==1)&&(y==1)) return s; else return x*y*s; } else { long int A=(long)(x/pow(10,(n/2))); //X的左边n/2位; long int B=(long)(x%(long)(pow(10,(n/2)))); //X的右边n/2位; long int C=(long)(y/pow(10,(n/2))); //Y的左边n/2位; long int D=(long)(y%(long)(pow(10,(n/2)))); //Y的右边n/2位; long int m1=mult(A,C,n/2); long int m2=mult(A-B,D-C,n/2); long int m3=mult(B,D,n/2);
s=s*(m1*pow(10,(n/2)*2)+(m1+m2+m3)*pow(10,n/2)+m3); } return s; }
int num(long x) //判断输入的数字的位数{ int i=0; if(x-9<=0) return 1; else { while (x!=0) { i++; x=x/10; } return i; }}
|
| 个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除 |
| 回复:[转]分治法优化大整数乘法 C++实现 |
|
apo(游客)发表评论于2007/9/28 21:30:14 |
if (n=1) return x*y;永远为真，这个程序和直接求乘法一样的了,后面的全是废话
|
| 个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除 |
| 回复:[转]分治法优化大整数乘法 C++实现 |
|
jun(游客)发表评论于2007/6/2 12:27:19 |
但是这个只能求一般的数啊，连10000000*100000之类的东西都求不了
|
| 个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除 |
| 回复:[转]分治法优化大整数乘法 C++实现 |
|
zxl(游客)发表评论于2006/11/11 20:50:05 |
// *********************Algorithm: (a+ib)*(c+id)=(ac-bd)+i(bc+ad)**************************Complex Complex::operator*( const Complex &operand2 ) const{ return Complex( real * operand2.real - imaginary * operand2.imaginary, imaginary * operand2.real + real * operand2.imaginary );}
|
| 个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除 |
| 回复:[转]分治法优化大整数乘法 C++实现 |
|
flyfish(游客)发表评论于2006/3/23 15:17:39 |
如果要求两个复数乘法的话。。。怎么写？
我的QQ414147419
|
| 个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除 |
| 回复:[转]分治法优化大整数乘法 C++实现 |
|
flyfish(游客)发表评论于2006/3/23 15:16:48 |
如果要求两个复数乘法的话。。。怎么写？
|
| 个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除 |
» 1 »
|
