[racket] Math - factorial.rkt, binomial.rkt and memoization

On Mon, Apr 8, 2013 at 9:34 PM, Jens Axel Søgaard <jensaxel at soegaard.net>wrote:

> > Would it make sense to use memoization more broadly for the definition
> of the factorial
> > in the math lib, maybe with a `provide'd parameter to control how many
> values can be
> > memoized?
>
> An interesting question. First of all it seems that especially binomial
> can be improved. Second I think there is a difference between
> non-permanent caching and permanent caching. I see no problem
> with non-permanent caching. For caching between calls I am not
> sure, what is the best solution for a general purpose library.
> I lean towards non-caching functions as standard, but it would
> be nice to offer both versions in the library. The same problem
> arises in prime? . Having a large table of small primes
> improve the running time, but is a reasonable table
> size 10^3, 10^4 or 10^5 ?
>

Hence the idea of the parameter (or several?), with a default correct
general value that can be changed by the user.

Btw, the factorial table uses some unnecessary memory space (though not
that big anyway), I think it would be better to request memory on demand.
Memoization with a hash table does exactly that, although a growable vector
would fit too.
I guess the same goes for `prime?' and maybe other places?

Laurent
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20130409/8cce731f/attachment-0001.html>