标题:在Python中如何写一个大整数的快速乘法程序
只看楼主
ysr2857
Rank: 6Rank: 6
等 级:贵宾
威 望:28
帖 子:767
专家分:65
注 册:2020-2-10
结帖率:100%
 问题点数:0 回复次数:25 
在Python中如何写一个大整数的快速乘法程序
如下为vb代码:
Public Function MbC(D1 As String, D2 As String) As String
Dim j1&, j2&, e&, d&, e1&

   ' 按列法计算C=A*B
m = Trim(D1): n = Trim(D2)
x = Len(m) \ 4: Y = Len(n) \ 4
m = String(4 * x + 4 - Len(m), "0") & m
n = String(4 * Y + 4 - Len(n), "0") & n
x = x + 1: Y = Y + 1
Dim A(), B()
ReDim A(1 To x): ReDim B(1 To Y)
For i1 = 1 To x
A(i1) = Val(Mid(m, i1 * 4 - 3, 4))
Next
For i2 = 1 To Y
B(i2) = Val(Mid(n, i2 * 4 - 3, 4))
Next
ma = x: mb = Y
    MC = ma + mb
    ReDim c(MC)
    e1 = 0
    j1 = ma: j2 = ma
    For I = MC To 2 Step -1
        If I <= ma Then j2 = I - 1
        e = e1: e1 = 0
        For J = j1 To j2
            e = e + A(J) * B(I - J)
            If e > 2040000000 Then '减少进位次数
                e = e - 2040000000
                e1 = e1 + 204000
            End If
        Next J

        If j1 > 1 Then j1 = j1 - 1
base = 10000
        d = e \ base
        c(I) = e - d * base
        If Len(c(I)) < 4 Then
        c(I) = String(4 - Len(c(I)), "0") & c(I)
        Else
        c(I) = c(I)
        End If
jc = c(I) & jc
        e1 = e1 + d
    Next I
    jc = d & jc
   MbC = qqdl(Trim(jc))
End Function

这个程序算几十万位的两个数的乘法得3个小时,太慢了!
搜索更多相关主题的帖子: If String Next For Then 
2022-06-27 10:53
ysr2857
Rank: 6Rank: 6
等 级:贵宾
威 望:28
帖 子:767
专家分:65
注 册:2020-2-10
得分:0 
判断素数的程序

Python代码:

from math import sqrtdef is_prime(n):    if n == 1:        return False    for i in range(2, int(sqrt(n))+1):        if n % i == 0:            return False    return True

这个程序对吗?
2022-12-14 17:37
mrexcel
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:22
帖 子:125
专家分:480
注 册:2022-11-3
得分:0 
以下是引用ysr2857在2022-12-14 17:37:10的发言:

判断素数的程序

Python代码:

from math import sqrtdef is_prime(n):    if n == 1:        return False    for i in range(2, int(sqrt(n))+1):        if n % i == 0:            return False    return True

这个程序对吗?

没有测试,感觉至少2会出问题。return False之后加一行break

可以直接引用sympy库 from sympy import isprime
2022-12-16 16:01
mrexcel
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:22
帖 子:125
专家分:480
注 册:2022-11-3
得分:0 
几十万位的两个数的乘法得3个小时?

什么算法也快不到哪里去,几千亿位的结果存储是个大问题,有什么意义呢?
2022-12-16 16:05
mrexcel
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:22
帖 子:125
专家分:480
注 册:2022-11-3
得分:0 
以下是引用ysr2857在2022-12-14 17:37:10的发言:

判断素数的程序

Python代码:

from math import sqrtdef is_prime(n):    if n == 1:        return False    for i in range(2, int(sqrt(n))+1):        if n % i == 0:            return False    return True

这个程序对吗?


你的代码测试通过,可以不引用math库。
程序代码:
def is_prime(n): 
    if n == 1: 
        return False 
    for i in range(2,int(n**0.5+1)):
        if n % i == 0:  
            return False  
    return True

print([n for n in range(1,100) if is_prime(n)])


或者通过忽略偶数,减少循环进行优化,如:
程序代码:
def is_prime(n): 
    if n == 1 or (n%2==0 and n>2): 
        return False 
    for i in range(3,int(n**0.5+1),2):
        if n % i == 0:  
            return False  
    return True

print([n for n in range(1,100) if is_prime(n)])

2022-12-16 23:29
ysr2857
Rank: 6Rank: 6
等 级:贵宾
威 望:28
帖 子:767
专家分:65
注 册:2020-2-10
得分:0 
回复 5楼 mrexcel
谢谢老师指导!对于Python语言我是菜鸟一点儿不懂,我仅仅会一点VB语句。

非常感谢!

判断大整数是否素数,我用欧拉原理(欧拉定理和推论)编程的VB代码,经过优化后可以在3秒内判断一个100多位的大素数。如果用Python再快点儿就可以用来搜索巨大的孪生素数,甚至可以破解世界纪录。
2022-12-17 04:52
ysr2857
Rank: 6Rank: 6
等 级:贵宾
威 望:28
帖 子:767
专家分:65
注 册:2020-2-10
得分:0 
任何数学规律都是有价值的可以用于实际的,素数的一些规律(差定理和和定理就是哥德巴赫猜想等),起码有助于我们快速找到我们需要的巨大的素数或孪生素数,当然还要结合其他技术知识如计算大整数的快速程序,下面这对大孪生素数就是应用前面的规律找到的:

1000002100内有1组3生素数:
1000001329,9173994463960286046443283581208347763186259956673124494950355357547691504353939232280074212440503746219891,9173994463960286046443283581208347763186259956673124494950355357547691504353939232280074212440503746219893,4n+2=9173994463960286046443283581208347763186259956673124494950355357547691504353939232280074212440502746218562(含有一对106位的孪生素数)——
用时9692.083秒
2022-12-17 04:59
ysr2857
Rank: 6Rank: 6
等 级:贵宾
威 望:28
帖 子:767
专家分:65
注 册:2020-2-10
得分:0 
20000与21000之间的素数打头有1组差为1606938044258990275541962092341162602522202993782792835301376和2的整数加孪生素数对: (用时682.9688秒)
//20593/1606938044258990275541962092341162602522202993782792835321969/1606938044258990275541962092341162602522202993782792835321971

这是一对61位的孪生素数
2022-12-17 05:30
mrexcel
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:22
帖 子:125
专家分:480
注 册:2022-11-3
得分:0 
以下是引用ysr2857在2022-6-27 10:53:45的发言:

如下为vb代码:
Public Function MbC(D1 As String, D2 As String) As String
Dim j1&, j2&, e&, d&, e1&

   ' 按列法计算C=A*B
m = Trim(D1): n = Trim(D2)
x = Len(m) \ 4: Y = Len(n) \ 4
m = String(4 * x + 4 - Len(m), "0") & m
n = String(4 * Y + 4 - Len(n), "0") & n
x = x + 1: Y = Y + 1
Dim A(), B()
ReDim A(1 To x): ReDim B(1 To Y)
For i1 = 1 To x
A(i1) = Val(Mid(m, i1 * 4 - 3, 4))
Next
For i2 = 1 To Y
B(i2) = Val(Mid(n, i2 * 4 - 3, 4))
Next
ma = x: mb = Y
    MC = ma + mb
    ReDim c(MC)
    e1 = 0
    j1 = ma: j2 = ma
    For I = MC To 2 Step -1
        If I <= ma Then j2 = I - 1
        e = e1: e1 = 0
        For J = j1 To j2
            e = e + A(J) * B(I - J)
            If e > 2040000000 Then '减少进位次数
                e = e - 2040000000
                e1 = e1 + 204000
            End If
        Next J

        If j1 > 1 Then j1 = j1 - 1
base = 10000
        d = e \ base
        c(I) = e - d * base
        If Len(c(I)) < 4 Then
        c(I) = String(4 - Len(c(I)), "0") & c(I)
        Else
        c(I) = c(I)
        End If
jc = c(I) & jc
        e1 = e1 + d
    Next I
    jc = d & jc
   MbC = qqdl(Trim(jc))
End Function

这个程序算几十万位的两个数的乘法得3个小时,太慢了!


MbC = qqdl(Trim(jc)),qqdl是个什么函数?
2022-12-17 14:09
mrexcel
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:22
帖 子:125
专家分:480
注 册:2022-11-3
得分:0 
Python支持大数直接运算,做数论的东西,还是建议选择Python 或 Mathematica 或者 Pari
2022-12-17 14:11



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




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

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