Python: Is it possible to make this tail-recursion factorial even faster?

user_1241715 0
Viewed 199

I'm making a utilities class for an application which involves combinatorics.

I've made two factorial funcion which tail recursion. The second one improves a lot the performance when coming to calculate combinatorics numbers (I think in English they are called n choose k, I use C(n,k) notation and made a nCk function also).

So I measured times, and I achieved my goal. My new combinatorics functions are much faster than the new ones.

But when coming to the factorial function I found that my new factorial function 'f' is a bit slower than the first one 'fact'.

Is there a way to make this 'f' function as good in performance as 'fact'?

You can see the main test execution and results in my machine at the bottom.

Source code

class Utils(object):
    """
    Class with useful functions
    """

    @staticmethod
    def fact(i, _current_factorial=1):
        '''
        The factorial function
        :param i: the number for calculating the factorial
        :param _current_factorial: for internal use, it is the acumulated product
        :return the result
        '''
        if i == 1:
            return _current_factorial
        else:
            return Utils.fact(i - 1, _current_factorial * i)

    @staticmethod
    def f(i, k=None, _current_factorial=1):
        '''
        The factorial function
        If k is given, it calculates the factorial but only with
        the k-th first numbers.
        Example:
            f(6) = 6 · 5 · 4 · 3 · 2 · 1
            f(6, 2) = 6 · 5
            f(6, 3) = 6 · 5 · 4
            f(9, 4) = 9 · 8 · 7 · 6
        :param i: the number for calculating the factorial
        :param k: optional, the number for calculating the factorial
        :param _current_factorial: for internal use, it is the acumulated product
        :return the result
        '''
        if k is None:
            k = i
        if i == 1 or k == 0:
            return _current_factorial
        else:
            return Utils.f(i - 1, k - 1, _current_factorial=_current_factorial * i)

    @staticmethod
    def C(n, k=1):
        '''
        Statistical combinations 'nCk'
        :param n: number of elements to be combined
        :param k: number of elements to be taken for each combination
        :return: the 'n choose k' mathematical result
        '''
        return Utils.fact(n) / (Utils.fact(k) * Utils.fact(n - k))

    @staticmethod
    def nCk(n, k=1):
        '''
        Statistical combinations 'nCk'
        :param n: number of elements to be combined
        :param k: number of elements to be taken for each combination
        :return: the 'n choose k' mathematical result
        '''
        return Utils.f(n, k) / Utils.f(k)



if __name__ == "__main__":
    NUM_TEST_ITERATIONS = 7500
    MAX_NUMBER_WITHOUT_STACKOVERFLOW = 998

    import time

    start = time.process_time()
    for i in range(NUM_TEST_ITERATIONS): Utils.f(MAX_NUMBER_WITHOUT_STACKOVERFLOW)
    elapsed = time.process_time() - start
    print('Function {} took {} to get result {}'.format('f', elapsed, Utils.f(MAX_NUMBER_WITHOUT_STACKOVERFLOW)))

    start = time.process_time()
    for i in range(NUM_TEST_ITERATIONS): Utils.fact(MAX_NUMBER_WITHOUT_STACKOVERFLOW)
    elapsed = time.process_time() - start
    print('Function {} took {} to get result {}'.format('fact', elapsed, Utils.fact(MAX_NUMBER_WITHOUT_STACKOVERFLOW)))

    start = time.process_time()
    for i in range(NUM_TEST_ITERATIONS): Utils.nCk(997, 4)
    elapsed = time.process_time() - start
    print('Function {} took {} to get result {}'.format('nCk', elapsed, Utils.nCk(997, 4)))

    start = time.process_time()
    for i in range(NUM_TEST_ITERATIONS): Utils.C(997, 4)
    elapsed = time.process_time() - start
    print('Function {} took {} to get result {}'.format('C', elapsed, Utils.C(997, 4)))

On screen:

Function f    took 7.854962716 to get result 402790050127220994538240674597601587306681545756471103647447357787726238637266286878923131618587992793273261872069265323955622495490298857759082912582527118115540044131204964883707335062250983503282788739735011132006982444941985587005283378024520811868262149587473961298417598644470253901751728741217850740576532267700213398722681144219777186300562980454804151705133780356968636433830499319610818197341194914502752560687555393768328059805942027406941465687273867068997087966263572003396240643925156715326363340141498803019187935545221092440752778256846166934103235684110346477890399179387387649332483510852680658363147783651821986351375529220618900164975188281042287183543472177292257232652561904125692525097177999332518635447000616452999984030739715318219169707323799647375797687367013258203364129482891089991376819307292252205524626349705261864003453853589870620758596211518646408335184218571196396412300835983314926628732700876798309217005024417595709904449706930796337798861753941902125964936412501007284147114260935633196107341423863071231385166055949914432695939611227990169338248027939843597628903525815803809004448863145157344706452445088044626373001304259830129153477630812429640105937974761667785045203987508259776060285826091261745049275419393680613675366264232715305430889216384611069135662432391043725998805881663054913091981633842006354699525518784828195856033032645477338126512662942408363494651203239333321502114252811411713148843370594801145777575035630312885989779863888320759224882127141544366251503974910100721650673810303577074640154112833393047276025799811224571534249672518380758145683914398263952929391318702517417558325636082722982882372594816582486826728614633199726211273072775131325222240100140952842572490801822994224069971613534603487874996852498623584383106014533830650022411053668508165547838962087111297947300444414551980512439088964301520461155436870989509667681805149977993044444138428582065142787356455528681114392680950815418208072393532616122339434437034424287842119316058881129887474239992336556764337968538036861949918847009763612475872782742568849805927378373244946190707168428807837146267156243185213724364546701100557714520462335084082176431173346929330394071476071813598759588818954312394234331327700224455015871775476100371615031940945098788894828812648426365776746774528000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Function fact took 6.757415364 to get result 402790050127220994538240674597601587306681545756471103647447357787726238637266286878923131618587992793273261872069265323955622495490298857759082912582527118115540044131204964883707335062250983503282788739735011132006982444941985587005283378024520811868262149587473961298417598644470253901751728741217850740576532267700213398722681144219777186300562980454804151705133780356968636433830499319610818197341194914502752560687555393768328059805942027406941465687273867068997087966263572003396240643925156715326363340141498803019187935545221092440752778256846166934103235684110346477890399179387387649332483510852680658363147783651821986351375529220618900164975188281042287183543472177292257232652561904125692525097177999332518635447000616452999984030739715318219169707323799647375797687367013258203364129482891089991376819307292252205524626349705261864003453853589870620758596211518646408335184218571196396412300835983314926628732700876798309217005024417595709904449706930796337798861753941902125964936412501007284147114260935633196107341423863071231385166055949914432695939611227990169338248027939843597628903525815803809004448863145157344706452445088044626373001304259830129153477630812429640105937974761667785045203987508259776060285826091261745049275419393680613675366264232715305430889216384611069135662432391043725998805881663054913091981633842006354699525518784828195856033032645477338126512662942408363494651203239333321502114252811411713148843370594801145777575035630312885989779863888320759224882127141544366251503974910100721650673810303577074640154112833393047276025799811224571534249672518380758145683914398263952929391318702517417558325636082722982882372594816582486826728614633199726211273072775131325222240100140952842572490801822994224069971613534603487874996852498623584383106014533830650022411053668508165547838962087111297947300444414551980512439088964301520461155436870989509667681805149977993044444138428582065142787356455528681114392680950815418208072393532616122339434437034424287842119316058881129887474239992336556764337968538036861949918847009763612475872782742568849805927378373244946190707168428807837146267156243185213724364546701100557714520462335084082176431173346929330394071476071813598759588818954312394234331327700224455015871775476100371615031940945098788894828812648426365776746774528000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Function nCk took 0.021283503999999454 to get result 40921610765.0
Function C   took 13.261998684000002   to get result 40921610765.0
combinatorics tail-recursion recursion python performance
1 Answers

I finally removed the class code and used math.factorial, but I imported it with 'fact' name.

I also use a shortcut in the formula explained in the source code docs

This is much much better than the original. Thanks

Source code (omitting the main for brevity):

# Importing math.factorial with shorter name
from math import factorial as fact
from functools import reduce
from operator import mul


def C(n, k=1):
    '''
    Statistical combinations 'nCk'
    :param n: number of elements to be combined
    :param k: number of elements to be taken for each combination
    :return: the 'n choose k' mathematical result
    '''
    '''
        Original formula: fact(n) / (fact(k) * fact(n-k))

        Performance shortcut (about 40% faster): 
            1.- Calculates the numerator as the product over the first k-th elements of fact(n)
            Let's call this f'(n,k), we store it in fnkProduct variable
            Example:
                n = 6, k = 2 => f'(n,k) =   30 = 6 · 5
                n = 6, k = 3 => f'(n,k) =  120 = 6 · 5 · 4
                n = 9, k = 4 => f'(n,k) = 3024 = 9 · 8 · 7 · 6
            2.- Then divide it by fact(k)

        New formula: f'(n,k) / fact(k)

        '''
    # C(n,k) == C(n,n-k), but the second is best when k is much bigger
    k = n - k if k > (n // 2) else k
    fnkProduct = reduce(mul, range(n, n - k, -1), 1)
    return fnkProduct // fact(k)

On screen (this is the last comparison I did before I decided 15 million iterations)

Function C took 0.01638609299999999 to get result 40921610765.0
Function nCk took 0.016534930000000003 to get result 40921610765.0
user_12417150
Related