Estimating n log n via a estimation like newtons method

README.md

Estimating hard to invert functions

Works for

• n log(n)
• n! ( Factorial function )

$ python function_estimation.py 
Inverse of n log (n) for 10**6
(1, 1000000)
(2, 50171.665943996864)
(3, 64042.687379853196)
(4, 62630.16808504241)
(5, 62756.63490254194)
(6, 62745.1753033653)
(7, 62746.2125733879)
(8, 62746.1186752841)
(9, 62746.12717526523)
(10, 62746.12640581692)
(11, 62746.1264754701)
(12, 62746.12646916485)
(13, 62746.12646973562)
(14, 62746.12646968395)
(15, 62746.12646968862)
(16, 62746.1264696882)
(17, 62746.12646968824)
Inverse of n! for 10**6
(1, 1000000)
(2, 1000000)
(3, 500000)
(4, 166666)
(5, 41666)
(6, 8333)
(7, 1388)
(8, 198)
(9, 24)

function_estimation.py

import math


def inverse_nlogn(t):
    n = t
    i = 0
    n_prime = n
    while i <= 100:
        n, n_prime = (t / math.log(n, 2), n)
        i += 1
        print(i, n_prime)
        if n == n_prime:
            break


def inverse_nfactorial(t):

    factor = t
    i = 1

    while factor > i:
        print(i, factor)
        factor = factor / i
        i += 1

    return i


print("Inverse of n log (n) for 10**6")
inverse_nlogn(10**6)


print("Inverse of n! for 10**6")
inverse_nfactorial(10**6)

OUTPUT:

$ python nlogn.py
(1, 1000000)
(2, 50171.665943996864)
(3, 64042.687379853196)
(4, 62630.16808504241)
(5, 62756.63490254194)
(6, 62745.1753033653)
(7, 62746.2125733879)
(8, 62746.1186752841)
(9, 62746.12717526523)
(10, 62746.12640581692)
(11, 62746.1264754701)
(12, 62746.12646916485)
(13, 62746.12646973562)
(14, 62746.12646968395)
(15, 62746.12646968862)
(16, 62746.1264696882)
(17, 62746.12646968824)