Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: [Pari/GP] Extreme run-time effect when expression was un-optimized
Replies: 11   Last Post: Nov 6, 2011 3:36 PM

 Messages: [ Previous | Next ]
 Gottfried Helms Posts: 1,926 Registered: 12/6/04
[Pari/GP] Extreme run-time effect when expression was un-optimized
Posted: Nov 5, 2011 12:30 PM

Hi -
I've got an extreme effect of the rewriting of a
relatively simple formula.
I've done three versions of the same formula; it is
the iteration of

g(x) = (sqrt(1+x)-x)^2 - 1

in principle by a call like this:

f(x,h) = for(k=1,h, x = g(x)); return (x )

I worked with float precison of 200 digits.
----------------------------------------------------------------
That was the initial idea.

Somehow innocently I tried to do a small optimization . First
I made the function-expression explicite in f(x,h) to avoid overhead
of function calls:

f (x,h) = for(k=1,h,x = (sqrt(1+x) -x)^2-1 );x

Then I thought, possibly it would be better to expand the squaring:

f2(x,h) = for(k=1,h,x = x - 2*x*sqrt(1+x) + x^2 );x

and finally to take benefit from the more concise notation for
the process of updating of a variable's value in the memory:

f3(x,h)=for(k=1,h,x *= ((1+x)-2*sqrt(1+x)) );x

Then I let the three versions repeat 1200 times
h = 1200
\\ call of function \\ iter result time
[h,f (1.0,h),gettime] [1200, 0.0406225463413, 4078]
[h,f2 (1.0,h),gettime] [1200, 0.0406225463413, 47]
[h,f3 (1.0,h),gettime] [1200, 0.0406225463413, 46]

Well, I would already like to know how that nearly 100-fold time consumtion
can be explained.

But more: if I simply double the iteration height, then in the original
f (x,h) version there occurs time-consumtion which I cannot understand
at all:

h=2400
\\ call of function \\ iter result time
[h,f (1.0,h),gettime] [2400, 0.0287900934710, 42235]
[h,f2 (1.0,h),gettime] [2400, 0.0287900934710, 93]
[h,f3 (1.0,h),gettime] [2400, 0.0287900934710, 79]

The f(x,h)-version does not only double its time-consumtion but
needs nearly the 10-fold time now. How can this happen?

Gottfried Helms