computing powers without the pow() function.
Author Message
computing powers without the pow() function.

How would I calculate positive powers of a type double identifier
without using the pow() function. I am also to minimize the number of
multiplications in this "challenge".

Kenji
--

Wed, 09 Jul 2003 02:01:36 GMT
computing powers without the pow() function.

Quote:

> How would I calculate positive powers of a type double identifier
> without using the pow() function. I am also to minimize the number of
> multiplications in this "challenge".

Sounds a lot like homework.

Think about how mulitplication works. What is common in the expression
N x N x N x N
--

Thu, 10 Jul 2003 13:21:06 GMT
computing powers without the pow() function.

writes

Quote:
>How would I calculate positive powers of a type double identifier
>without using the pow() function. I am also to minimize the number of
>multiplications in this "challenge".

You mean homework? Well I think Knuth discusses it in 'The Art of
Computer programming).  The only hint that I am willing to give until
you actually cut some code is that in x^n the binary representation of n

Francis Glassborow      Association of C & C++ Users
64 Southfield Rd
Oxford OX4 1PA          +44(0)1865 246490
All opinions are mine and do not represent those of any organisation
--

Thu, 10 Jul 2003 13:22:26 GMT
computing powers without the pow() function.

Quote:

> How would I calculate positive powers of a type double identifier
> without using the pow() function. I am also to minimize the number of
> multiplications in this "challenge".

That cannot be stated correctly, since identifiers do
not have powers.  Presumably you mean, powers of a
floating-point value of type double.

Strict minimization of the number of multiplications
is not a realistic goal; it is possible to use *no*
multiply operators in the generated code, but that
is not the best way to implement pow().  There is no
*practical* reason not to use pow() in the general
case; if you want to rewrite pow(), the usual method
of exponentiated multiplied logarithm doesn't use
many multiplications.  If you separate the exponent
and significand parts of the floating-point values,
you can reduce the problem to integer operations,
although it gets somewhat messy.

It is possible that you misstated the problem in
another way, and it is really supposed to be about
computing *integer* powers.  In that case, just
think about the binary representation of an integer
and a solution should occur to you.
--

Thu, 10 Jul 2003 13:22:37 GMT
computing powers without the pow() function.

Quote:

>How would I calculate positive powers of a type double identifier
>without using the pow() function. I am also to minimize the number of
>multiplications in this "challenge".

I am assuming you mean integer powers.

fortran does this, and I believe that C++ might allow the
redefinition of pow(d,i) to be defined this way.  Optimizing
Fortran compilers did quite a few of the powers hand
optimized "small" powers (I recall up to 50 for one); this
can only be done AFAIK by having an operator rather than a
function, so the arguments can be used at compile time.

The minimal number of multiplications is not easy to get.
For example, for 15, the optimum is 2, 4, 5, 10, 15 or
2, 3, 6, 12, 15, as against the easily programmed
2, 3, 4, 7, 8, 15.  This latter one computes the 2^k
power as far as is necessary, and multiplies the ones
for which the coefficient in the binary expansion are 1.
--
This address is for information only.  I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399

--

Thu, 10 Jul 2003 13:33:43 GMT
computing powers without the pow() function.

Quote:

>How would I calculate positive powers of a type double identifier
>without using the pow() function. I am also to minimize the number of
>multiplications in this "challenge".

This one does no multiplications.  It does p divisions, but that shouldn't
count.

double mypow(double d, int p) {
int i;
double a;
double mod;
double oldd = d;

if (p == 0)
return 1;

if (fmod(d, 1.0)) {
mod = 1 / fmod(d, 1.0);
} else {
mod = -1;
}
for (i = 1; i < p; ++i) {
int n;

a = 0;
for (n = 0; n < oldd; ++n) {
a += d;
}
if (mod != -1)
a += d / mod - d;

d = a;
}
return d;

Quote:
}

--

C/Unix wizard, Pro-commerce radical, Spam fighter.  Boycott Spamazon!
Consulting & Computers: http://www.plethora.net/
--

Thu, 10 Jul 2003 13:34:01 GMT
computing powers without the pow() function.

Quote:

> Fortran compilers did quite a few of the powers hand
> optimized "small" powers (I recall up to 50 for one); this
> can only be done AFAIK by having an operator rather than a
> function, so the arguments can be used at compile time.

The difference between X**Y and pow(X,Y) is
merely a matter of notation, if the compiler
can understand the semantics in both cases.
The standard C library functions can be
treated specially by the compiler, and some
of them are obvious candidates for such
treatment.
--

Fri, 11 Jul 2003 01:29:40 GMT
computing powers without the pow() function.

Quote:

>How would I calculate positive powers of a type double identifier
>without using the pow() function. I am also to minimize the number of
>multiplications in this "challenge".

Instead of using the multiply operator, write a function to do
multiplication by repeated addition.  You'll end up with zero
multiplications.  That's minimum!

Glad to be of help to the other readers of this group wanting a
laugh.

Sincerely,

Gene Wirchenko

Computerese Irregular Verb Conjugation:
I have preferences.
You have biases.
He/She has prejudices.
--

Fri, 11 Jul 2003 01:29:49 GMT
computing powers without the pow() function.

Quote:
> How would I calculate positive powers of a type double identifier
> without using the pow() function. I am also to minimize the number of
> multiplications in this "challenge".

RTFM.  In this case, the "manual" is a good college calculus textbook or
Knuth's _The Art of Computer Programming_.  Mathematicians spent centuries
devising fast, elegant exponentiation algorithms.  You're unlikely to find
--

Fri, 11 Jul 2003 01:30:14 GMT
computing powers without the pow() function.

Quote:

> >How would I calculate positive powers of a type double identifier
> >without using the pow() function. I am also to minimize the number of
> >multiplications in this "challenge".

> I am assuming you mean integer powers.

> Fortran does this, and I believe that C++ might allow the
> redefinition of pow(d,i) to be defined this way.  Optimizing
> Fortran compilers did quite a few of the powers hand
> optimized "small" powers (I recall up to 50 for one); this
> can only be done AFAIK by having an operator rather than a
> function, so the arguments can be used at compile time.

> The minimal number of multiplications is not easy to get.
> For example, for 15, the optimum is 2, 4, 5, 10, 15 or
> 2, 3, 6, 12, 15, as against the easily programmed
> 2, 3, 4, 7, 8, 15.  This latter one computes the 2^k
> power as far as is necessary, and multiplies the ones
> for which the coefficient in the binary expansion are 1.

What about 2, 3, 5, 15?  Think of the prime factors.

--

http://www.qwikpages.com/backstreets/cbfalconer

--

Fri, 11 Jul 2003 12:27:49 GMT
computing powers without the pow() function.

Quote:
>     Instead of using the multiply operator, write a function to do
>multiplication by repeated addition.  You'll end up with zero
>multiplications.  That's minimum!

Well if we count a division as a negative multiplication, we would have
no lower bound :)

Francis Glassborow      Association of C & C++ Users
64 Southfield Rd
Oxford OX4 1PA          +44(0)1865 246490
All opinions are mine and do not represent those of any organisation
--

Fri, 11 Jul 2003 12:28:32 GMT
computing powers without the pow() function.

Quote:
> How would I calculate positive powers of a type double identifier
> without using the pow() function. I am also to minimize the number of
> multiplications in this "challenge".

a^b = exp(b*log(a)) .. can you beat 1 multiplication? :)
--

Sat, 12 Jul 2003 02:38:29 GMT
computing powers without the pow() function.

Quote:

> >     Instead of using the multiply operator, write a function to do
> >multiplication by repeated addition.  You'll end up with zero
> >multiplications.  That's minimum!

> Well if we count a division as a negative multiplication, we would have
> no lower bound :)

If you count division as division and no multiplication, you can always do
it with one multiplication:

Calculate x^n:
if x = 0 the result is x.
Otherwise, let y = 1/x.
Start with z = 1, and replace z with z/y n times.
The result is z.
--

Sat, 12 Jul 2003 02:38:57 GMT
computing powers without the pow() function.

Quote:

>How would I calculate positive powers of a type double identifier
>without using the pow() function. I am also to minimize the number of
>multiplications in this "challenge".

Well, that's simple.  You can get away with just a single
multiplication.

#include <math.h>

double power( double x, double y) {
return( exp( y*log( x ) );

Quote:
}

Somehow, I doubt that that is what you indended to ask, but it answers
the question that you did ask.

Note that these functions require much more time to compute than several
double precision multiplications, but this little function will also
compute real numbers raised to the power of real numbers.  Moreover, if
y is an integer, this will still be the most efficient method of y is
sufficiently large.

Cheers,
Mike

--

address.  It is a mail alias.  Once spammed, the alias is deleted, and
the integer 'N' incremented.  Currently, mike[42,43] are valid.  If
email to mikeN bounces, try mikeN+1.
--

Sat, 12 Jul 2003 02:40:34 GMT
computing powers without the pow() function.

Quote:

>> Fortran compilers did quite a few of the powers hand
>> optimized "small" powers (I recall up to 50 for one); this
>> can only be done AFAIK by having an operator rather than a
>> function, so the arguments can be used at compile time.
>The difference between X**Y and pow(X,Y) is
>merely a matter of notation, if the compiler
>can understand the semantics in both cases.
>The standard C library functions can be
>treated specially by the compiler, and some
>of them are obvious candidates for such
>treatment.

It is more than a matter of notation.  Even if the power
function is redefined for the second argument an integer so
that logarithm and exponential is never used, a compiler
normally can and does look for special values for arguments
of operators at ccmpile time, while I do not know of this
being done for arguments of functions.

Some Fortran compilers even looked for ".5" in the exponent
so they could use the faster square root instead of
logarithm and exponential.
--
This address is for information only.  I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399

--

Sun, 13 Jul 2003 08:01:58 GMT

 Page 1 of 3 [ 38 post ] Go to page: [1] [2] [3]

Relevant Pages