Documentation Center |
On this page… |
---|
Why Use the Remember Mechanism |
If your code calls a procedure with the same arguments more than once, avoid unnecessary reevaluations, and thus, improve performance. Instead of multiple evaluations of a procedure call with the same arguments, MuPAD^{®} can store the results of the first procedure call in a special table. This table is called the remember table. The system stores the arguments of a procedure call as indices of the remember table entries, and the corresponding results as values of these entries. When you call a procedure using the same arguments as in previous calls, MuPAD accesses the remember table of that procedure. If the remember table contains the entry with the required arguments, MuPAD returns the value of that entry. Otherwise, MuPAD evaluates the procedure call, and writes the arguments and corresponding results to the remember table of the procedure.
Using the remember mechanism in MuPAD can significantly accelerate your computations, especially when you use recursive procedure calls. For example, create the procedure that computes the Lucas numbers. The Lucas numbers are a sequence of integers. The recursion formula that defines the nth Lucas number is similar to the definition of the Fibonacci numbers:
The following recursive procedure returns any Lucas number:
lucas:= proc(n:Type::PosInt) begin if n = 1 then 1 elif n = 2 then 3 else lucas(n - 1) + lucas(n - 2) end_if end_proc:
However, if the value n is large, computing the nth Lucas number can be very slow. The number of required procedure calls is exponential. Often, the procedure calls itself with the same arguments, and it reevaluates the result in every call:
time(lucas(35))
Using the remember mechanism eliminates these reevaluations. To enable the remember mechanism for a particular procedure, use the prog::remember function. This function returns a modified copy of a procedure that stores results of previous calls in the remember table:
lucas := prog::remember(lucas):
When you call this procedure, MuPAD accesses the remember table. If the system finds the required entry in the remember table, it returns remembered results immediately. Now, MuPAD computes the 35th and even the 100th Lucas number almost instantly:
time(lucas(35)), time(lucas(100))
Alternatively, you can enable the remember mechanism for a particular procedure by using the option remember for that procedure. For example, use the option remember to enable the remember mechanism for the procedure lucas:
lucas:= proc(n:Type::PosInt) option remember; begin if n = 1 then 1 elif n = 2 then 3 else lucas(n - 1) + lucas(n - 2) end_if end_proc:
For further computations, delete the procedure lucas:
delete lucas:
By default, the remember mechanism does not consider context information of a procedure call. Thus, the remember mechanism disregards any changes in assumptions set on the arguments of a procedure call and the number of digits used for floating-point arithmetic. By default, remember tables contain only arguments and results of procedure calls. They do not store context information. For example, create the function f that computes the reciprocal of a number. Use prog::remember to enable the remember mechanism for this function:
f := (x)-> 1.0/x: f := prog::remember(f):
The default number of significant digits for floating-point numbers is 10. Use the function f to compute the reciprocal of 3. The system displays the result with the 10-digits accuracy:
f(3)
Now increase the number of digits to 50. Then call the function f with the argument 3 again. By default, MuPAD does not realize that you increased the required accuracy. The system accesses the remember table, finds the entry that corresponds to the argument 3, and returns the result previously computed for that argument. Since MuPAD must display the output with 50 digits, the last digits in the displayed result are incorrect:
DIGITS := 50: f(3)
For further computations, restore the default value of DIGITS and delete f:
delete DIGITS, f
Although by default the remember mechanism in MuPAD disregards all context information, you can extend the prog::remember function call and take into account the properties of arguments and current accuracy of floating-point arithmetic. For example, create the function f that computes the reciprocal of a number. Use prog::remember to enable the remember mechanism for this function. In the prog::remember function call, specify the dependency function. The dependency function is the function that computes the current properties of the input arguments and the values of DIGITS and ORDER. Then prog::remember compares this context information with the context information used to compute the remembered values. If the context information is the same, prog::remember returns the remembered result. Otherwise MuPAD evaluates the current procedure call, and adds the new result to the remember table.
Note: The option remember does not let you specify the dependency function. If results of a procedure depend on the context information, use the prog::remember function for that procedure. |
In this example, the dependency function is a list that checks both the properties of input arguments and the value of DIGITS:
f := (x)-> 1.0/x: f := prog::remember(f, () -> [property::depends(args()), DIGITS]):
The default number of significant digits for floating-point numbers is 10. Use the function f to compute the reciprocal of 3. The system displays the result with the 10-digits accuracy:
f(3)
If you set the number of digits to 50, and then call the function f with the same argument 3, prog::remember realizes that the number of digits has changed. Instead of returning the previous result stored in the remember table, the system reevaluates the result and updates the remember table:
DIGITS := 50: f(3)
For further computations, restore the default value of DIGITS and delete f:
delete DIGITS, f
In some cases, the remember mechanism can lead to incorrect results. For example, if a nested procedure uses the remember mechanism, and you redefine the inner procedure, MuPAD does not recognize the changes and does not reevaluate the procedure call.
Create the following procedure f as a wrapper for the MuPAD heaviside function. Use prog::remember to enable the remember mechanism for the procedure f:
f := proc(x) begin heaviside(x) end: f := prog::remember(f):
Now compute the Heaviside function for the values -10, 0, and 10. MuPAD uses the value heaviside(0)=1/2:
f(-10), f(0), f(10)
You can define a different value for heaviside(0). First, use the unprotect function to be able to overwrite the value of heaviside. Then, assign the new value to heaviside(0):
unprotect(heaviside): heaviside(0):= 0:
Despite the new value heaviside(0) = 0, the wrapper procedure f returns the old value 1/2:
f(0)
The result of the procedure call f(0) does not change because the system does not reevaluate this result. It finds the result in the remember table of the procedure f and returns that result. To display the content of the remember table, call the wrapper procedure f with the Remember option as a first argument and the Print option as a second argument. The value 10^{6} in the second column is the value of MAXEFFORT used during computations.
f(Remember, Print)
To force reevaluation of the procedure calls of f, clear the remember table of that procedure. To clear the remember table, call f with the Remember option as a first argument and the Clear option as a second argument:
f(Remember, Clear):
Now f returns the correct result:
f(0)
If you use the option remember, you also can clear the remember table and force reevaluation. For example, rewrite the procedure f as follows:
f := proc(x) option remember; begin heaviside(x) end: f(0)
Now restore the heaviside function to its default definition:
heaviside(0):= 1/2:
To clear a remember table created by the option remember, use the forget function:
forget(f): f(0)
Use the protect function with the ProtectLevelError option to prevent further changes to heaviside. Also, delete the procedure f:
protect(heaviside, ProtectLevelError): delete f
The remember mechanism is a powerful tool for improving performance of MuPAD procedures. Nevertheless, you can encounter some problems when using this mechanism:
Remember tables are efficient only if the access time of the remember table is significantly less than the time needed to evaluate the result. If a remember table is very large, evaluation can be computationally cheaper than accessing the result stored in the remember table.
Storing large remember tables requires a large amount of memory. Especially, remember tables created with the option remember can grow very large, and significantly reduce available memory. The number of entries in remember tables created by prog::remember is limited. When the number of entries in a remember table created by prog::remember reaches the maximum number, the system removes a group of older entries.
Using prog::remember or the option remember for nonrecurring procedure calls can significantly decrease code performance. Avoid using the remember mechanism for nonrecurring procedure calls, especially if the arguments are numerical.
If you change the properties of input arguments or modify the variables DIGITS or ORDER, the remember mechanism ignores these changes by default. See Remembering Results Without Context.
In some cases you must clear the remember table of a procedure to enforce reevaluation and avoid incorrect results. For example, clearing the remember table can be necessary when a procedure changes global variables or if global variables affect the results of a procedure. See Clearing Remember Tables.
Many predefined MuPAD functions have special values stored in their remember tables. Therefore, clearing the remember tables of predefined MuPAD functions is not recommended. Note that the forget function does not error when you call it for a predefined MuPAD function.