optimization of an order n^3- routine
- From: Gottfried Helms <helms@xxxxxxxxxxxxx>
- Date: Sun, 17 Feb 2008 09:31:14 +0100
Hi -
don't know, whether this is the appropriate newsgroup for
this algorithmic question; - anyway, here it goes.
To evaluate f(b,x) = b^b^b^x I've a routine, which uses
conversion of f(b,x) into
sum {k=0..inf} g(b)^k * h(x,k)
where h(x,k) is a routine of quadratic order but is
independent of b, so -assumed constant x (for simpliness
x=1 may be assumed) I could store the values for h(x,k)
in a vector of sufficient length. Sufficient means here,
because h(x,k) is convergent for k->inf, and even approaches
zero faster than g(b)^k diverges, some couple of hundred
entries for say, k<500.
I could principally use a matrix, but a matrix of 500x500
seems to be too big for my purposes. So I ask here for
possibly better implementation of dynamic computation, possibly
keeping few vectors of length ~ 500 in memory.
The function goes like this
\\ most inner loop
t3s2(x,r0,r1) = sum(r2=0,r1, (r0-r1)^(r1-r2) / (r1-r2)! * (r1-r2)^r2 / r2! * x^r2 )
\\ second inner loop
t3s1(x,r0) = sum(r1=0,r0, 1 / (r0-r1)! * t3s2(x,r0,r1))
\\ outer loop
t3s0(b,x,r0max)=local(lb=log(b)); sum(r0=0,r0max, lb^r0 * t3s1(x,r0))
Then, for b=1.5 or b=2.0 (x=1.0) I need 40 or 60 terms to get convergence
and approximation up to 10 or 12 digits
for(k=1,50,print(k," ",t3s0(1.5,1.0,k))); \\ b=1.5 40 Terms
for(k=1,70,print(k," ",t3s0(2.0,1.0,k))); \\ b=2.0 60 Terms
It is obvious, that at least the factorials could be precomputed
and stored in a vector of length r0max. The powers (r0-r1)^(r1-r2)
could be precomputed as well and stored in a matrix - but this
needed then the size of r0max * r0max , which I don't want.
To accelerate I tried to rewrite this, using binomials and extracting
constant terms as much out as possible, so I have this other version:
\\ Alternative (only sketch: the (r0-r1)=0 -case is not yet properly respected in t3s2)
t3s2(x,r0,r1) = sum(r2=0,r1, (r1-r2)^r2 * binomial(r1,r2) * (x/(r0-r1))^r2 )
t3s1(x,r0) = sum(r1=0,r0, (r0-r1)^r1 * binomial(r0,r1) * t3s2(x,r0,r1) )
t3s0(b,x,r0max)=local(lb=log(b));
sum(r0=0,r0max, lb^r0/r0! * t3s1(x,r0))
Does someone see a better optimization?
Gottfried
--
---
Gottfried Helms, Kassel
.
- Prev by Date: Re: solution manual to david j. griffiths' introduction to electrodynamics 3rd edition
- Next by Date: a question regarding optimization theory
- Previous by thread: Digital Communications by Bernard Sklar
- Next by thread: a question regarding optimization theory
- Index(es):
Relevant Pages
|
