1

Are there functions that remember values they have found on Octave?

When you make a function definition, the value of the function is recomputed every time you ask for it. In some kinds of calculations, you may end up asking for the same function value many times. You can save time in these cases by having the Language to remember all the function values it finds.

For other languages there are, but for octave I could not find:

  1. https://reference.wolfram.com/language/tutorial/FunctionsThatRememberValuesTheyHaveFound.html
  2. Memoized recursive functions. How to make them fool-proof?
  3. How to improve ( mathematica ) performance when dealing with recursive functions?
  4. https://mathematica.stackexchange.com/q/18783 _ Functions that remember their values
  5. https://www.mathworks.com/matlabcentral/answers/163145-saving-values-in-a-recursive-function
  6. java retain information in recursive function
  7. Recursive Fibonacci memoization

This is mostly to optimize recursive functions calls as when calculating the factorial or Fibonacci number. This why we may save up and remove the exponencial complexity they have. Since otherwise intermediate computations have to be carried out several times, resulting in exponential complexity.

Community
  • 1
  • 1
Evandro Coan
  • 8,560
  • 11
  • 83
  • 144
  • 1
    This technique has a name: it's called [Memoization](https://en.wikipedia.org/wiki/Memoization). There's a very nice article entitled [how to use nested functions to memoize costly functions](http://blogs.mathworks.com/loren/2006/02/08/use-nested-functions-to-memoize-costly-functions/) on the matlab blog :) – Tasos Papastylianou Nov 08 '16 at 00:43

2 Answers2

2

As briefly mentioned in the MATLAB link in your question, you can use a persistent variable to retain your previous calculations.

Here's a test function using your example of calculating factorials:

function f = persistentFactorial(n)

   % declare variable factorials to be persistent
   persistent factorials

   computed = numel(factorials);
   if computed == 0
      % function called for the first time; initialize first element
      factorials(1) = 1;
      computed = 1;
   end

   if n > computed
      % fill in uncomputed factorials between computed and n
      % fprintf('calculating factorials between %d and %d\n', computed+1, n);
      factorials(computed+1:n) = computed+1:n;
      factorials(computed:n) = cumprod(factorials(computed:n));
   end

   % return requested factorial
   f = factorials(n);
end

If you call this function with the fprintf uncommented, you get something like this:

>> persistentFactorial(5)
calculating factorials between 2 and 5   % <-- first call to function
ans =  120
>> persistentFactorial(5)                % <-- second call; no new values
ans =  120
>> persistentFactorial(6)
calculating factorials between 6 and 6   % <-- third call; one new value
ans =  720

Note that if you want to clear the persistent variable, you can't access it directly from any other function, or even the command window, so you can't type clear factorials. You have to clear the function itself (or even just edit it):

clear persistentFactorial
beaker
  • 16,331
  • 3
  • 32
  • 49
0

Here is a different kind recursion than the @beaker using the Matlab/Octave persistent variables to implement the remember function.

It is tested only on Octave, for the Matlab version you will need to convert the comments form # to %, and other minor changes like this.

The full code may be found on this GitHub Repository: https://github.com/evandrocoan/ComputerScienceGraduation/tree/master/NumericalAnalysis/2016-2/Others/11.04_class22_Chebyshev

#
# Evaluate the t variable at the k'th Chebyshev Polynom
#
# i = 1 : n
# fChebyshev( i ) = b0*T0( t(i) ) + b1*T1( t(i) ) + b2*T2( t(i) ) + b3*T3( t(i) ) + ...
#
# @param k                           , the k'th Chebyshev Polynom.
# @param t                           , the value to evaluate at the k'th Chebyshev Polynom.
# @param isToDiscartTheSavedRecursion, true to indicate the current `t`'s Chebyshev Polynom sequence
#                                      must to be discarded. You must to always discard the old
#                                      sequence when a new `t` value is provided. Use false to
#                                      preserve the `t` cached values and use the recursion remember
#                                      feature.
#
function value = getChebyshevCoefficientsNumerically( k, t, isToDiscartTheSavedRecursion = true )

    persistent chebyshevPolynomCoefficients;
    chebyshevPolynomCoefficients;

    t_size   = numel( t );
    computed = numel( chebyshevPolynomCoefficients );

    # printf( 'Calling Chebyshev Polynom Coefficients with computed = %d, k = %d', computed, k );
    # printf( 'and t_size: %d \n', t_size );

    # When the function is called for the first time, initialize the first element and also reset
    # the old data, when a new variable `t` is calculated.
    if computed == 0 || isToDiscartTheSavedRecursion

        # printf( '\n\n\n\n\n( getChebyshevCoefficientsNumerically ) Cleaning ' );
        # printf(  'chebyshevPolynomCoefficients! computed: %d, k: %d\n', computed, k );

        for i = 1 : t_size

            chebyshevPolynomCoefficient( i ).vector = 1;

        end

        computed                     = 1;
        chebyshevPolynomCoefficients = chebyshevPolynomCoefficient;

    end

    t_size;
    t;
    k;
    chebyshevPolynomCoefficients.vector;

    for i = 1 : t_size

        # printf( '( getChebyshevCoefficientsNumerically ) Calculating the %dth t''s vector point.\n', i );
        [ value( i ), chebyshevPolynomCoefficients( i ).vector ] = getnthChebyshevCoefficientsNumerically( ...
                k, t( i ), chebyshevPolynomCoefficients( i ).vector );

    end

end

#
# Efficient Computation of Chebyshev Polynomials in Computer Algebra
# http://www.mathematik.uni-kassel.de/koepf/cheby.pdf
#
# Mathematics 4330/5344–#5 Approximation of Functions
# http://texas.math.ttu.edu/~gilliam/ttu/m4330/m4330_5.pdf
#
# Are there functions that remember values they have found on Octave?
# http://stackoverflow.com/questions/40445316/are-there-functions-that-remember-values-they-have-found-on-octave
#
# @param k                           , the k'th Chebyshev Polynom.
# @param t                           , the value to evaluate at the k'th Chebyshev Polynom.
# @param chebyshevPolynomCoefficients, a vector within the cached Chebyshev Polynom sequences.
#
function [ result, chebyshevPolynomCoefficients ] = ...
        getnthChebyshevCoefficientsNumerically( k, t, chebyshevPolynomCoefficients )

    t;
    computed = numel( chebyshevPolynomCoefficients );

    # printf( '( getnthChebyshevCoefficientsNumerically ) Calling with computed = ' );
    # printf( '%d and k = %d\n', computed, k );

    # Compute in uncomputed `chebyshevPolynomCoefficients`. The indexes are `k + 1` shifted because
    # the b's Chebyshev Polynom Coefficients starts on 0, but octave only allow indexes starting
    # at 1. This starts calculating all the missing b's Chebyshev Polynom from the index `computed`
    # until the requested coefficient `k`.
    if k + 1 > computed

        for i = computed : k

            # printf( '( getnthChebyshevCoefficientsNumerically ) Starting computing the %d ', i );
            # printf( 'coefficient of %d (k) coefficients.\n',  k );

            if i == 0

                chebyshevPolynomCoefficients( i + 1, : ) = 1;

            elseif i == 1

                chebyshevPolynomCoefficients( i + 1, : ) = t;

            elseif mod( i, 2 ) == 0

                chebyshevPolynomCoefficients( i + 1, : ) = 2.*getnthChebyshevCoefficientsNumerically( ...
                        i/2, t, chebyshevPolynomCoefficients ).^2 .- 1;

            else

                chebyshevPolynomCoefficients( i + 1, : ) = 2.*getnthChebyshevCoefficientsNumerically( ...
                        (i-1) / 2, t, chebyshevPolynomCoefficients ).*getnthChebyshevCoefficientsNumerically( ...
                        (i+1) / 2, t, chebyshevPolynomCoefficients ) - t;

            end

        end

    end

    k;
    chebyshevPolynomCoefficients;

    result = chebyshevPolynomCoefficients( k + 1 );

end

Sample Output with the Remember

This is a sample output with the recursion remember feature activated for the 9th Chebyshev Coefficient and with t = 0.6:

> T9_calcula = getChebyshevCoefficientsNumerically( 9, 0.6, false )

T9_correct = -0.472103423999999
Calling Chebyshev Polynom Coefficients with computed = 0, k = 9 and t_size: 1 
( getChebyshevCoefficientsNumerically ) Cleaning chebyshevPolynomCoefficients! computed: 0, k: 9
( getChebyshevCoefficientsNumerically ) Calculating the 1th t's vector point.
( getnthChebyshevCoefficientsNumerically ) Calling with computed = 1 and k = 9
( getnthChebyshevCoefficientsNumerically ) Starting computing the 1 coefficient of 9 (k) coefficients.
( getnthChebyshevCoefficientsNumerically ) Starting computing the 2 coefficient of 9 (k) coefficients.
( getnthChebyshevCoefficientsNumerically ) Calling with computed = 2 and k = 1
( getnthChebyshevCoefficientsNumerically ) Starting computing the 3 coefficient of 9 (k) coefficients.
( getnthChebyshevCoefficientsNumerically ) Calling with computed = 3 and k = 1
( getnthChebyshevCoefficientsNumerically ) Calling with computed = 3 and k = 2
( getnthChebyshevCoefficientsNumerically ) Starting computing the 4 coefficient of 9 (k) coefficients.
( getnthChebyshevCoefficientsNumerically ) Calling with computed = 4 and k = 2
( getnthChebyshevCoefficientsNumerically ) Starting computing the 5 coefficient of 9 (k) coefficients.
( getnthChebyshevCoefficientsNumerically ) Calling with computed = 5 and k = 2
( getnthChebyshevCoefficientsNumerically ) Calling with computed = 5 and k = 3
( getnthChebyshevCoefficientsNumerically ) Starting computing the 6 coefficient of 9 (k) coefficients.
( getnthChebyshevCoefficientsNumerically ) Calling with computed = 6 and k = 3
( getnthChebyshevCoefficientsNumerically ) Starting computing the 7 coefficient of 9 (k) coefficients.
( getnthChebyshevCoefficientsNumerically ) Calling with computed = 7 and k = 3
( getnthChebyshevCoefficientsNumerically ) Calling with computed = 7 and k = 4
( getnthChebyshevCoefficientsNumerically ) Starting computing the 8 coefficient of 9 (k) coefficients.
( getnthChebyshevCoefficientsNumerically ) Calling with computed = 8 and k = 4
( getnthChebyshevCoefficientsNumerically ) Starting computing the 9 coefficient of 9 (k) coefficients.
( getnthChebyshevCoefficientsNumerically ) Calling with computed = 9 and k = 4
( getnthChebyshevCoefficientsNumerically ) Calling with computed = 9 and k = 5
T9_calcula = -0.472103424000000

But is may also be called as:

> T9_calcula = getChebyshevCoefficientsNumerically( 9, [ 0.6, 0.7, 0.3 ], false )
Evandro Coan
  • 8,560
  • 11
  • 83
  • 144