33,008
社区成员
发帖
与我相关
我的任务
分享多重精度-乘
假设b为进制，u, v分别为左右操作数，w为结果
u[0]表示最低位
1、n 位 u 乘 1 位 v
c = 0
i 从 0 到 n - 1 循环执行下面过程
t = u[i] + c
w[i] = t % b
c = t / b
输出c 作为溢出结果
2、n 位 u 乘 m 位 v
首先
w[i] = 0 对i = 0 .. m - 1
i 从 0 到 n - 1 循环执行下面过程
k = u[i]
c = 0
j 从 0 到 m - 1 循环执行下面过程
t = k * v[j] + w[i + j] + c
w[i + j] = t % b
c = t / b
w[i + m] = c
u[0]表示最低位
1、n 位 u 乘 1 位 v
c = 0
i 从 0 到 n - 1 循环执行下面过程
t = u[i] + c
w[i] = t % b
c = t / b
输出c 作为溢出结果
2、n 位 u 乘 m 位 v
首先
w[i] = 0 对i = 0 .. m - 1
i 从 0 到 n - 1 循环执行下面过程
k = u[i]
c = 0
j 从 0 到 m - 1 循环执行下面过程
t = k * v[j] + w[i + j] + c
w[i + j] = t % b
c = t / b
w[i + m] = c
...全文
请发表友善的回复…
发表回复
无心人 2004-08-18
- 打赏
- 举报
有点明白为什么加减法慢了，似乎代码执行路径预测出错的问题，大家帮着分析一下
liangbch 2004-08-18
- 打赏
- 举报
mark
kerbcurb 2004-08-17
- 打赏
- 举报
刚发现以pascal写的
来自
http://bbs.mydrs.org/dispbbs.asp?boardID=13&ID=5614&page=1
高精度计算
高精度数的定义：
type
hp=array[1..maxlen] of integer;
1．高精度加法
procedure plus ( a,b:hp; var c:hp);
var i,len:integer;
begin
fillchar(c,sizeof(c),0);
if a[0]>b[0] then len:=a[0] else len:=b[0];
for i:=1 to len do begin
inc(c,a+b);
if c>10 then begin dec(c,10); inc(c[i+1]); end; {进位}
end;
if c[len+1]>0 then inc(len);
c[0]:=len;
end;{plus}
2．高精度减法
procedure substract(a,b:hp;var c:hp);
var i,len:integer;
begin
fillchar(c,sizeof(c),0);
if a[0]>b[0] then len:=a[0] else len:=b[0];
for i:=1 to len do begin
inc(c,a-b);
if c<0 then begin inc(c,10);dec(c[i+1]); end;
while (len>1) and (c[len]=0) do dec(len);
c[0]:=len;
end;
3．高精度乘以低精度
procedure multiply(a:hp;b:longint;var c:hp);
var i,len:integer;
begin
fillchar(c,sizeof(c),0);
len:=a[0];
for i:=1 to len do begin
inc(c,a*b);
inc(c[i+1],(a*b) div 10);
c:=c mod 10;
end;
inc(len);
while (c[len]>=10) do begin {处理最高位的进位}
c[len+1]:=c[len] div 10;
c[len]:=c[len] mod 10;
inc(len);
end;
while (len>1) and (c[len]=0) do dec(len); {若不需进位则调整len}
c[0]:=len;
end;{multiply}
4．高精度乘以高精度
procedure high_multiply(a,b:hp; var c:hp}
var i,j,len:integer;
begin
fillchar(c,sizeof(c),0);
for i:=1 to a[0] do
for j:=1 to b[0] do begin
inc(c[i+j-1],a*b[j]);
inc(c[i+j],c[i+j-1] div 10);
c[i+j-1]:=c[i+j-1] mod 10;
end;
len:=a[0]+b[0]+1;
while (len>1) and (c[len]=0) do dec(len);
c[0]:=len;
end;
5．高精度除以低精度
procedure devide(a:hp;b:longint; var c:hp; var d:longint);
{c:=a div b; d:= a mod b}
var i,len:integer;
begin
fillchar(c,sizeof(c),0);
len:=a[0]; d:=0;
for i:=len downto 1 do begin
d:=d*10+a;
c:=d div b;
d:=d mod b;
end;
while (len>1) and (c[len]=0) then dec(len);
c[0]:=len;
end;
6．高精度除以高精度
procedure high_devide(a,b:hp; var c,d:hp);
var
i,len:integer;
begin
fillchar(c,sizeof(c),0);
fillchar(d,sizeof(d),0);
len:=a[0];d[0]:=1;
for i:=len downto 1 do begin
multiply(d,10,d);
d[1]:=a;
while(compare(d,b)>=0) do {即d>=b}
begin
Subtract(d,b,d);
inc(c);
end;
end;
while(len>1)and(c.s[len]=0) do dec(len);
c.len:=len;
end;
六、 树的遍历
1．已知前序中序求后序
procedure Solve(pre,mid:string);
var i:integer;
begin
if (pre='') or (mid='') then exit;
i:=pos(pre[1],mid);
solve(copy(pre,2,i),copy(mid,1,i-1));
solve(copy(pre,i+1,length(pre)-i),copy(mid,i+1,length(mid)-i));
post:=post+pre[1]; {加上根，递归结束后post即为后序遍历}
end;
2．已知中序后序求前序
procedure Solve(mid,post:string);
var i:integer;
begin
if (mid='') or (post='') then exit;
i:=pos(post[length(post)],mid);
pre:=pre+post[length(post)]; {加上根，递归结束后pre即为前序遍历}
solve(copy(mid,1,I-1),copy(post,1,I-1));
solve(copy(mid,I+1,length(mid)-I),copy(post,I,length(post)-i));
end;
3．已知前序后序求中序的一种
function ok(s1,s2:string):boolean;
var i,l:integer; p:boolean;
begin
ok:=true;
l:=length(s1);
for i:=1 to l do begin
p:=false;
for j:=1 to l do
if s1=s2[j] then p:=true;
if not p then begin ok:=false;exit;end;
end;
end;
procedure solve(pre,post:string);
var i:integer;
begin
if (pre='') or (post='') then exit;
i:=0;
repeat
inc(i);
until ok(copy(pre,2,i),copy(post,1,i));
solve(copy(pre,2,i),copy(post,1,i));
midstr:=midstr+pre[1];
solve(copy(pre,i+2,length(pre)-i-1),copy(post,i+1,length(post)-i-1));
end;
七 进制转换
1任意正整数进制间的互化
除n取余
2实数任意正整数进制间的互化
乘n取整
3负数进制：
设计一个程序，读入一个十进制数的基数和一个负进制数的基数，并将此十进制数转换为此负 进制下的数：-R∈{-2，-3，-4,....-20}
来自
http://bbs.mydrs.org/dispbbs.asp?boardID=13&ID=5614&page=1
高精度计算
高精度数的定义：
type
hp=array[1..maxlen] of integer;
1．高精度加法
procedure plus ( a,b:hp; var c:hp);
var i,len:integer;
begin
fillchar(c,sizeof(c),0);
if a[0]>b[0] then len:=a[0] else len:=b[0];
for i:=1 to len do begin
inc(c,a+b);
if c>10 then begin dec(c,10); inc(c[i+1]); end; {进位}
end;
if c[len+1]>0 then inc(len);
c[0]:=len;
end;{plus}
2．高精度减法
procedure substract(a,b:hp;var c:hp);
var i,len:integer;
begin
fillchar(c,sizeof(c),0);
if a[0]>b[0] then len:=a[0] else len:=b[0];
for i:=1 to len do begin
inc(c,a-b);
if c<0 then begin inc(c,10);dec(c[i+1]); end;
while (len>1) and (c[len]=0) do dec(len);
c[0]:=len;
end;
3．高精度乘以低精度
procedure multiply(a:hp;b:longint;var c:hp);
var i,len:integer;
begin
fillchar(c,sizeof(c),0);
len:=a[0];
for i:=1 to len do begin
inc(c,a*b);
inc(c[i+1],(a*b) div 10);
c:=c mod 10;
end;
inc(len);
while (c[len]>=10) do begin {处理最高位的进位}
c[len+1]:=c[len] div 10;
c[len]:=c[len] mod 10;
inc(len);
end;
while (len>1) and (c[len]=0) do dec(len); {若不需进位则调整len}
c[0]:=len;
end;{multiply}
4．高精度乘以高精度
procedure high_multiply(a,b:hp; var c:hp}
var i,j,len:integer;
begin
fillchar(c,sizeof(c),0);
for i:=1 to a[0] do
for j:=1 to b[0] do begin
inc(c[i+j-1],a*b[j]);
inc(c[i+j],c[i+j-1] div 10);
c[i+j-1]:=c[i+j-1] mod 10;
end;
len:=a[0]+b[0]+1;
while (len>1) and (c[len]=0) do dec(len);
c[0]:=len;
end;
5．高精度除以低精度
procedure devide(a:hp;b:longint; var c:hp; var d:longint);
{c:=a div b; d:= a mod b}
var i,len:integer;
begin
fillchar(c,sizeof(c),0);
len:=a[0]; d:=0;
for i:=len downto 1 do begin
d:=d*10+a;
c:=d div b;
d:=d mod b;
end;
while (len>1) and (c[len]=0) then dec(len);
c[0]:=len;
end;
6．高精度除以高精度
procedure high_devide(a,b:hp; var c,d:hp);
var
i,len:integer;
begin
fillchar(c,sizeof(c),0);
fillchar(d,sizeof(d),0);
len:=a[0];d[0]:=1;
for i:=len downto 1 do begin
multiply(d,10,d);
d[1]:=a;
while(compare(d,b)>=0) do {即d>=b}
begin
Subtract(d,b,d);
inc(c);
end;
end;
while(len>1)and(c.s[len]=0) do dec(len);
c.len:=len;
end;
六、 树的遍历
1．已知前序中序求后序
procedure Solve(pre,mid:string);
var i:integer;
begin
if (pre='') or (mid='') then exit;
i:=pos(pre[1],mid);
solve(copy(pre,2,i),copy(mid,1,i-1));
solve(copy(pre,i+1,length(pre)-i),copy(mid,i+1,length(mid)-i));
post:=post+pre[1]; {加上根，递归结束后post即为后序遍历}
end;
2．已知中序后序求前序
procedure Solve(mid,post:string);
var i:integer;
begin
if (mid='') or (post='') then exit;
i:=pos(post[length(post)],mid);
pre:=pre+post[length(post)]; {加上根，递归结束后pre即为前序遍历}
solve(copy(mid,1,I-1),copy(post,1,I-1));
solve(copy(mid,I+1,length(mid)-I),copy(post,I,length(post)-i));
end;
3．已知前序后序求中序的一种
function ok(s1,s2:string):boolean;
var i,l:integer; p:boolean;
begin
ok:=true;
l:=length(s1);
for i:=1 to l do begin
p:=false;
for j:=1 to l do
if s1=s2[j] then p:=true;
if not p then begin ok:=false;exit;end;
end;
end;
procedure solve(pre,post:string);
var i:integer;
begin
if (pre='') or (post='') then exit;
i:=0;
repeat
inc(i);
until ok(copy(pre,2,i),copy(post,1,i));
solve(copy(pre,2,i),copy(post,1,i));
midstr:=midstr+pre[1];
solve(copy(pre,i+2,length(pre)-i-1),copy(post,i+1,length(post)-i-1));
end;
七 进制转换
1任意正整数进制间的互化
除n取余
2实数任意正整数进制间的互化
乘n取整
3负数进制：
设计一个程序，读入一个十进制数的基数和一个负进制数的基数，并将此十进制数转换为此负 进制下的数：-R∈{-2，-3，-4,....-20}
kerbcurb 2004-08-16
- 打赏
- 举报
确实如此
因此必须调整进制
因此必须调整进制
gxqcn 2004-08-16
- 打赏
- 举报
to yaos(等待WoW前玩私服吧·无心人):
我曾说过GMP“从其算法的角度考虑应没有绝对的优势”。如果 Maple 9 的运算库是基于 GMP，那么 GMP 可就并不象你所描述那般快了（至少不会超出同类软件一大截）。
对 HugeCalc3.0.0.1 / apfloat2.40 / Mathematica4.0.0.0 / Maple9.50 的对比测试，
可参考本坛帖子：
http://community.csdn.net/Expert/topic/3197/3197332.xml?temp=.9504969
我曾说过GMP“从其算法的角度考虑应没有绝对的优势”。如果 Maple 9 的运算库是基于 GMP，那么 GMP 可就并不象你所描述那般快了（至少不会超出同类软件一大截）。
对 HugeCalc3.0.0.1 / apfloat2.40 / Mathematica4.0.0.0 / Maple9.50 的对比测试，
可参考本坛帖子：
http://community.csdn.net/Expert/topic/3197/3197332.xml?temp=.9504969
gxqcn 2004-08-16
- 打赏
- 举报
Toom-Cook 我曾推导过的，中间需要解一个线性方程组，不是很难。
只是临时结果需/3，如果已实现了karatsuba 及 FFT/FNT，
我个人认为再实现 Toom-Cook 必要性不大。
另，我不明白楼主的karatsuba何以非得将长度补齐为2的整数次幂的形式？
“对n, m如果两个数字相差太大，最好先分段相乘，然后加分段结果”可曾做过实验？
只是临时结果需/3，如果已实现了karatsuba 及 FFT/FNT，
我个人认为再实现 Toom-Cook 必要性不大。
另，我不明白楼主的karatsuba何以非得将长度补齐为2的整数次幂的形式？
“对n, m如果两个数字相差太大，最好先分段相乘，然后加分段结果”可曾做过实验？
programfanny 2004-08-16
- 打赏
- 举报
Mark to study
yaos 2004-08-16
- 打赏
- 举报
Toom-Cook的算法太难懂了
可能暂时要跳过了 ：）
可能暂时要跳过了 ：）
yaos 2004-08-16
- 打赏
- 举报
另外，GMP是大数运行库，不是算法库，看其中的汇编代码
我按照其中思路，写的代码，竟然比人家慢很多
乘法，它是6 Clock / DWORD，我是12
加减更惨，竟然比12还多，它是4
我按照其中思路，写的代码，竟然比人家慢很多
乘法，它是6 Clock / DWORD，我是12
加减更惨，竟然比12还多，它是4
yaos 2004-08-16
- 打赏
- 举报
Toom-Cook 我曾推导过的，中间需要解一个线性方程组，不是很难。
只是临时结果需/3，如果已实现了karatsuba 及 FFT/FNT，
我个人认为再实现 Toom-Cook 必要性不大。
-------------------------------------------------------------
我看到的knuth的算法没有这么简单阿，按速度关系，他处于karatsuba和FFT/FNT中间的位置
应该有必要
另，我不明白楼主的karatsuba何以非得将长度补齐为2的整数次幂的形式？
-----------------------------------------------------------------
为了方便一次次的迭代折半相乘阿，如果不这样子，可能要有数组的重组的额外开销吧
你有更好的方法么？
to yaos(等待WoW前玩私服吧·无心人):
我曾说过GMP“从其算法的角度考虑应没有绝对的优势”。如果 Maple 9 的运算库是基于 GMP，那么 GMP 可就并不象你所描述那般快了（至少不会超出同类软件一大截）。
-----------------------------------------------------------------------------
GMP公认是现在最快的大数运行库
你的测试有一个明显的问题，你只测试的是大数应用的一个很狭窄的方面
很多时候，大数应用主要是大数的模幂运算，比如加密，分解，验证素数
其他应用一般的现实意义不大。
考虑下面的问题
a = 1024位数
b = 1024位数
p = 1024位素数
求 c = a ^ b mod p，这个是很多应用的基础呢（位一般是二进制位）
只是临时结果需/3，如果已实现了karatsuba 及 FFT/FNT，
我个人认为再实现 Toom-Cook 必要性不大。
-------------------------------------------------------------
我看到的knuth的算法没有这么简单阿，按速度关系，他处于karatsuba和FFT/FNT中间的位置
应该有必要
另，我不明白楼主的karatsuba何以非得将长度补齐为2的整数次幂的形式？
-----------------------------------------------------------------
为了方便一次次的迭代折半相乘阿，如果不这样子，可能要有数组的重组的额外开销吧
你有更好的方法么？
to yaos(等待WoW前玩私服吧·无心人):
我曾说过GMP“从其算法的角度考虑应没有绝对的优势”。如果 Maple 9 的运算库是基于 GMP，那么 GMP 可就并不象你所描述那般快了（至少不会超出同类软件一大截）。
-----------------------------------------------------------------------------
GMP公认是现在最快的大数运行库
你的测试有一个明显的问题，你只测试的是大数应用的一个很狭窄的方面
很多时候，大数应用主要是大数的模幂运算，比如加密，分解，验证素数
其他应用一般的现实意义不大。
考虑下面的问题
a = 1024位数
b = 1024位数
p = 1024位素数
求 c = a ^ b mod p，这个是很多应用的基础呢（位一般是二进制位）
yaos 2004-08-15
- 打赏
- 举报
karatsuba乘法
n 位 u 乘 m 位 v的算法
对n, m如果两个数字相差太大，最好先分段相乘，然后加分段结果
如果n, m比不超过2，max = max(n, m)为n, m中最大值
寻找 2 ^ k >= m > 2 ^ (k - 1)
u, v前面补0 形成 l = 2 ^ k位数字U V
U = U0 + b ^ (l / 2) * U1
V = V0 + b ^ (l / 2) * V1
执行下面算法
C0 = U0 * V0
C1 = U1 * V1
C2 = (U0 - U1) * (V1 - V0) + C0 + C1
则 W = C0 + b ^ l * C1 + b ^ (l / 2) * C2
循环递归采用karatsuba算法，直到 l 小到karatsuba算法比普通乘法速度慢的时候，改普通算法计算乘积
(U0 - U1) * (V1 - V0)可能是负的，但是容易用递归的karatsuba计算
n 位 u 乘 m 位 v的算法
对n, m如果两个数字相差太大，最好先分段相乘，然后加分段结果
如果n, m比不超过2，max = max(n, m)为n, m中最大值
寻找 2 ^ k >= m > 2 ^ (k - 1)
u, v前面补0 形成 l = 2 ^ k位数字U V
U = U0 + b ^ (l / 2) * U1
V = V0 + b ^ (l / 2) * V1
执行下面算法
C0 = U0 * V0
C1 = U1 * V1
C2 = (U0 - U1) * (V1 - V0) + C0 + C1
则 W = C0 + b ^ l * C1 + b ^ (l / 2) * C2
循环递归采用karatsuba算法，直到 l 小到karatsuba算法比普通乘法速度慢的时候，改普通算法计算乘积
(U0 - U1) * (V1 - V0)可能是负的，但是容易用递归的karatsuba计算
yaos 2004-08-15
- 打赏
- 举报
普通n 位 u 乘 m 位 v的算法在 n, m很大时就会很慢
有下面的几个快速算法
1、karatsuba算法
2、Toom-Hook算法
3、模算法
4、FFT快速复数富利叶变换算法
5、FFT快速整数富利叶变换算法
6、FNT快速数论变换算法
有下面的几个快速算法
1、karatsuba算法
2、Toom-Hook算法
3、模算法
4、FFT快速复数富利叶变换算法
5、FFT快速整数富利叶变换算法
6、FNT快速数论变换算法
yaos 2004-08-15
- 打赏
- 举报
否则，你的算法出现溢出
yaos 2004-08-15
- 打赏
- 举报
前提条件：
你计算机内部进制 B > max(m, n) * b ^ 2
你计算机内部进制 B > max(m, n) * b ^ 2
kerbcurb 2004-08-15
- 打赏
- 举报
乘法有这样一种好理解的：
c = a * b
1)数组c全部置零
2）
for(i = 0;i < n;i++)
for(j = 0;j < m;j++)
c[i + j] += a[i] * b[j];
3）规整c的进位
c = a * b
1)数组c全部置零
2）
for(i = 0;i < n;i++)
for(j = 0;j < m;j++)
c[i + j] += a[i] * b[j];
3）规整c的进位
yaos 2004-08-15
- 打赏
- 举报
修改一下
普通n 位 u 乘 m 位 v的算法在 n, m很大时就会很慢
有下面的几个快速算法
1、karatsuba算法
2、Toom-Cook算法
3、模算法
4、FFT快速复数富利叶变换算法（包括扩展精度直到能计算几乎任何长度的算法）
5、FFT快速整数富利叶变换算法
6、FNT快速数论变换算法
karatsuba乘法
n 位 u 乘 m 位 v的算法
对n, m如果两个数字相差太大，最好先分段相乘，然后加分段结果
如果n, m比不超过2，max = max(n, m)为n, m中最大值
寻找 2 ^ k >= max > 2 ^ (k - 1)
u, v前面补0 形成 l = 2 ^ k位数字U V
U = U0 + b ^ (l / 2) * U1
V = V0 + b ^ (l / 2) * V1
执行下面算法
C0 = U0 * V0
C1 = U1 * V1
C2 = (U0 - U1) * (V1 - V0) + C0 + C1
则 W = C0 + b ^ l * C1 + b ^ (l / 2) * C2
拷贝W 中 0 .. n + m - 1 到 w
循环递归采用karatsuba算法，直到 l 小到karatsuba算法比普通乘法速度慢的时候，改普通算法计算乘积
(U0 - U1) * (V1 - V0)可能是负的，但是容易用递归的karatsuba计算
普通n 位 u 乘 m 位 v的算法在 n, m很大时就会很慢
有下面的几个快速算法
1、karatsuba算法
2、Toom-Cook算法
3、模算法
4、FFT快速复数富利叶变换算法（包括扩展精度直到能计算几乎任何长度的算法）
5、FFT快速整数富利叶变换算法
6、FNT快速数论变换算法
karatsuba乘法
n 位 u 乘 m 位 v的算法
对n, m如果两个数字相差太大，最好先分段相乘，然后加分段结果
如果n, m比不超过2，max = max(n, m)为n, m中最大值
寻找 2 ^ k >= max > 2 ^ (k - 1)
u, v前面补0 形成 l = 2 ^ k位数字U V
U = U0 + b ^ (l / 2) * U1
V = V0 + b ^ (l / 2) * V1
执行下面算法
C0 = U0 * V0
C1 = U1 * V1
C2 = (U0 - U1) * (V1 - V0) + C0 + C1
则 W = C0 + b ^ l * C1 + b ^ (l / 2) * C2
拷贝W 中 0 .. n + m - 1 到 w
循环递归采用karatsuba算法，直到 l 小到karatsuba算法比普通乘法速度慢的时候，改普通算法计算乘积
(U0 - U1) * (V1 - V0)可能是负的，但是容易用递归的karatsuba计算
