Computing Sylvester numbers for CR

sylvester.py

from time import clock


def sylvester_number_original(n):
    if n == 0:
        return 2

    return sylvester_number_original(n - 1) * (sylvester_number_original(n - 1) - 1) + 1


def sylvester_number_faster(n):
    if n == 0:
        return 2

    tmp = sylvester_number_original(n - 1)
    return tmp * (tmp - 1) + 1


def main():
    n = 23
    start = clock()
    result_original = sylvester_number_original(n)
    end = clock()

    print("Original implementation took ", int(1000 * (end - start)), "milliseconds.")

    start = clock()
    result_dynamic = sylvester_number_faster(n)
    end = clock()

    print("Dynamic programming implementation took ", int(1000 * (end - start)), "milliseconds.")

    print("Results are same: ", result_dynamic == result_original)

if __name__ == "__main__":
    main()