Method and apparatus for maintaining a lookup table for storing function values

A method for building and accessing a table storing an evaluated function value for each of a plurality of points in a domain of a function comprising the steps of:

• generating an input address which identifies a selected domain point,
• mapping the input address to a corresponding storage location in a memory device, wherein the input address is initially unallocated and mapped to a default storage location shared with other input addresses and containing a default lookup table value, and wherein the input address is subsequently allocated and mapped to a corresponding storage location allocated to said input address,
• determining whether said input address is allocated based on the entry table value provided in response to the input address,
• determining the value of said function at said selected domain point when the input address is unallocated,
• storing said determined function value in a storage location allocated to said input address, and
• remapping said input address to said allocated storage location.

A method for dynamically allocating storage memory for storing a plurality of function values, each stored function value representing a value of a function evaluated at a selected domain point of the function's domain, the method comprising the steps of:

• generating an input address representative of a selected domain point,
• selecting, from a page table storage means, a page pointer which indicated whether said input address is allocated,
• selecting, if said input address is unallocated, a new portion of said memory, said new portion comprising a new storage location allocated to said input address,
• evaluating the function at the selected domain point, and
• storing in said new storage location, the function value evaluated at the selected domain point identified by said input address.

A method for evaluating a function comprising the steps of:

• generating an input address representation of the function input value,
• searching a stored lookup table, based on the address representation, for the corresponding function value,
• determining the function value explicitly if a default value is stored in the lookup table,
• storing the determined function value at the corresponding address representation, said storing step comprising:
• determining if said input address is allocated,
• selecting, if said input address is unallocated, a newly allocated storage location allocated to said input address, and
• remapping said input address to said newly allocated storage location.

A method for building and accessing a function table which stores function values in function table addresses that correspond to points in the function's input domain, the method comprising steps of:

• initializing a page table to map input domain points to a shared region of the function table where a default value is stored as a function value;
• selecting a domain point in the function's input domain;
• mapping the domain point to a function table address;
• reading a function value stored in the function table address;
• if the function value is the default value then (1) evaluating the function for the input domain point, (2) storing the evaluated function value in a non-shared function table address, and (3) modifying the page table to map the domain point to the non-shared function table address in which the output value is stored.