异步计算斐波那契数列大数值项(千万数级)的值

简介: 异步计算斐波那契数列大数值项(千万数级)的值

image.png

异步编程

异步计算斐波那契数列,半分钟可以计算出第5000万项的数值。

完整代码

import sys, time, asyncio
 
def timer(func):  
    def wrapper(*args, **kwargs):  
        start_time = time.time()  
        result = func(*args, **kwargs)  
        end_time = time.time()  
        print(f"{func.__name__} took {end_time - start_time} seconds to run.")  
        return result  
    return wrapper
 
def fib(n):
    if n<600:
        n1 = n2 = 1
        for _ in range(2,n):
            n1,n2 = n1+n2,n1
        return n1
    t = n//2
    if n%2:
        return fib(t+1)**2 + fib(t)**2
    else:
        return fib(t+1)**2 - fib(t-1)**2
 
@timer
def Fib(n):
    return fib(n)
 
async def asyncFib(n):
    res = Fib(n)
    print(res)
 
async def main():
    await asyncio.gather(*tasks)
 
if __name__ == "__main__":
    sys.set_int_max_str_digits(0)
    parms = [5000_0000, 2000_0000, 1000_0000]
    tasks = [asyncFib(p) for p in parms]
    loop = asyncio.run(main())

输出结果

Fib took 24.186946153640747 seconds to run.
Squeezed text(121505 lines).
Fib took 5.968385457992554 seconds to run.
Squeezed text(121505 lines).
Fib took 2.031674385070801 seconds to run.
Squeezed text(121505 lines).
Fib took 0.0 seconds to run.
33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875

代码分析

耗时装饰器

def timer(func):  
    def wrapper(*args, **kwargs):  
        start_time = time.time()  
        result = func(*args, **kwargs)  
        end_time = time.time()  
        print(f"{func.__name__} took {end_time - start_time} seconds to run.")  
        return result  
    return wrapper

@timer
def Fib(n):
    return fib(n)

斐波那契数列

def fib(n):
    if n<600:
        n1 = n2 = 1
        for _ in range(2,n):
            n1,n2 = n1+n2,n1
        return n1
    t = n//2
    if n%2:
        return fib(t+1)**2 + fib(t)**2
    else:
        return fib(t+1)**2 - fib(t-1)**2

使用以下两个恒等式可快速缩小fib()函数的参数值,极大效率地减少fib函数的递归次数:

fib(2*t+1)=fib(t+1)**2 + fib(t)**2

fib(2*t)=fib(t+1)**2 - fib(t-1)**2

异步函数

async def asyncFib(n):
    res = Fib(n)
    print(res)

async def main():
    await asyncio.gather(*tasks)

设置字串处理的最大位数

sys.set_int_max_str_digits(0)

新版python默认只能最大处理4300位的字串,参数为0即解除长度限制。也可以设置具体数据为限制最长长度,比如sys.set_int_max_str_digits(10000),注意本例中fib(5000_0000)的值有几千万位,需要设置1亿位sys.set_int_max_str_digits(1_0000_0000)。如设置的位数不够会报错:ValueError: Exceeds the limit (10000 digits) for integer string conversion; use sys.set_int_max_str_digits() to increase the limit


目录
相关文章
|
6月前
|
存储 编译器 C++
在C++语言中计算并打印出两个数的求和
在C++语言中计算并打印出两个数的求和
289 0
|
6月前
|
Python
异步计算斐波那契数列大数值项(千万数级)的值
异步计算斐波那契数列,半分钟可以计算出第5000万项的数值。
63 0
定义求x的n次幂的函数,并返回计算结果
定义求x的n次幂的函数,并返回计算结果
题目:编写函数fun其功能是:根据整型形参m,计算如下公式的值:y=12!+14!+…+1m!(m是偶数)
题目:编写函数fun其功能是:根据整型形参m,计算如下公式的值:y=12!+14!+…+1m!(m是偶数)
258 0
wustojc4010按公式计算y和z的值
wustojc4010按公式计算y和z的值
95 0
|
Serverless
编写函数计算多项式的值
编写函数计算多项式的值
|
人工智能 Unix BI
1370:最小函数值(minval)
1370:最小函数值(minval)
|
C++
C++ 计算斐波那契数列第100万项的精确整数值
C++ 计算斐波那契数列第100万项的精确整数值
111 0
|
存储
使用程序计算近似Π值
现在大多数语言,只需要调用一下Math.PI就可以知道Π值了。但是你有没有想过这个PI是怎么来的,是直接存储吗?还是计算来的。虽然不知道具体是怎么实现的,但是我们可以使用一些简单的数学知识,来计算出近似的Π值。
191 0