Need help optimizing....

[JustSomeGuy]

I have a routine that evaluates a polynomial equation that have 3 variables
x,y,z of orders 1,2,3 the coefficients of the polynomial are in an array.
This routine is quite slow and I'd like to optimize it.
Any suggestions?

simply put pts is a vector of
typdef struct
double x;
double y;
double z;
double val;
} vect

xorder, yorder and zorder are the maximum polynomial exponents for an
equation
like val = fn(x,y,z).

void EvaluatePoly(Ve ctor<vect> & pts, int xorder, int yorder, int
zorder)
{
for (int pn=0; pn < pts.length(); ++pn)
{
int cn=0;
for (int k=0; k <= zorder; ++k)
{
float zexp = pow(pts[pn].z, k);
for (int j=0; j <= yorder; ++j)
{
float zyexp = zexp * pow(pts[pn].y, j);
for (int i=0; i <= xorder; ++i)
{
pts[pn].val = c[cn++] * pow(pts[pn].x, i) * zyexp;
}
}
}
}
}

[Kevin Goodsell]

Re: Need help optimizing....

JustSomeGuy wrote:
<snip>

Why did you cross-post this to several groups? Massive cross-posting is
very bad. I don't know the topics of all the groups, but I very much
doubt your question is topical in all of them.

If you feel the need to cross post to 2 or 3 groups, stop and think very
carefully about whether your message is topical in all of them. If you
feel the need to cross post to *more* than 2 or 3 groups, don't.

-Kevin
--
My email address is valid, but changes periodically.
To contact me please use the address from a recent posting.

[David B. Held]

Re: Need help optimizing....

"JustSomeGu y" <nope@nottellin g.com> wrote in message
news:MBtbb.8974 $TM4.4494@pd7tw 2no...[color=blue]
> I have a routine that evaluates a polynomial equation that
> have 3 variables x,y,z of orders 1,2,3 the coefficients of the
> polynomial are in an array. This routine is quite slow and I'd
> like to optimize it. Any suggestions?
> [...][/color]

Yes. 1) Don't cross-post to 9 newsgroups. You will almost
certainly receive a number of angry responses, which will
not help you solve your optimization problem (this is a
meta-optimization tip for the next time you have a question).
2) Take a look at Blitz++ and/or the GNU Scientific Library.
While I am not sure either one is totally relevant to your
problem, they might be. But your question is not a C++-
specific question (at least, not the way you framed it).
However, if you try Blitz++, it might become one. My
guess is that comp.programmin g would have been the
most appropriate group to try first.

Dave

[JustSomeGuy]

Re: Need help optimizing....


"David B. Held" <dheld@codelogi cconsulting.com > wrote in message
news:bklp3g$jsh $1@news.astound .net...[color=blue]
> "JustSomeGu y" <nope@nottellin g.com> wrote in message
> news:MBtbb.8974 $TM4.4494@pd7tw 2no...[color=green]
> > I have a routine that evaluates a polynomial equation that
> > have 3 variables x,y,z of orders 1,2,3 the coefficients of the
> > polynomial are in an array. This routine is quite slow and I'd
> > like to optimize it. Any suggestions?
> > [...][/color]
>
> Yes. 1) Don't cross-post to 9 newsgroups. You will almost
> certainly receive a number of angry responses, which will
> not help you solve your optimization problem (this is a
> meta-optimization tip for the next time you have a question).[/color]

People who get 'Angry' in regards to news group posting need to
seek help desperatly. But thanks for the info I will take in the
good spirit.

[color=blue]
> 2) Take a look at Blitz++ and/or the GNU Scientific Library.
> While I am not sure either one is totally relevant to your
> problem, they might be. But your question is not a C++-
> specific question (at least, not the way you framed it).
> However, if you try Blitz++, it might become one. My
> guess is that comp.programmin g would have been the
> most appropriate group to try first.
>[/color]

Thanks.
B.


[color=blue]
> Dave
>
>[/color]

[Gianni Mariani]

Re: Need help optimizing.... [Off topic]

JustSomeGuy wrote:[color=blue]
> I have a routine that evaluates a polynomial equation that have 3 variables
> x,y,z of orders 1,2,3 the coefficients of the polynomial are in an array.
> This routine is quite slow and I'd like to optimize it.
> Any suggestions?[/color]

Now that you have been significantly chastized for the massive cross
post, comp.lang.c++ is NOT the best NG for numerical stuff.

Not only that, optimization questions not relating to the C++ standard
are off topic in comp.lang.c++.

I'll however give you a few hints.

a) It seems like you may have done SOME profiling but let me state that
YOU REALLY NEED TO PROFILE THE CODE.

b) Let's assume you did some profiling and found that EvaluatePoly is
the culprit. You would have found that pow() was called a large number
of times more than EvaluatePoly.

c) Assuming EvaluatePoly needs to scream, I'd suggest making a small
test harness which allows you to run EvaluatePoly as a stand-alone app
and this will allow you to iterate your changes faster.

[color=blue]
>
> simply put pts is a vector of
> typdef struct
> double x;
> double y;
> double z;
> double val;
> } vect
>
> xorder, yorder and zorder are the maximum polynomial exponents for an
> equation
> like val = fn(x,y,z).
>
> void EvaluatePoly(Ve ctor<vect> & pts, int xorder, int yorder, int
> zorder)
> {
> for (int pn=0; pn < pts.length(); ++pn)
> {
> int cn=0;
> for (int k=0; k <= zorder; ++k)
> {
> float zexp = pow(pts[pn].z, k);[/color]
^^^^^^^^^^^^^^^ ^^^^^^^^^^ why floats ?
^^^^^^^^^^^^^^^ ^^^^^^^^^^ why call pow ? These may be computed using
multiplication per iterarion. Significantly fast[color=blue]
> for (int j=0; j <= yorder; ++j)
> {
> float zyexp = zexp * pow(pts[pn].y, j);[/color]
^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^ why floats ?[color=blue]
> for (int i=0; i <= xorder; ++i)
> {
> pts[pn].val = c[cn++] * pow(pts[pn].x, i) * zyexp;[/color]
^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^ ^^^^^^^^^^^
what is this ? don't you want this to be a sum of all the terms ?
[color=blue]
> }
> }
> }
> }
> }
>
>[/color]


So, give this a go. Compared to what is above, it should be
significantly faster and it might actually work.

Without knowing the data set, it's kind of hard to know better what you
need.


#include <vector>

typedef struct {
double x;
double y;
double z;
double val;
} vect;


void EvaluatePoly(
std::vector<vec t> & pts,
int xorder,
int yorder,
int zorder,
double * c
)
{

std::vector<vec t>::iterator p_pts = pts.begin();
std::vector<vec t>::iterator pts_end = pts.end();

for (; p_pts != pts_end; ++ p_pts )
{
int cn=0;

double val_x = p_pts->x;
double val_y = p_pts->y;
double val_z = p_pts->z;

double sum = 0;
double pow_z = 1;
for (int k=0; k <= zorder; ++k)
{
double pow_y = pow_z;
for (int j=0; j <= yorder; ++j)
{
double pow_x = pow_y;
for (int i=0; i <= xorder; ++i)
{
sum += c[cn++] * pow_x;

pow_x *= val_x;
}

pow_y *= val_y;
}

pow_z *= val_z;
}

p_pts->val = sum;
}
}

[Robert Vienneau]

Re: Need help optimizing....

It may be helpful to realize:

a*x^3 + b*x^2 + c*x + d = d + x*(c + b*(x + a*x))

and so on.

I think that's called Horner's rule, and it is a standard trick when
optimizing the evalutaion of polynomials.

--
Try http://csf.colorado.edu/pkt/pktautho.../Bukharin.html
To solve Linear Programs: .../LPSolver.html
r c A game: .../Keynes.html
v s a Whether strength of body or of mind, or wisdom, or
i m p virtue, are found in proportion to the power or wealth
e a e of a man is a question fit perhaps to be discussed by
n e . slaves in the hearing of their masters, but highly
@ r c m unbecoming to reasonable and free men in search of
d o the truth. -- Rousseau

[LibraryUser]

Re: Need help optimizing....

JustSomeGuy wrote:[color=blue]
> "David B. Held" <dheld@codelogi cconsulting.com > wrote in message[color=green]
> > "JustSomeGu y" <nope@nottellin g.com> wrote in message
> >[color=darkred]
> > > I have a routine that evaluates a polynomial equation that
> > > have 3 variables x,y,z of orders 1,2,3 the coefficients of
> > > the polynomial are in an array. This routine is quite slow
> > > and I'd like to optimize it. Any suggestions?
> > > [...][/color]
> >
> > Yes. 1) Don't cross-post to 9 newsgroups. You will almost
> > certainly receive a number of angry responses, which will
> > not help you solve your optimization problem (this is a
> > meta-optimization tip for the next time you have a question).[/color]
>
> People who get 'Angry' in regards to news group posting need to
> seek help desperatly. But thanks for the info I will take in the
> good spirit.[/color]

Inconsiderate people who do such massive crossposting need the
help. This leads to interminable off-topic threads and
continuous annoyance. Once the original post is made the harm is
done.

Usually any originally cross-posted queries should include a
followup to the single most appropriate newsgroup. That allows a
query to be spread over 3 or 4 groups, without the penalties.
Note that many of the better ISPs simply destroy any messages
crossposted to an excessive extent. If not, the better
newsreaders will automatically reject them. So the whole
business is counter-productive.

--
Replies should be to the newsgroup
Chuck Falconer, on vacation.

[JustSomeGuy]

Re: Need help optimizing....


"Robert Vienneau" <rvien@see.sig. com> wrote in message
news:rvien-8F0BC7.05264622 092003@news.dre amscape.com...[color=blue]
> It may be helpful to realize:
>
> a*x^3 + b*x^2 + c*x + d = d + x*(c + b*(x + a*x))
>
> and so on.
>
> I think that's called Horner's rule, and it is a standard trick when
> optimizing the evalutaion of polynomials.
>[/color]

I think your are right....

horner's rule in c.

n=5, p=c[n];
for (j=n-1; j >=0; j=j-1)
p *= x + c[j];

however I wonder how well, or even if its possible, to do this
with and equation with 3 variables, as in my example?

check this out.

http://www.dspguru.com/comp.dsp/tricks/alg/horner.htm

ps someone was awake enough to see the error
pts[pn].val = c[cn++] * pow(pts[pn].x, i) * zyexp;
which should have been:
pts[pn++].val = c[cn++] * pow(pts[pn].x, i) * zyexp;

So if any one has any suggestions on using this trick with more than one
variable let me know please.

[JustSomeGuy]

Re: Need help optimizing.... [Off topic]


"Gianni Mariani" <gi2nospam@mari ani.ws> wrote in message
news:bkm68m$qej @dispatch.conce ntric.net...[color=blue]
> JustSomeGuy wrote:[color=green]
> > I have a routine that evaluates a polynomial equation that have 3[/color][/color]
variables[color=blue][color=green]
> > x,y,z of orders 1,2,3 the coefficients of the polynomial are in an[/color][/color]
array.[color=blue][color=green]
> > This routine is quite slow and I'd like to optimize it.
> > Any suggestions?[/color]
>
> Now that you have been significantly chastized for the massive cross
> post, comp.lang.c++ is NOT the best NG for numerical stuff.
>
> Not only that, optimization questions not relating to the C++ standard
> are off topic in comp.lang.c++.
>
> I'll however give you a few hints.
>
> a) It seems like you may have done SOME profiling but let me state that
> YOU REALLY NEED TO PROFILE THE CODE.
>
> b) Let's assume you did some profiling and found that EvaluatePoly is
> the culprit. You would have found that pow() was called a large number
> of times more than EvaluatePoly.
>
> c) Assuming EvaluatePoly needs to scream, I'd suggest making a small
> test harness which allows you to run EvaluatePoly as a stand-alone app
> and this will allow you to iterate your changes faster.
>
>[color=green]
> >
> > simply put pts is a vector of
> > typdef struct
> > double x;
> > double y;
> > double z;
> > double val;
> > } vect
> >
> > xorder, yorder and zorder are the maximum polynomial exponents for an
> > equation
> > like val = fn(x,y,z).
> >
> > void EvaluatePoly(Ve ctor<vect> & pts, int xorder, int yorder, int
> > zorder)
> > {
> > for (int pn=0; pn < pts.length(); ++pn)
> > {
> > int cn=0;
> > for (int k=0; k <= zorder; ++k)
> > {
> > float zexp = pow(pts[pn].z, k);[/color]
> ^^^^^^^^^^^^^^^ ^^^^^^^^^^ why floats ?
> ^^^^^^^^^^^^^^^ ^^^^^^^^^^ why call pow ? These may be computed using
> multiplication per iterarion. Significantly fast[color=green]
> > for (int j=0; j <= yorder; ++j)
> > {
> > float zyexp = zexp * pow(pts[pn].y, j);[/color]
> ^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^ why floats ?[color=green]
> > for (int i=0; i <= xorder; ++i)
> > {
> > pts[pn].val = c[cn++] * pow(pts[pn].x, i) *[/color][/color]
zyexp;[color=blue]
> ^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^ ^^^^^^^^^^^
> what is this ? don't you want this to be a sum of all the terms ?
>[color=green]
> > }
> > }
> > }
> > }
> > }
> >
> >[/color]
>
>
> So, give this a go. Compared to what is above, it should be
> significantly faster and it might actually work.
>
> Without knowing the data set, it's kind of hard to know better what you
> need.
>[/color]

Yes I've gotten rid of the pow function and I've also started looking
into horner's rule, but I'm not sure I can apply it to polynomials with more
than one variable. If anyone knows... please let me know.




[color=blue]
>
> #include <vector>
>
> typedef struct {
> double x;
> double y;
> double z;
> double val;
> } vect;
>
>
> void EvaluatePoly(
> std::vector<vec t> & pts,
> int xorder,
> int yorder,
> int zorder,
> double * c
> )
> {
>
> std::vector<vec t>::iterator p_pts = pts.begin();
> std::vector<vec t>::iterator pts_end = pts.end();
>
> for (; p_pts != pts_end; ++ p_pts )
> {
> int cn=0;
>
> double val_x = p_pts->x;
> double val_y = p_pts->y;
> double val_z = p_pts->z;
>
> double sum = 0;
> double pow_z = 1;
> for (int k=0; k <= zorder; ++k)
> {
> double pow_y = pow_z;
> for (int j=0; j <= yorder; ++j)
> {
> double pow_x = pow_y;
> for (int i=0; i <= xorder; ++i)
> {
> sum += c[cn++] * pow_x;
>
> pow_x *= val_x;
> }
>
> pow_y *= val_y;
> }
>
> pow_z *= val_z;
> }
>
> p_pts->val = sum;
> }
> }
>[/color]

[Gianni Mariani]

Re: Need help optimizing.... [Off topic]

JustSomeGuy wrote:[color=blue]
> "Gianni Mariani" <gi2nospam@mari ani.ws> wrote in message
> news:bkm68m$qej @dispatch.conce ntric.net...
>[color=green]
>>JustSomeGuy wrote:
>>[color=darkred]
>>>I have a routine that evaluates a polynomial equation that have 3[/color][/color][/color]
....[color=blue][color=green]
>>
>>So, give this a go. Compared to what is above, it should be
>>significant ly faster and it might actually work.
>>
>>Without knowing the data set, it's kind of hard to know better what you
>>need.
>>[/color]
>
>
> Yes I've gotten rid of the pow function and I've also started looking
> into horner's rule, but I'm not sure I can apply it to polynomials with more
> than one variable. If anyone knows... please let me know.
>[/color]

Horner's rule only effects the inner loop but in this case it does not
save you anything because there are still 2 multiplies and an add per
inner loop iteration.

Here it is,

horner_sum = *(coef--)*pow_y + horner_sum * val_x;

- 2 multiplies and an add

The first code I wrote

sum += c[cn++] * pow_x;
pow_x *= val_x;

- two multiplies and an add !

I would go for simple.


#include <cmath>
#include <vector>

typedef struct {
double x;
double y;
double z;
double val;
} vect;


void EvaluatePoly(
std::vector<vec t> & pts,
int xorder,
int yorder,
int zorder,
double * c
)
{

std::vector<vec t>::iterator p_pts = pts.begin();
std::vector<vec t>::iterator pts_end = pts.end();

for (; p_pts != pts_end; ++ p_pts )
{
int cn=0;

double val_x = p_pts->x;
double val_y = p_pts->y;
double val_z = p_pts->z;

double sum = 0;
double pow_z = 1;
for (int k=0; k <= zorder; ++k)
{
double pow_y = pow_z;
for (int j=0; j <= yorder; ++j)
{
double horner_sum = 0;
double * coef = c + cn + xorder + 1;
for (int i=xorder; i >= 0; i --)
{
horner_sum = *(coef--)*pow_y + horner_sum * val_x;
}

cn += xorder + 1;
sum += horner_sum;

pow_y *= val_y;
}

pow_z *= val_z;
}

p_pts->val = sum;
}
}

[Doug Norris]

Re: Need help optimizing....

"JustSomeGu y" <nope@nottellin g.com> writes:
[color=blue]
>"David B. Held" <dheld@codelogi cconsulting.com > wrote in message
>news:bklp3g$js h$1@news.astoun d.net...[color=green]
>>
>> Yes. 1) Don't cross-post to 9 newsgroups. You will almost
>> certainly receive a number of angry responses, which will
>> not help you solve your optimization problem (this is a
>> meta-optimization tip for the next time you have a question).[/color][/color]
[color=blue]
>People who get 'Angry' in regards to news group posting need to
>seek help desperatly. But thanks for the info I will take in the
>good spirit.[/color]

People who read what David wrote to you and infer that he's "angry"
need to either (1) read it again, or (2) read it again. HTH.

Doug

[jeffc]

Re: Need help optimizing....


"Doug Norris" <norrisdt@rinti ntin.colorado.e du> wrote in message
news:norrisdt.1 064328441@rinti ntin.colorado.e du...[color=blue]
> "JustSomeGu y" <nope@nottellin g.com> writes:
>[color=green]
> >"David B. Held" <dheld@codelogi cconsulting.com > wrote in message
> >news:bklp3g$js h$1@news.astoun d.net...[color=darkred]
> >>
> >> Yes. 1) Don't cross-post to 9 newsgroups. You will almost
> >> certainly receive a number of angry responses, which will
> >> not help you solve your optimization problem (this is a
> >> meta-optimization tip for the next time you have a question).[/color][/color]
>[color=green]
> >People who get 'Angry' in regards to news group posting need to
> >seek help desperatly. But thanks for the info I will take in the
> >good spirit.[/color]
>
> People who read what David wrote to you and infer that he's "angry"
> need to either (1) read it again, or (2) read it again. HTH.[/color]

I don't think SomeGuy inferred that David was angry any more than David
implied it to begin with. They were both speaking in the third person, no?

[Slartibartfast]

Re: Need help optimizing....

"Doug Norris" <norrisdt@rinti ntin.colorado.e du> wrote in message news:norrisdt.1 064328441@rinti ntin.colorado.e du...[color=blue]
> "JustSomeGu y" <nope@nottellin g.com> writes:
>[color=green]
> >"David B. Held" <dheld@codelogi cconsulting.com > wrote in message
> >news:bklp3g$js h$1@news.astoun d.net...[color=darkred]
> >>
> >> Yes. 1) Don't cross-post to 9 newsgroups. You will almost
> >> certainly receive a number of angry responses, which will
> >> not help you solve your optimization problem (this is a
> >> meta-optimization tip for the next time you have a question).[/color][/color]
>[color=green]
> >People who get 'Angry' in regards to news group posting need to
> >seek help desperatly. But thanks for the info I will take in the
> >good spirit.[/color]
>
> People who read what David wrote to you and infer that he's "angry"
> need to either (1) read it again, or (2) read it again. HTH.[/color]

People who think that "JustSomeGu y" was referring to David himself,
rather than to the senders of the "number of angry responses" to which
David refers, need to either (1) read it again, or (2) read it again. HTH.

--
#include <stdio.h>
char*f="#includ e <stdio.h>%cchar *f=%c%s%c;%cint main(void){prin tf(f,10,34,f,34 ,10,10);return 0;}%c";
int main(void){prin tf(f,10,34,f,34 ,10,10);return 0;}

[Robert Vienneau]

Re: Need help optimizing....

In article <bko9op$1348$1@ nserve1.acs.uca lgary.ca>, "JustSomeGu y"
<nope@nottellin g.com> wrote:
[color=blue]
> "Robert Vienneau" <rvien@see.sig. com> wrote in message
> news:rvien-8F0BC7.05264622 092003@news.dre amscape.com...[color=green]
> > It may be helpful to realize:
> >
> > a*x^3 + b*x^2 + c*x + d = d + x*(c + b*(x + a*x))
> >
> > and so on.
> >
> > I think that's called Horner's rule, and it is a standard trick when
> > optimizing the evalutaion of polynomials.[/color][/color]
[color=blue]
> I think your are right....
>
> horner's rule in c.
>
> n=5, p=c[n];
> for (j=n-1; j >=0; j=j-1)
> p *= x + c[j];
>
> however I wonder how well, or even if its possible, to do this
> with and equation with 3 variables, as in my example?[/color]

I did not look at your code too closely. But frequently one can
reverse the order of nested loops. Can you do such? And will it
make some such trick as Horner's rule useful?
[color=blue]
> check this out.
> http://www.dspguru.com/comp.dsp/tricks/alg/horner.htm[/color]

--
Try http://csf.colorado.edu/pkt/pktautho.../Bukharin.html
To solve Linear Programs: .../LPSolver.html
r c A game: .../Keynes.html
v s a Whether strength of body or of mind, or wisdom, or
i m p virtue, are found in proportion to the power or wealth
e a e of a man is a question fit perhaps to be discussed by
n e . slaves in the hearing of their masters, but highly
@ r c m unbecoming to reasonable and free men in search of
d o the truth. -- Rousseau

[JustSomeGuy]

Re: Need help optimizing....


"jeffc" <nobody@nowhere .com> wrote in message
news:3f7062a1_4 @news1.prserv.n et...[color=blue]
>
> "Doug Norris" <norrisdt@rinti ntin.colorado.e du> wrote in message
> news:norrisdt.1 064328441@rinti ntin.colorado.e du...[color=green]
> > "JustSomeGu y" <nope@nottellin g.com> writes:
> >[color=darkred]
> > >"David B. Held" <dheld@codelogi cconsulting.com > wrote in message
> > >news:bklp3g$js h$1@news.astoun d.net...
> > >>
> > >> Yes. 1) Don't cross-post to 9 newsgroups. You will almost
> > >> certainly receive a number of angry responses, which will
> > >> not help you solve your optimization problem (this is a
> > >> meta-optimization tip for the next time you have a question).[/color]
> >[color=darkred]
> > >People who get 'Angry' in regards to news group posting need to
> > >seek help desperatly. But thanks for the info I will take in the
> > >good spirit.[/color]
> >
> > People who read what David wrote to you and infer that he's "angry"
> > need to either (1) read it again, or (2) read it again. HTH.[/color]
>
> I don't think SomeGuy inferred that David was angry any more than David
> implied it to begin with. They were both speaking in the third person,[/color]
no?[color=blue]
>
>[/color]
Correct, I didn't think Dave was angry... Simply stating a fact.