Memory Bound Function - Memory Bound Functions and Memory Functions

Memory Bound Functions and Memory Functions

Memory bound functions and memory functions are related in that both involve extensive memory access, but a distinction exists between the two.

Memory functions use a dynamic programming technique called memoization in order to relieve the inefficiency of recursion that might occur. It is based on the simple idea of calculating and storing solutions to subproblems so that the solutions can be reused later without recalculating the subproblems again. The best known example that takes advantage of memoization is an algorithm that computes the Fibonacci numbers. The following pseudocode illustrates an algorithm that uses memoization, which runs in linear CPU time:

Fibonacci (n) { for i = 0 to n-1 results = -1 // -1 means undefined return Fibonacci_Results (results, n); } Fibonacci_Results (results, n) { if (results != -1) //check if it has already been solved before return results if (n == 0) val = 0 else if (n == 1) val = 1 else val = Fibonacci_Results(results, n -2 ) + Fibonacci_Results(results, n -1) results = val return val }

Compare the above to an algorithm that uses recursion, which runs in exponential CPU time:

Recursive_Fibonacci (n) { if (n == 0) return 0 else if ( n == 1) return 1 else return Recursive_Fibonacci (n -1) + Recursive_Fibonacci (n -2) }

While the recursive algorithm is simpler and more elegant than the algorithm that uses memoization, the latter has a significantly lower time complexity than the former. The term "memory bound function" has surfaced only recently and is used principally to describe a function that uses XOR and consists of a series of computations in which each computation depends on the previous computation. Whereas memory functions have long been an important actor in improving time complexity, memory bound functions have seen far fewer applications. Recently, however, scientists have proposed a method using memory bound functions as a means to discourage spammers from abusing resources, which could be a major breakthrough in that area.