Martin Rubey wrote:
>
> Well, I guess I first need to submit the package. I can then include a
> test, too.
>
> Concerning the package, I just noticed that I'm not completely satisfied
> with the representation (the interface is fine, in my opinion).
>
> Namely, I just had a computationally really expensive function
>
> n +-> f(n)
>
> but was only interested in the values
>
> (constant(1)*f)(n), which is just \sum_{d | n} f(d)
>
> However, due to the representation as streams, even if I only want to
> compute \sum_{d | n} f(d) for a specific n, say n=70, the package
> computes f(k) for all k in {1,2,...,70}, instead of just
> {1,2,5,7,10,14,35,70}. What a waste!
>
> So I was thinking of a representation like
>
> Rep := Stream Union(Coef, "not yet computed")
>
> and adapt elt and coerce accordingly. Actually, I'd really like
> something like
>
> Rep := PositiveInteger -> Coef
>
> which is however caching values. Or maybe I should just forget about
> the caching?
>
> What do you think?
>
I have noticed inefficiency, multiplying constant function by
itself needs 4.11 sec to compute term number 5000. I think
we can get much better efficiency using a version of Stream
which is buffering values using array (and growing the array
as needed). Then we can compute only needed values (we
still need to allocate space for all).
Alternatively, we could try to use hash table as a buffer.
On average n has about log n divisors so if we only need
single value gain may be significant. But if we need
many values then space gain is probably irrelevant and
we loose on access time.
--
Waldek Hebisch
[email protected]
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/fricas-devel?hl=en.
