make_natural_log_lookup_table.py

"""
NATURAL LOG LOOKUP TABLE GENERATOR

Generates a lookup table for the natural log function given a lower and upper bound
Points chosen ensure that linear approximation between the points minimize error
within the MAX_PERCENT_ERROR provided.

You can adjust the MAX_PERCENT_ERROR, realizing that a smaller error will require
more data points. The length of the resulting list should be printed to standard output.

Script prints the lookup table to standard output for simplicity of copy-pasting.
"""

import math

MAX_PERCENT_ERROR = 0.86  # NOTE: This in percentage out of 100 (i.e. 0.5 is 0.5%)
LOWER_BOUND = 0.0009775171065493646
UPPER_BOUND = 43.52173913043478

def main():
    x_values = [LOWER_BOUND, UPPER_BOUND]
    result = create_new_list_to_minimize_error(x_values)

    new_values = dict()

    for item in sorted(result):
        new_values[item.point0.x] = item.point0.y
        # print(item)  # details about each line, not necessary but good for debugging

    print_lt(new_values)
    print("Number of Items in Lookup Table: " + str(len(new_values.items())))

    # Also print out CSV list, nice for copying/pasting into Excel to visualize
    # for item in new_values.items():
    #     print(str(item[0]) + ", " + str(item[1]) + "")

class Point():
    """
    A point on a cartesian graph with x and y representing position.
    """
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __repr__(self):
        output = ""
        output += "Point(" + str(self.x) + ", " + str(self.y) + ")"
        return output

class Line():
    """
    Two points on a graph.

    NOTE: y values representing the ln(x) in this example
    """
    def __init__(self, point0, point1):
        self.point0 = point0
        self.point1 = point1
        self.get_slope()
        self.get_y_intercept()
        self.get_raw_error()
        self.get_percent_error()

    def get_slope(self):
        self.slope = ((self.point1.y - self.point0.y) / (self.point1.x - self.point0.x))

    def get_y_intercept(self):
        self.y_intercept = (self.point1.y - (self.slope * self.point1.x))

    def get_raw_error(self):
        """
        Done by taking the integral of ln(x) from point0 -> point1
        and subracting the integral of the line from point0 -> point1 (e.g. mx + b)

        This gives us a raw value representing the area between the two functions.
        Higher area = greater error
        """
        inside_0 = self.point0.y - 1 - self.y_intercept - (self.slope * self.point0.x / 2)
        inside_1 = self.point1.y - 1 - self.y_intercept - (self.slope * self.point1.x / 2)

        self.error = (self.point1.x * inside_1) - (self.point0.x * inside_0)

    def get_percent_error(self):
        """
        % error = | ( relative error / accepted value ) * 100 |

        Our accepted value is the integral of ln(x) from point0 -> point1
        """
        accepted_value = (self.point1.x * (self.point1.y - 1)) - (self.point0.x * (self.point0.y - 1))
        self.percent_error = abs((self.error / accepted_value) * 100)

    def __repr__(self):
        output = ""
        output += "      point0: " + str(self.point0) + "\n"
        output += "      point1: " + str(self.point1) + "\n"
        output += "       slope: " + str(self.slope) + "\n"
        output += " y_intercept: " + str(self.y_intercept) + "\n"
        output += "       error: " + str(self.error) + "\n"
        output += "      perror: " + str(self.percent_error) + "\n"
        return output

    def __lt__(self, other):
        return (self.point0.x < other.point0.x)

def create_new_list_to_minimize_error(x_values):
    values = []

    for item in x_values:
        values.append(Point(item, math.log(item)))

    lines = []

    # Create a list of objects that represent two points (e.g. a line)
    for x in range(1, len(values)):
        two_points = Line(values[x-1], values[x])
        lines.append(two_points)

    for two_points in lines:
        if (two_points.percent_error > MAX_PERCENT_ERROR):
            # We need to add a point inbetween the two points
            # and then rerun this algorithm
            new_list = add_point_inbetween(two_points, x_values)
            return create_new_list_to_minimize_error(new_list)

    return lines

def add_point_inbetween(item, x_values):
    new_x_values = []
    for x_value in x_values:
        if item.point0.x == x_value:
            new_x_values.append(x_value)
            new_x_values.append((item.point0.x + item.point1.x) / 2)
        else:
            new_x_values.append(x_value)

    return new_x_values

def print_lt(lookup):
    print("{")
    for item in lookup.items():
        print("   {\n"
              "      /* input     */ " + str(item[0]) + ",\n"
              "      /* ln(input) */ " + str(item[1]) + ",\n"
              "   },")
    print("}\n")

if __name__ == '__main__':
    main()