| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 6044 人关注过本帖
标题:求助:如何把利用快速傅里叶变换的大数乘法变成vb程序?
只看楼主 加入收藏
风吹过b
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:贵宾
威 望:364
帖 子:4947
专家分:30084
注 册:2008-10-15
收藏
得分:0 
稍微搜索了一下 大数乘法,
搜到了就是 五种算法:
1、模拟小学乘法:最简单的乘法竖式手算的累加型;
2、分治乘法:最简单的是Karatsuba乘法,一般化以后有Toom-Cook乘法;
3、快速傅里叶变换FFT:(为了避免精度问题,可以改用快速数论变换FNTT),时间复杂度O(N lgN lglgN)。具体可参照Schönhage–Strassen algorithm;
4、中国剩余定理:把每个数分解到一些互素的模上,然后每个同余方程对应乘起来就行;
5、Furer’s algorithm:在渐进意义上FNTT还快的算法。不过好像不太实用,本文就不作介绍了。大家可以参考维基百科Fürer’s algorithm

然后看了一介绍,Java 中,采用的是
用二重循环直接相乘
采用 Karatsuba algorithm
采用 Toom-Cook multiplication

然后看了一下,竟然是数论。好吧,我根本看不懂。
按java的算法类型,建议你照着 Karatsuba 乘法 去写吧!数位不够时,可以使用递归就是了。

或者你去翻译:GMP(The GNU MP Bignum Library)。这里面有你所需要的算法,不过是 C++ 的。

附:找到的 Karatsuba 算法, C++ 的,稍微琢磨了一下,估计要先写一个大数加减法的。主要是看不太懂。
程序代码:
/**

 * Karatsuba乘法

 */
public static long karatsuba(long num1, long num2){
    //递归终止条件
    if(num1 < 10 || num2 < 10) return num1 * num2;

    // 计算拆分长度
    int size1 = String.valueOf(num1).length();
    int size2 = String.valueOf(num2).length();
    int halfN = Math.max(size1, size2) / 2;

    /* 拆分为a, b, c, d */
    long a = Long.valueOf(String.valueOf(num1).substring(0, size1 - halfN));
    long b = Long.valueOf(String.valueOf(num1).substring(size1 - halfN));
    long c = Long.valueOf(String.valueOf(num2).substring(0, size2 - halfN));
    long d = Long.valueOf(String.valueOf(num2).substring(size2 - halfN));

    // 计算z2, z0, z1, 此处的乘法使用递归
    long z2 = karatsuba(a, c);
    long z0 = karatsuba(b, d);
    long z1 = karatsuba((a + b), (c + d)) - z0 - z2;

    return (long)(z2 * Math.pow(10, (2*halfN)) + z1 * Math.pow(10, halfN) + z0);
}




--------------------
最后,我决定我再不关注这个贴子了,看不懂。

[此贴子已经被作者于2020-9-15 21:36编辑过]


授人于鱼,不如授人于渔
早已停用QQ了
2020-09-15 21:35
ysr2857
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:34
帖 子:809
专家分:77
注 册:2020-2-10
收藏
得分:0 
谢谢关注和指导!这些东西很重要,我好好学习一下,感觉还是快速傅里叶变换或数论变换最快,都需要学习,我也是不懂,谢谢您!
2020-09-15 23:06
ysr2857
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:34
帖 子:809
专家分:77
注 册:2020-2-10
收藏
得分:0 
ω是如何计算的呢?
为了计算离散傅里叶变换,我们令:
ω = e^(-2πi/N )= e^(-2πi/8) = e^(-πi/4) = cos(-π/4) + i sin(-π/4) = √2 / 2 - i √2 / 2 ≈ 0.7-0.7i
而ω^0~ω^8都以此为基础,以此类推,如ω^0=e^0=1,
ω^1=e^(-πi/4) = cos(-π/4) + i sin(-π/4) = √2 / 2 - i √2 / 2 ≈ 0.7-0.7i,
ω^2=e^(-πi/2)=0+i*(-1)=-i,
……。

[此贴子已经被作者于2020-10-9 23:21编辑过]

2020-10-09 17:47
ysr2857
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:34
帖 子:809
专家分:77
注 册:2020-2-10
收藏
得分:0 
ω是如何计算的呢?
为了计算离散傅里叶变换,如当N=8时,我们令:
ω = e^(-2πi/N )= e^(-2πi/8) = e^(-πi/4) = cos(-π/4) + i sin(-π/4) = √2 / 2 - i √2 / 2 ≈ 0.7-0.7i
而ω^0~ω^8都以此为基础,以此类推,如ω^0=e^0=1,
ω^1=e^(-πi/4) = cos(-π/4) + i sin(-π/4) = √2 / 2 - i √2 / 2 ≈ 0.7-0.7i,
ω^2=e^(-πi/2)=0+i*(-1)=-i,
……。

[此贴子已经被作者于2020-10-9 23:22编辑过]

2020-10-09 17:49
ysr2857
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:34
帖 子:809
专家分:77
注 册:2020-2-10
收藏
得分:0 
总计进行了两次快速傅里叶变换(被乘数和乘数各一次),得到:
{ A7, A6, A5, A4, A3, A2, A1, A0 } = { 12.9+10.9i, 2+7i, 3.1-1.1i, 7, 3.1+1.1i, 2-7i, 12.9-10.9i, 21 }
{ B7, B6, B5, B4, B3, B2, B1, B0 } = { 4.1+6.1i, -2+3i, -0.1-1.9i, 3, -0.1+1.9i, -2-3i, 4.1-6.1i, 9 }

一次对应项相乘,得到向量 {Ck},即 { C7, C6, C5, C4, C3, C2, C1, C0 }
= { -13.6+123.4i, -25-8i, -2.4-5.8i, 21, -2.4+5.8i, -25+8i, -13.6-123.4i, 189 }

一次逆变换计算出了向量 {ai} 和向量 {bj} 的卷积向量 {ck},如下所示:
{ c7, c6, c5, c4, c3, c2, c1, c0 } = { 0, 0, 0, 0, 24, 46, 65, 38, 16 }

最后错位相加得到结果。
2020-10-09 18:14
ysr2857
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:34
帖 子:809
专家分:77
注 册:2020-2-10
收藏
得分:0 
例如如下向量:
{ A7, A6, A5, A4, A3, A2, A1, A0 } = { 12.9+10.9i, 2+7i, 3.1-1.1i, 7, 3.1+1.1i, 2-7i, 12.9-10.9i, 21 }
显然以7为对称中心,对称项都是共轭复数,只有7和21是不对称的,如何快速得到?
先得到7,还是先得到 3.1+1.1i?然后由对称性和其它算法(而不再进行乘法)推演出来其他项?
2020-10-23 18:50
ysr2857
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:34
帖 子:809
专家分:77
注 册:2020-2-10
收藏
得分:0 
改造后的蝶形运算程序和结果:
Private Sub Command1_Click()
Dim xr() As Double, a As String
a = Trim(Text1)
ReDim xr(0 To Len(a) - 1)
For i1 = 0 To Len(a) - 1
xr(i1) = Mid(a, i1 + 1, 1)
  Next
Dim l As Long, le As Long, le1 As Long, n As Long, r As Long, p As Long, q As Long, m As Byte
Dim wr As Double, w1 As Double, wlr As Double, wl1 As Double, tr As Double, t1 As Double
Dim pi As Double, t As Double
Dim xi()
n = Len(a) '求数组大小,其值必须是2的幂
m = 0
l = 2
pi = 3.14159265358979
Do
 l = l + l
 m = m + 1
 Loop Until l > n
 n = l / 2
ReDim xi(n - 1)

l = 1
Do
  le = 2 ^ l
  le1 = le / 2
  wr = 1
  wi = 0
  w1r = Cos(t)
  w1i = -Sin(t)
  r = 0
Do
  p = r
  Do
   q = p + le1
   
   tr = xr(q) * wr - xi(q) * wi
   ti = xr(q) * wi + xi(q) * wr
   
   xr(q) = xr(p) - tr
   xi(q) = xi(p) - ti
   xr(p) = xr(p) + tr
   xi(p) = xi(p) + ti
   
   p = p + le
Loop Until p > n - 1

wr = wr * w1r - wi * w1i
wi = wr * w1i - wi * w1r
r = r + 1
Loop Until r > le1 - 1
l = l + 1
Loop Until l > m

For i = 0 To n - 1 '仅输出模
   xr(i) = Sqr(xr(i) ^ 2 + xi(i) ^ 2)
   Text2 = Text2 & "  " & xr(i)
   Next
End Sub

Private Sub Command2_Click()
Text1 = ""
Text2 = ""
End Sub
运算结果:
Text1=00000678,Text2=21  7  9  5  21  7  9  5,
Text1=00000432,Text2=  9  3  1  5  9  3  1  5.
2020-12-24 21:04
ysr2857
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:34
帖 子:809
专家分:77
注 册:2020-2-10
收藏
得分:0 
程序出现了错误,怪不得了呀,修改了一下,如下为代码和计算结果:
Private Sub Command1_Click()
Dim xr() As Double, a As String
a = Trim(Text1)
ReDim xr(0 To Len(a) - 1)
For i1 = 0 To Len(a) - 1
xr(i1) = Mid(a, i1 + 1, 1)
  Next
Dim l As Long, le As Long, le1 As Long, n As Long, r As Long, p As Long, q As Long, m As Byte
Dim wr As Double, w1 As Double, wlr As Double, wl1 As Double, tr As Double, t1 As Double
Dim pi As Double, t As Double
Dim xi()
n = Len(a) '求数组大小,其值必须是2的幂
m = 0
l = 2
pi = 3.14159265358979
Do
 l = l + l
 m = m + 1
 Loop Until l > n
 n = l / 2
ReDim xi(n - 1)

l = 1
Do
  le = 2 ^ l
  le1 = le / 2
  wr = 1
  wi = 0
  t = pi / le1
  w1r = Cos(t)
  w1i = -Sin(t)
  r = 0
Do
  p = r
  Do
   q = p + le1
   
   tr = xr(q) * wr - xi(q) * wi
   ti = xr(q) * wi + xi(q) * wr
   
   xr(q) = xr(p) - tr
   xi(q) = xi(p) - ti
   xr(p) = xr(p) + tr
   xi(p) = xi(p) + ti
   p = p + le
Loop Until p > n - 1

wr = wr * w1r - wi * w1i
wi = wr * w1i - wi * w1r
r = r + 1
Loop Until r > le1 - 1
l = l + 1
Loop Until l > m

For i = 0 To n - 1 '仅输出模
   xr(i) = Sqr(xr(i) ^ 2 + xi(i) ^ 2)
   Text2 = Text2 & "  " & xr(i)
   Next
End Sub

Private Sub Command2_Click()
Text1 = ""
Text2 = ""
End Sub
计算结果:
Text1=00000678,Text2= 21  5.19615242270664  2.60761871483253  2.80919177949488  21  5.19615242270664  2.60761871483253  2.80919177949488.
2020-12-24 23:59
ysr2857
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:34
帖 子:809
专家分:77
注 册:2020-2-10
收藏
得分:0 
改造后输出复数的蝶形运算程序代码及结果:
Private Sub Command1_Click()
Dim xr() As Double, a As String
a = Trim(Text1)
ReDim xr(0 To Len(a) - 1)
For i1 = 0 To Len(a) - 1
xr(i1) = Mid(a, i1 + 1, 1)
  Next
Dim l As Long, le As Long, le1 As Long, n As Long, r As Long, p As Long, q As Long, m As Byte
Dim wr As Double, w1 As Double, wlr As Double, wl1 As Double, tr As Double, t1 As Double
Dim pi As Double, t As Double
Dim xi()
n = Len(a) '求数组大小,其值必须是2的幂
m = 0
l = 2
pi = 3.14159265358979
Do
 l = l + l
 m = m + 1
 Loop Until l > n
 n = l / 2
ReDim xi(n - 1)

l = 1
Do
  le = 2 ^ l
  le1 = le / 2
  wr = 1
  wi = 0
  t = pi / le1
  w1r = Cos(t)
  w1i = -Sin(t)
  r = 0
Do
  p = r
  Do
   q = p + le1
   
   tr = xr(q) * wr - xi(q) * wi
   ti = xr(q) * wi + xi(q) * wr
   
   xr(q) = xr(p) - tr
   xi(q) = xi(p) - ti
   xr(p) = xr(p) + tr
   xi(p) = xi(p) + ti
   p = p + le
Loop Until p > n - 1

wr = wr * w1r - wi * w1i
wi = wr * w1i - wi * w1r
r = r + 1
Loop Until r > le1 - 1
l = l + 1
Loop Until l > m

For i = 0 To n - 1 '仅输出模
   
   Text2 = Text2 & "  " & xr(i) & "+" & xi(i) & "i"
   Next
End Sub

Private Sub Command2_Click()
Text1 = ""
Text2 = ""
End Sub
计算结果:
Text1=00000678,Text2= 21+0i  -4.24264068711929+3i  -1.31801948466055+-2.25i  -1.68198051533947+2.25i  -21+0i  4.24264068711929+-3i  1.31801948466055+2.25i  1.68198051533947+-2.25i
2020-12-25 00:04
ysr2857
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:34
帖 子:809
专家分:77
注 册:2020-2-10
收藏
得分:0 
跟前面的例子比较如下:
 21+0i  -4.24264068711929+3i  -1.31801948466055+-2.25i  -1.68198051533947+2.25i  -21+0i  4.24264068711929+-3i  1.31801948466055+2.25i  1.68198051533947+-2.25i

 12.9+10.9i, 2+7i, 3.1-1.1i, 7, 3.1+1.1i, 2-7i, 12.9-10.9i, 21

不一样,咋回事呢?希望老师指点!谢谢!
2020-12-25 00:12
快速回复:求助:如何把利用快速傅里叶变换的大数乘法变成vb程序?
数据加载中...
 
   



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

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