User avatar
HermannSW
Posts: 4130
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany
Contact: Website Twitter YouTube

builtin µs timing code made platform independent (Python[23] / Pico MicroPython)

Wed May 12, 2021 8:08 am

In order to achieve what title states, I needed something to measure that scales. I did choose N-th Fibonacci number, which is no problem despite being very big because of "(Micro)?Python" 's arbitrary precision integer arithmetic.

Recently I posted fibmod.py, that did compute N-th Fibonacci number "mod m":
https://gist.github.com/Hermann-SW/7e99 ... 0d01c6e819
For constant m runtime of that algorithm is linear in input size "log(N)", find analysis here:
https://pbs.twimg.com/media/E0-R4imXsAA ... name=large

Yesterday I removed the "mod m" specific code, so N-th Fibonacci number can be computed with log(N) recursive calls. Because F(n)=round(phi**N/sqrt(5)) with phi=(sqrt(5)+1)/2, the result (binary) length is roughly 1.618*n bits, which is exponential in (binary) input size log(N):
https://gist.github.com/Hermann-SW/caa1 ... 124bf773a5


For timing I realized that Python[23] provides timeit module with builtin "default_timer()" function, returning µs precision timestamp as (second unit) float. Pico MicroPython provides time module builtin function "ticks_us" returning µs timestamp as integer. I learned how to eliminate that detail using "from ... import ... as ...", and using platform dependent new function "delta(t0,t1)" to deal with float/integer timestamps of the different platforms (to output µs integer timestamp delta):

Code: Select all

from sys import platform

if platform=='rp2':
    from time import ticks_us as default_timer
    def delta(t0,t1):
        return t1-t0
else:
    from timeit import default_timer
    def delta(t0,t1):
        return int(1000000*(t1-t0)+0.5)

Next, this is fast computation of tuple (F(n),F(n+1)) with only log(n) recursive calls:

Code: Select all

def calc(t, odd):
    return ((t[1]**2 +     t[0]**2   ), (t[1]**2 + 2*t[0]*t[1])) if odd\
      else ((t[1]**2 - (t[1]-t[0])**2), (t[1]**2 +   t[0]**2  ))

def fib(n):
    if n==0:
        return (0, 1)
    elif n==1:
        return (1, 1)
    else:
        return calc(fib(n//2), n%2 == 1)

"Ffast(n)" computes N-th Fibonacci number fast, whereas "F(n)" computes it traditionally with N additions:

Code: Select all

def Ffast(n):
    return fib(n)[0]

def F(n):
    a=0
    b=1
    for i in range(0,n):
        n=a+b
        a=b
        b=n
    return a

"tst(n)" computes F(n-9)..F(n) and does compute runtimes for standard and fast computation. 2nd arg selects whether to output F(n) itself (default), or just the number of decimal digits. The final print outputs the microseconds for two consecutive timestamps, single digit for builtin functions on all platforms:

Code: Select all

def tst(N, pF=True):
    for n in range(N-9, 1+N):
        start=default_timer()
        r=F(n)
        stop=default_timer()
        r2=Ffast(n)
        stop2=default_timer()
        print(r if pF else len(str(r)), delta(start,stop), r==r2, delta(stop,stop2))

print(delta(default_timer(),default_timer()))

Here is 1st example with output of Fibonacci numbers for comptation of F(341)..F(350):

Code: Select all

pi@raspberrypi4B:~ $ python -c "import fib; fib.tst(350)"
3
(82281144336295989585340713815384441479925901307982452831610787275979941L, 216, True, 103)
(133133688169362819419341682354326791750874517270785300499298099495818696L, 205, True, 89)
(215414832505658809004682396169711233230800418578767753330908886771798637L, 203, True, 81)
(348548520675021628424024078524038024981674935849553053830206986267617333L, 203, True, 88)
(563963353180680437428706474693749258212475354428320807161115873039415970L, 202, True, 83)
(912511873855702065852730553217787283194150290277873860991322859307033303L, 205, True, 85)
(1476475227036382503281437027911536541406625644706194668152438732346449273L, 202, True, 81)
(2388987100892084569134167581129323824600775934984068529143761591653482576L, 203, True, 84)
(3865462327928467072415604609040860366007401579690263197296200323999931849L, 204, True, 80)
(6254449428820551641549772190170184190608177514674331726439961915653414425L, 204, True, 81)
pi@raspberrypi4B:~ $ 

Here is same output in Pico MicroPython (minicom) REPL:

Code: Select all

>>> fib.tst(350)                                                                             
82281144336295989585340713815384441479925901307982452831610787275979941 5297 True 1240       
133133688169362819419341682354326791750874517270785300499298099495818696 5283 True 1185      
215414832505658809004682396169711233230800418578767753330908886771798637 5295 True 1128      
348548520675021628424024078524038024981674935849553053830206986267617333 5313 True 1247      
563963353180680437428706474693749258212475354428320807161115873039415970 5326 True 1210      
912511873855702065852730553217787283194150290277873860991322859307033303 5343 True 1205      
1476475227036382503281437027911536541406625644706194668152438732346449273 12296 True 1159    
2388987100892084569134167581129323824600775934984068529143761591653482576 5377 True 1221     
3865462327928467072415604609040860366007401579690263197296200323999931849 5396 True 1176     
6254449428820551641549772190170184190608177514674331726439961915653414425 5413 True 1178     
>>> 
For 73 digits Fibonacci numbers Pi4B Python needs roughly 200µs with default and 80µs for fast Fibonacci computations.
Pico Micropython needs roughly 5400µs/1180µs for 350 digits.


Passing "False" as second argument outputs number of decimal digits, allowing to get runtime numbers for computing 10,000th(!) Fibonacci number with more than 2000 decimal digits:

Code: Select all

pi@raspberrypi4B:~ $ python -c "import fib; fib.tst(10000,False)"
2
(2088, 25940, True, 777)
(2088, 10547, True, 425)
(2089, 10091, True, 428)
(2089, 10865, True, 435)
(2089, 10208, True, 435)
(2089, 10231, True, 417)
(2089, 10496, True, 442)
(2090, 10503, True, 434)
(2090, 10580, True, 454)
(2090, 10118, True, 415)
pi@raspberrypi4B:~ $ 

Roughly 70ms for Pico MicroPython, compared to 430µs for Pi4B Python:

Code: Select all

>>> fib.tst(10000,False)                                                                     
2088 1210229 True 69978                                                                      
2088 1221406 True 71887                                                                      
2089 1051971 True 69788                                                                      
2089 1280082 True 75597                                                                      
2089 1102442 True 68994                                                                      
2089 1166174 True 69171                                                                      
2089 1241290 True 70132                                                                      
2090 1076333 True 69608                                                                      
2090 1424052 True 75134                                                                      
2090 978265 True 69157                                                                       
>>> 


This is first time that I eliminated platform dependency for using builtin functions from different platforms without performance loss, hopefully this technique will be useful for others as well.
Last edited by HermannSW on Wed May 12, 2021 9:21 am, edited 2 times in total.
https://stamm-wilbrandt.de/2wheel_balancing_robot
https://stamm-wilbrandt.de/en#raspcatbot
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://github.com/Hermann-SW/raspiraw
https://stamm-wilbrandt.de/en/Raspberry_camera.html

User avatar
OneMadGypsy
Posts: 271
Joined: Wed Apr 28, 2021 1:57 am
Location: New Orleans, Louisiana
Contact: Website

Re: builtin µs timing code made platform independent (python[23] / Pico MicroPython)

Wed May 12, 2021 8:17 am

Excellent work!
"Focus is a matter of deciding what things you're not going to do." ~ John Carmack

User avatar
HermannSW
Posts: 4130
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany
Contact: Website Twitter YouTube

Re: builtin µs timing code made platform independent (Python[23] / Pico MicroPython)

Wed May 12, 2021 9:33 am

Nice, timestamping allowed to show that Python double assignments are (sometimes) slightly faster than 3 sequential assignments, this is the diff:

Code: Select all

pi@raspberrypi4B:~ $ diff fib.py fib1.py
35a36,42
> def F2(n):
>     a=0
>     b=1
>     for i in range(0,n):
>         (a,b)=(b,a+b)
>     return a
> 
41c48
<         r2=Ffast(n)
---
>         r2=F2(n)
pi@raspberrypi4B:~ $ 

Comparison for using F(n) left vs. F2(n) right, this time for 100,000th(!) Fibonacci number with roughly 20,900 decimal digits:

Code: Select all

pi@raspberrypi4B:~ $ python -c "import fib1; fib1.tst(100000,False)"
2
(20897, 811706, True, 776663)
(20897, 805090, True, 783051)
(20897, 788361, True, 786974)
(20898, 797782, True, 802456)
(20898, 790623, True, 794436)
(20898, 779696, True, 787630)
(20898, 783586, True, 787494)
(20898, 779631, True, 782246)
(20899, 793039, True, 777138)
(20899, 784679, True, 781744)
pi@raspberrypi4B:~ $ 
https://stamm-wilbrandt.de/2wheel_balancing_robot
https://stamm-wilbrandt.de/en#raspcatbot
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://github.com/Hermann-SW/raspiraw
https://stamm-wilbrandt.de/en/Raspberry_camera.html

Return to “MicroPython”