small integer powers -- use pow() or explicit multiplication?

B

blmblm

Maybe a style question, though there could be efficiency issues
too .... :

I teach beginning/intermediate programming to university
students, and I've noticed that they often want to use pow() to
compute small integer powers (squares, e.g.) where I would use
explicit multiplication. Is there a "best practice" on this one?
I'm thinking that the tradeoffs are something like the following:

Explicit multiplication might be more efficient -- but a smart
enough compiler might transform pow(x, 2) into x*x.

Using pow() might be clearer, and if the thing to be raised to a
power is an expression, it avoids writing the expression twice,
which makes the code shorter and avoids a source of possible error.

I've almost convinced myself here that the students are right,
but to me explicit multiplication still seems more idiomatic.
Am I completely off-base here, perhaps having developed bad habits
in an era in which compilers were less smart?
 
R

Rich Webb

Maybe a style question, though there could be efficiency issues
too .... :

I teach beginning/intermediate programming to university
students, and I've noticed that they often want to use pow() to
compute small integer powers (squares, e.g.) where I would use
explicit multiplication. Is there a "best practice" on this one?
I'm thinking that the tradeoffs are something like the following:

Explicit multiplication might be more efficient -- but a smart
enough compiler might transform pow(x, 2) into x*x.

Using pow() might be clearer, and if the thing to be raised to a
power is an expression, it avoids writing the expression twice,
which makes the code shorter and avoids a source of possible error.

I've almost convinced myself here that the students are right,
but to me explicit multiplication still seems more idiomatic.
Am I completely off-base here, perhaps having developed bad habits
in an era in which compilers were less smart?

My general rule of thumb: Don't try to out-optimize the compiler. If,
after profiling, it happens that a given section of code is a
significant bottleneck, then first look for a better overall algorithm
and only then use tricks to try to speed things up.

I think that your comment "Using pow() might be clearer, and if the
thing to be raised to a power is an expression, it avoids writing the
expression twice, which makes the code shorter and avoids a source of
possible error." answers the question.
 
U

user923005

Maybe a style question, though there could be efficiency issues
too .... :

I teach beginning/intermediate programming to university
students, and I've noticed that they often want to use pow() to
compute small integer powers (squares, e.g.) where I would use
explicit multiplication.  Is there a "best practice" on this one?
I'm thinking that the tradeoffs are something like the following:

Explicit multiplication might be more efficient -- but a smart
enough compiler might transform pow(x, 2) into x*x.

Using pow() might be clearer, and if the thing to be raised to a
power is an expression, it avoids writing the expression twice,
which makes the code shorter and avoids a source of possible error.

I've almost convinced myself here that the students are right,
but to me explicit multiplication still seems more idiomatic.
Am I completely off-base here, perhaps having developed bad habits
in an era in which compilers were less smart?

It's not important which one is chosen unless a bad choice causes
performance problems.

I think it is best to write code that most clearly expresses the
intentions.
After writing the code, if performance problems arise, then profile
it.

Something like pow(x,k) verses explicit multiplication with an
integral power k is very unlikely to cause any problem unless it is in
a nested loop.

Personally, I think that:
y = x * x;
and:
y = pow(x,2);
have about the same clarity.

I would probably write 'x * x' but I don't really think it is superior
to pow(x,2).

If k is a large integer, I think it likely that pow(x,k) will do a
better job than a simple expansion, since it may do a recursive
mulitplication.
Also, the pow() call becomes more and more clear as k increases.

For instance, consider:
y = pow(x,13);
verses:
y = x * x * x * x * x * x * x * x * x * x * x * x * x;

Is the loss of clarity worth some imagined gain in efficiency (that
may not materialize anyway)?

So, I suggest:
1. Make the code as clear and expressive as possible -- communicating
the algorithm in the cleanest and easiest to understand way at your
disposal.
2. If {and ONLY if} it is too slow, profile it.
A. Once you have found the slow parts, consider improving the
fundamental, underlying algorithm
B. If you cannot improve the algorithm, consider tweaky things to
speed up the code enough to pass the timing specification.

IMO-YMMV
 
K

Keith Thompson

Maybe a style question, though there could be efficiency issues
too .... :

I teach beginning/intermediate programming to university
students, and I've noticed that they often want to use pow() to
compute small integer powers (squares, e.g.) where I would use
explicit multiplication. Is there a "best practice" on this one?
[...]

If the first operand is floating-point, it probably doesn't make much
difference. If it's an integer, I'd use explicit multiplication to
avoid possible rounding errors.
 
B

Bartc

Maybe a style question, though there could be efficiency issues
too .... :

I teach beginning/intermediate programming to university
students, and I've noticed that they often want to use pow() to
compute small integer powers (squares, e.g.) where I would use
explicit multiplication. Is there a "best practice" on this one?
I'm thinking that the tradeoffs are something like the following:

Explicit multiplication might be more efficient -- but a smart
enough compiler might transform pow(x, 2) into x*x.

Using pow() might be clearer, and if the thing to be raised to a
power is an expression, it avoids writing the expression twice,
which makes the code shorter and avoids a source of possible error.

I've almost convinced myself here that the students are right,
but to me explicit multiplication still seems more idiomatic.
Am I completely off-base here, perhaps having developed bad habits
in an era in which compilers were less smart?

Create a small macro or function to calculate squares or cubes of integers.

The result will be as clear or clearer than using pow(), can probably be
optimised, and you run no risk of activating the floating point unit.
 
U

user923005

Create a small macro or function to calculate squares or cubes of integers.

The result will be as clear or clearer than using pow(), can probably be
optimised, and you run no risk of activating the floating point unit.

Function macros are evil.

#define SQUARE(x) (x*x)
#define CUBE(x) (x*x*x)
....
y = SQUARE(x++); // undefined behavior
z = CUBE(++x); // ditto

The floating point unit is not a penalty like it was in the old days.
 
K

Keith Thompson

user923005 said:
Function macros are evil.

#define SQUARE(x) (x*x)
#define CUBE(x) (x*x*x)

I think you mean:

#define SQUARE(x) ((x)*(x))
#define CUBE(x) ((x)*(x)*(x))

though the parentheses don't help the following:
...
y = SQUARE(x++); // undefined behavior
z = CUBE(++x); // ditto

However, the use of an all-caps name should warn the programmer that
this is a macro, and that arguments with side effects are to be
avoided.

Of course you can use an inline function if your compiler supports it.
The floating point unit is not a penalty like it was in the old days.

True (though I suppose it might be on some systems), but there's
still the risk of roundoff error. On any sane implementation,
pow(2.0, 2.0) == 4.0, but implementations aren't required to be sane.
It's conceivable that pow(2.0, 2.0) could yield 3.999999999...;
then this:
int two_squared = pow(2, 2);
would set two_squared to 3.

Perhaps no current real-world systems have this problem, but
personally I'd rather write ``2 * 2'' than have to think about whether
pow() is going to do what I want after all the implicit conversions
settle out.
 
N

Nate Eldredge

Keith Thompson said:
True (though I suppose it might be on some systems), but there's
still the risk of roundoff error. On any sane implementation,
pow(2.0, 2.0) == 4.0, but implementations aren't required to be sane.
It's conceivable that pow(2.0, 2.0) could yield 3.999999999...;
then this:
int two_squared = pow(2, 2);
would set two_squared to 3.

Perhaps no current real-world systems have this problem, but
personally I'd rather write ``2 * 2'' than have to think about whether
pow() is going to do what I want after all the implicit conversions
settle out.

In fact, on my amd64 machine, where `double' is IEEE 754
double-precision with a 53-bit mantissa, we have

pow(3, 35) == 50031545098999704.000000

But the true value is 50031545098999707. This value fits in a 64-bit
`long int' and can be obtained by a simple multiplication loop.

It appears that you get the correct answer from `pow' if the result is
smaller than 2^53 or is a power of 2. Otherwise all bets are off.

Also, the loop appears to be faster by a factor of 3 or so, even for
exponents as large as 35.

I think this is a pretty strong argument for avoiding the use of `pow'
for integers.
 
K

Keith Thompson

Nate Eldredge said:
In fact, on my amd64 machine, where `double' is IEEE 754
double-precision with a 53-bit mantissa, we have

pow(3, 35) == 50031545098999704.000000

But the true value is 50031545098999707. This value fits in a 64-bit
`long int' and can be obtained by a simple multiplication loop.

It appears that you get the correct answer from `pow' if the result is
smaller than 2^53 or is a power of 2. Otherwise all bets are off.

Sure, that's to be expected with a 53-bit mantissa.

But the potential problem I was referring to was where, even though
the mathematical result of pow(2.0, 2.0) can be represented exactly,
the computed result is still a little off. The C standard's
requirements for floating-point aren't strict enough to forbid this.
Also, the loop appears to be faster by a factor of 3 or so, even for
exponents as large as 35.

And for integer exponents (with the first operand being either integer
or floating-point), there are tricks you can do with squaring that
reduce the number of multiplications needed. For example, x**8 is
square(square(square(x))), for 3 multiplications rather than 7; x**9
is x * square(square(square(x))), and so forth.
 
B

Bartc

user923005 said:
Function macros are evil.

#define SQUARE(x) (x*x)
#define CUBE(x) (x*x*x)
...
y = SQUARE(x++); // undefined behavior
z = CUBE(++x); // ditto

Using x++ * x++ is much better defined of course.
The floating point unit is not a penalty like it was in the old days.

I've just tested gcc on x86 and even with -O3 optimisation, doing pow(A,2)
requires half a dozen instructions, some of them floating point, plus a call
to pow() with who knows how much complex code inside it.

On the other hand A*A or SQR(A) would take two integer instructions. Even an
int function sqr() would be faster, and in fact gcc -O3 seems to inline
this.
 
B

Bartc

blargg said:
Bartc said:
Maybe a style question, though there could be efficiency issues
too .... :

I teach beginning/intermediate programming to university
students, and I've noticed that they often want to use pow() to
compute small integer powers (squares, e.g.) where I would use
explicit multiplication. Is there a "best practice" on this one?
I'm thinking that the tradeoffs are something like the following:
[...]
Create a small macro or function to calculate squares or cubes of
integers.

The result will be as clear or clearer than using pow(), can
probably be optimised, and you run no risk of activating the
floating point unit.

I think that

x*x

will generally be clearer than

square(x)

Try x[i+j][k-i]*x[i+j][k-1] and see if it's still clearer than
sqr(x[i+j][k-i]), and as correct. And remember any maintenance on the term
has to be done twice.

And you have to rely on the compiler to avoid evaluating the term twice as
well.
 
E

Eric Sosman

Maybe a style question, though there could be efficiency issues
too .... :

I teach beginning/intermediate programming to university
students, and I've noticed that they often want to use pow() to
compute small integer powers (squares, e.g.) where I would use
explicit multiplication. Is there a "best practice" on this one?
I'm thinking that the tradeoffs are something like the following:

Explicit multiplication might be more efficient -- but a smart
enough compiler might transform pow(x, 2) into x*x.

Using pow() might be clearer, and if the thing to be raised to a
power is an expression, it avoids writing the expression twice,
which makes the code shorter and avoids a source of possible error.

A further consideration is the type of the result:
pow(x,3) is a double (for all legal x), while x*x*x could
be a double or a float or a long or ...

IMHO, "best practice" is to use the exponentiation operator.
Unfortunately, C doesn't have one -- so "best practice" means
"switch to Fortran."
 
B

Bartc

pete said:
blargg said:
Bartc said:
user923005 wrote: [...]
Function macros are evil.

#define SQUARE(x) (x*x)
#define CUBE(x) (x*x*x)
...
y = SQUARE(x++); // undefined behavior
z = CUBE(++x); // ditto
Using x++ * x++ is much better defined of course.

It's clearer that it has undefined behavior than a macro invocation.
The floating point unit is not a penalty like it was in the old days.
I've just tested gcc on x86 and even with -O3 optimisation, doing
pow(A,2) requires half a dozen instructions, some of them floating
point, plus a call to pow() with who knows how much complex code inside
it.

Yep; the floating-point unit itself is quite fast these days, but
conversions between integers and floats usually goes through memory,
which
is still somewhat slow.

The other problem with all of this mishagoss,
is that if you have any trouble at all understanding (x*x)
in all of its nuances, then you can't read c code.

Yes, the idea of superscripted powers in algebra (as in x2 for x-squared)
was completely unncessary.

Come to think of it, we don't really need '*' for multiply a lot of the time
either, we can write x+x+x instead of x*3.

The point being, if x*3 is handy to be able to write instead of x+x+x, then
so is x**3 in place of x*x*x (or whatever syntax is possible in C).
 
P

Phil Carmody

Bartc said:
blargg said:
Bartc said:
Maybe a style question, though there could be efficiency issues
too .... :

I teach beginning/intermediate programming to university
students, and I've noticed that they often want to use pow() to
compute small integer powers (squares, e.g.) where I would use
explicit multiplication. Is there a "best practice" on this one?
I'm thinking that the tradeoffs are something like the following: [...]
Create a small macro or function to calculate squares or cubes of
integers.

The result will be as clear or clearer than using pow(), can
probably be optimised, and you run no risk of activating the
floating point unit.

I think that

x*x

will generally be clearer than

square(x)

Try x[i+j][k-i]*x[i+j][k-1] and see if it's still clearer than
sqr(x[i+j][k-i]), and as correct. And remember any maintenance on the term
has to be done twice.

Beware - it's a trap!
And you have to rely on the compiler to avoid evaluating the term
twice as well.

I'm fairly happy there'll be no evaluation of the multiplicands
twice in any sane compiler...

Phil
 
B

blmblm

Maybe a style question, though there could be efficiency issues
too .... :

Following up to my own post rather than to any of the replies,
because they've all been helpful, and it's hard to know which
to single out for follow-up ....
I teach beginning/intermediate programming to university
students, and I've noticed that they often want to use pow() to
compute small integer powers (squares, e.g.) where I would use
explicit multiplication.

By "small integer powers" here I meant that the exponent was
a small (non-negative!) integer. I didn't have in mind any
particular restrictions on the base (thing being raised to a
power), other than the obvious ones (some sort of integer or
floating-point).
Is there a "best practice" on this one?
I'm thinking that the tradeoffs are something like the following:

Explicit multiplication might be more efficient -- but a smart
enough compiler might transform pow(x, 2) into x*x.

Using pow() might be clearer, and if the thing to be raised to a
power is an expression, it avoids writing the expression twice,
which makes the code shorter and avoids a source of possible error.

The "error" I had in mind here was programmer error -- i.e.,
meaning to write the same expression twice but actually writing
two different expressions. Replies mentioning that the formal
parameters to pow() are doubles, which implies conversion if
the actual parameters are not -- this is a good point, and one
I hadn't thought of, and a *possible* source of a different kind
of error.

The reply (replies?) suggesting a macro or macros -- that's
an idea that occurred to me also, a few hours after writing my
original post. I rather like it, especially if the thing to be
raised to a power is an integer, but those who argue that it's
no clearer (since it could be implemented different ways) have
a point.

Those who pointed out (or implied) that one must take into
consideration possible side effects if the thing being raised
to a power is an expression -- this is a good point, especially
relevant for the macro approach, where it might not be so obvious
whether the expression would be evaluated more than once.
I've almost convinced myself here that the students are right,
but to me explicit multiplication still seems more idiomatic.
Am I completely off-base here, perhaps having developed bad habits
in an era in which compilers were less smart?

The suggestion to tell students about both (or all) approaches
and let them make their own decisions is a good one. As for
penalizing them for making a different choice from the one I'd
make -- perish the thought! To me that would seem uncomfortably
close to those unpleasant stories I sometimes hear about faculty
in other disciplines who penalize students who aren't willing to
follow some party line, which -- well, no, perhaps best to stay
away from that soapbox.
 
B

Bartc

blargg said:
Bartc said:
pete said:
blargg wrote:
Bartc wrote:
user923005 wrote:
[...]
Function macros are evil.

#define SQUARE(x) (x*x)
#define CUBE(x) (x*x*x)
...
y = SQUARE(x++); // undefined behavior
z = CUBE(++x); // ditto
Using x++ * x++ is much better defined of course.

It's clearer that it has undefined behavior than a macro invocation.
The floating point unit is not a penalty like it was in the old
days.
I've just tested gcc on x86 and even with -O3 optimisation, doing
pow(A,2) requires half a dozen instructions, some of them floating
point, plus a call to pow() with who knows how much complex code
inside
it.

Yep; the floating-point unit itself is quite fast these days, but
conversions between integers and floats usually goes through memory,
which is still somewhat slow.

The other problem with all of this mishagoss,
is that if you have any trouble at all understanding (x*x)
in all of its nuances, then you can't read c code.

Yes, the idea of superscripted powers in algebra (as in x2 for x-squared)
was completely unncessary.

Come to think of it, we don't really need '*' for multiply a lot of the
time
either, we can write x+x+x instead of x*3.

I take it this sarcasm is an admission that you don't have a technical
argument?

Yes.
 
U

user923005

I'd keep the macro, and avoid ever using x++ or ++x.

You can use:

x = x + 1;

either afterwards or before.

Of course, the macro is broken to start with.
Even when fixed, when someone else maintains your code do you imagine
that they will never misuse the macro?
If your compiler has inline capability, then you get the same effect
as the macro but also with the sequence points of a function call and
type safety.

In short, function macros are for when there is no other choice and
that is almost never.
The above macros would flunk a code review I was performing on the
spot. No need to continue until they are fixed.
 
K

Keith Thompson

user923005 said:
Of course, the macro is broken to start with.

I see your point, but I don't entirely agree.
Even when fixed, when someone else maintains your code do you imagine
that they will never misuse the macro?

If they do, that's their problem, isn't it?

If you follow the convention of giving macros names in all-caps, the
anyone using your macro who is aware of the convention should know
enough to be cautious. It's the responsibility of the author of the
macro to use enough parentheses and to use a name that makes it clear
that it's a macro; it's the responsibility of the user to avoid
arguments with side effects. (Yes, I know the standard library
doesn't follow the all-caps convention; see offsetof() and assert(),
for example.)
If your compiler has inline capability, then you get the same effect
as the macro but also with the sequence points of a function call and
type safety.

Yes, that's a very good point. Since C99 introduced inline functions,
there's much less reason to use function-like macros for this kind of
thing:

inline int square(int x) { return x * x; }

Except that (a) a function can't handle multiple types, as a macro
can, and (b) this isn't an option if you need, for whatever reason, to
stick to C90.
In short, function macros are for when there is no other choice and
that is almost never.
The above macros would flunk a code review I was performing on the
spot. No need to continue until they are fixed.

I'm not necessarily disagreeing, and I wouldn't object to a coding
standard that forbids this kind of macro. I'm just offering a
different perspective.
 
U

user923005

I see your point, but I don't entirely agree.


If they do, that's their problem, isn't it?

If you follow the convention of giving macros names in all-caps, the
anyone using your macro who is aware of the convention should know
enough to be cautious.  It's the responsibility of the author of the
macro to use enough parentheses and to use a name that makes it clear
that it's a macro; it's the responsibility of the user to avoid
arguments with side effects.  (Yes, I know the standard library
doesn't follow the all-caps convention; see offsetof() and assert(),
for example.)


Yes, that's a very good point.  Since C99 introduced inline functions,
there's much less reason to use function-like macros for this kind of
thing:

    inline int square(int x) { return x * x; }

Except that (a) a function can't handle multiple types, as a macro
can, and (b) this isn't an option if you need, for whatever reason, to
stick to C90.


I'm not necessarily disagreeing, and I wouldn't object to a coding
standard that forbids this kind of macro.  I'm just offering a
different perspective.

I guess that the difference comes from my coding.
In my job, 99% of my code is actually in C++.
It causes a C++ way of thinking (encapculation, type safety, etc.).

I understand that they are convenient. It's just that I think the
convenience is too expensive.
But I do agree that it is a matter of opinion.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top