computing powers without the pow() function.
Author 
Message 
kenji2.. #1 / 38

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 


davidbrad.. #2 / 38

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 


Francis Glassboro #3 / 38

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 is significant in the answer. 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 


Douglas A. Gwy #4 / 38

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


Herman Rub #5 / 38

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 IN479071399


Thu, 10 Jul 2003 13:33:43 GMT 


Peter Seeba #6 / 38

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, Procommerce radical, Spam fighter. Boycott Spamazon! Consulting & Computers: http://www.plethora.net/ 

Thu, 10 Jul 2003 13:34:01 GMT 


Douglas A. Gwy #7 / 38

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 


Gene Wirchen #8 / 38

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 


Robert J. Hanse #9 / 38

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 better advice in here than "read a good math reference". 

Fri, 11 Jul 2003 01:30:14 GMT 


CBFalcone #10 / 38

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 (Remove "NOSPAM." from reply address. mydeja works unmodified)


Fri, 11 Jul 2003 12:27:49 GMT 


Francis Glassboro #11 / 38

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 


Zeljko Vr #12 / 38

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 


Christian B #13 / 38

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 


Mike Dowli #14 / 38

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 


Herman Rub #15 / 38

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 IN479071399


Sun, 13 Jul 2003 08:01:58 GMT 


Page 1 of 3

[ 38 post ] 

Go to page:
[1]
[2] [3] 
