Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > small integer powers -- use pow() or explicit multiplication?

Reply
Thread Tools

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

 
 
blmblm@myrealbox.com
Guest
Posts: n/a
 
      03-17-2009
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?

--
B. L. Massingill
ObDisclaimer: I don't speak for my employers; they return the favor.
 
Reply With Quote
 
 
 
 
Rich Webb
Guest
Posts: n/a
 
      03-17-2009
On 17 Mar 2009 15:34:23 GMT, http://www.velocityreviews.com/forums/(E-Mail Removed) <(E-Mail Removed)>
wrote:

>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.

--
Rich Webb Norfolk, VA
 
Reply With Quote
 
 
 
 
user923005
Guest
Posts: n/a
 
      03-17-2009
On Mar 17, 8:34*am, (E-Mail Removed) <(E-Mail Removed)> wrote:
> 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
 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      03-17-2009
(E-Mail Removed) <(E-Mail Removed)> writes:
> 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.

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
 
Reply With Quote
 
Bartc
Guest
Posts: n/a
 
      03-17-2009

<(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> 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.

--
Bartc

 
Reply With Quote
 
user923005
Guest
Posts: n/a
 
      03-18-2009
On Mar 17, 3:29*pm, "Bartc" <(E-Mail Removed)> wrote:
> <(E-Mail Removed)> wrote in message
>
> news:(E-Mail Removed)...
>
>
>
>
>
> > 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.


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.
 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      03-18-2009
user923005 <(E-Mail Removed)> writes:
> On Mar 17, 3:29*pm, "Bartc" <(E-Mail Removed)> wrote:
>> <(E-Mail Removed)> wrote in message

[...]
>> 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)


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.

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
 
Reply With Quote
 
Nate Eldredge
Guest
Posts: n/a
 
      03-18-2009
Keith Thompson <(E-Mail Removed)> writes:

> user923005 <(E-Mail Removed)> writes:
>
>> 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.


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.
 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      03-18-2009
Nate Eldredge <(E-Mail Removed)> writes:
> Keith Thompson <(E-Mail Removed)> writes:
>> user923005 <(E-Mail Removed)> writes:
>>> 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.

>
> 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.

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


--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
 
Reply With Quote
 
Bartc
Guest
Posts: n/a
 
      03-18-2009
user923005 wrote:
> On Mar 17, 3:29 pm, "Bartc" <(E-Mail Removed)> wrote:
>> <(E-Mail Removed)> wrote in message
>> news:(E-Mail Removed)...


>>> 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.

>
> 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.

--
bartc

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Diff bw Small integer and Capitol integer vijjirams@gmail.com ASP .Net 0 09-17-2008 02:41 PM
Explicit instantiation of STL vector demands explicit instantiation of all the templates it using internally. krunalbauskar@gmail.com C++ 1 12-25-2006 03:51 PM
Two's complement integer divided by Powers of 2 question Janice C Programming 3 07-09-2005 06:05 AM
What's the difference betwwen explicit instantiaion and explicit specialization? Andy C++ 5 01-30-2005 11:46 PM
Is explicit template qualification required for explicit delete? J.T. Conklin C++ 1 08-11-2004 02:06 AM



Advertisments