lambda, apply, arbitrary precision

Discussion about programs, libraries and tools that work with MicroPython. Mostly these are provided by a third party.
Target audience: All users and developers of MicroPython.
Post Reply
HermannSW
Posts: 197
Joined: Wed Nov 01, 2017 7:46 am
Contact:

lambda, apply, arbitrary precision

Post by HermannSW » Tue Apr 27, 2021 4:08 pm

Today I stumbled over this identity for Catalan numbers:
https://oeis.org/A000108
C(p+q)-C(p)*C(q) = Sum_{i=0..p-1, j=0..q-1} C(i)*C(j)*C(p+q-i-j-1). - Groux Roland, Nov 13 2009
Normally I use "bc" tool for arbitrary precision calculations, but realized that MicroPython allows for that as well. And I wanted to learn on (Micro)Python's lambda functions. Since functools module seems not available for MicroPython, I created my own "apply(range,func)" function (concatenation of tuples):

Code: Select all

def apply(r,f):
    R=()
    for i in r:
        R += f(i),
    return R




These are the basic "bin(n,k)" and "C(n)" functions I used:

Code: Select all

def bin(n,k):
    return 1 if k<=0 else bin(n-1,k-1) * n // k

def C(n):
    return bin(2*n,n) // (n+1)


This code computed part of above identity the imperative way:

Code: Select all

def sigma(p,q):
    s=0
    for i in range(p):
        for j in range(q):
            s+=C(i)*C(j)*C(p+q-i-j-1)
    return s

print(sigma(11,11))

It took me a while to correctly uise lamda and sum functions to compute same value -- the "sum(apply(..." looks more like mathematical "Sum_{...}...":

Code: Select all

def siglam(p,q):
    return sum(apply(range(p),
                     lambda i: sum(apply(range(q),
                                         lambda j: C(i)*C(j)*C(p+q-i-j-1)
                                        )
                                  )
                    )
              )

print(siglam(11,11))

Finally I wanted to check that identity is valid, but stack size limited what is possible. Anyway the "tst()" function allows for nice way to pass lambda functions with two arguments. Boolean values False/True are converted to 0/1 by "sum()" function. So overall sum returning 0 means that all (negative) identities tested are valid:

Code: Select all

def tst(n, f):
    return sum(apply(range(n+1),
                     lambda p: sum(apply(range(p+1),
                                         lambda q: f(p,q)
                                        )
                                  )
                    )
              )

print(tst(8, lambda p,q: siglam(p,q) != sigma(p,q)))
print(tst(8, lambda p,q: C(p+q)-C(p)*C(q) != sigma(p,q)))
print("[bin(9+1,2)="+str(tst(8, lambda p,q: 1))+"]")



The last line tells the number of tests done in total:

Code: Select all

>>> 
MPY: soft reboot
MicroPython v1.14 on 2021-04-13; Raspberry Pi Pico with RP2040
Type "help()" for more information.                                            
>>> import catalan                                                             
88026769844                                                                    
88026769844                                                                    
0                                                                              
0                                                                              
[bin(9+1,2)=45]                                                                
>>> 


Finaly this is complete "catalan.py":

Code: Select all

def bin(n,k):
    return 1 if k<=0 else bin(n-1,k-1) * n // k

def C(n):
    return bin(2*n,n) // (n+1)

def apply(r,f):
    R=()
    for i in r:
        R += f(i),
    return R

def sigma(p,q):
    s=0
    for i in range(p):
        for j in range(q):
            s+=C(i)*C(j)*C(p+q-i-j-1)
    return s

print(sigma(11,11))

def siglam(p,q):
    return sum(apply(range(p),
                     lambda i: sum(apply(range(q),
                                         lambda j: C(i)*C(j)*C(p+q-i-j-1)
                                        )
                                  )
                    )
              )

print(siglam(11,11))

def tst(n, f):
    return sum(apply(range(n+1),
                     lambda p: sum(apply(range(p+1),
                                         lambda q: f(p,q)
                                        )
                                  )
                    )
              )

print(tst(8, lambda p,q: siglam(p,q) != sigma(p,q)))
print(tst(8, lambda p,q: C(p+q)-C(p)*C(q) != sigma(p,q)))
print("[bin(9+1,2)="+str(tst(8, lambda p,q: 1))+"]")
Pico-W Access Point static file webserver:
https://github.com/Hermann-SW/pico-w

Tiny MicroPython robots (the PCB IS the robot platform)
viewtopic.php?f=5&t=11454

webrepl_client.py
https://github.com/Hermann-SW/webrepl#webrepl-shell

HermannSW
Posts: 197
Joined: Wed Nov 01, 2017 7:46 am
Contact:

Re: lambda, apply, arbitrary precision

Post by HermannSW » Thu Apr 29, 2021 4:38 pm

Cosmetics, easier to read, does not use that much space horizontally, equivalent to previous code:

Code: Select all

def siglam(p,q):
    return sum(apply(range(p), lambda i:
               sum(apply(range(q), lambda j:
                   C(i)*C(j)*C(p+q-i-j-1)
               ))
           ))
        
Pico-W Access Point static file webserver:
https://github.com/Hermann-SW/pico-w

Tiny MicroPython robots (the PCB IS the robot platform)
viewtopic.php?f=5&t=11454

webrepl_client.py
https://github.com/Hermann-SW/webrepl#webrepl-shell

HermannSW
Posts: 197
Joined: Wed Nov 01, 2017 7:46 am
Contact:

Re: lambda, apply, arbitrary precision

Post by HermannSW » Fri Apr 30, 2021 1:41 pm

This is more clean:

Code: Select all

def siglam(p,q):
    return (apply(range(p), lambda i:
                (apply(range(q), lambda j:
                    C(i)*C(j)*C(p+q-i-j-1)
                ))
           ))

Returns nested tuples

Code: Select all

>>> catalan.siglam2(3,2)                                                       
((14, 5), (5, 2), (4, 2))                                                      
>>> 

which "sum()" cannot handle -- but "sumit()" can:

Code: Select all

def sumit(t):
    return t if isinstance(t, (int,float)) \
      else 0 if len(t)==0                  \
      else sumit(t[0])+sumit(t[1:])

Code: Select all

>>> catalan.sumit(catalan.siglam2(3,2))                                        
32                                                                             
>>> 

"sumit()" can deal with integers and floats, and with nested tuples and lists:

Code: Select all

>>> catalan.sumit([1, (2, 3), [4, 5.6], ([7, 8, 9, 10], 11)])                  
60.6                                                                           
>>> 

"mulit()" can simply be defined if needed for mathematical product of terms.

Code: Select all

$ cat catalan.py
def bin(n,k):
    return 1 if k<=0 else bin(n-1,k-1) * n // k

def C(n):
    return bin(2*n,n) // (n+1)

def apply(r,f):
    R=()
    for i in r:
        R += f(i),
    return R

def sumit(t):
    return t if isinstance(t, (int,float)) \
      else 0 if len(t)==0                  \
      else sumit(t[0])+sumit(t[1:])

def siglam2(p,q):
    return (apply(range(p), lambda i:
                (apply(range(q), lambda j:
                    C(i)*C(j)*C(p+q-i-j-1)
                ))
           ))

print(sumit(siglam2(3,2)))
print(siglam2(3,2))
$
Pico-W Access Point static file webserver:
https://github.com/Hermann-SW/pico-w

Tiny MicroPython robots (the PCB IS the robot platform)
viewtopic.php?f=5&t=11454

webrepl_client.py
https://github.com/Hermann-SW/webrepl#webrepl-shell

Post Reply