hi,
i already posted an entry because of this problem, unfortunately i
havent solved it so far..:(
I have created a recursion for the calculation of the power like this:
[code] -
double power(double x, int n) {
-
if (n < 0)
-
return 1/power(x, -n);
-
else if (n == 0)
-
return 1.0;
-
else
-
return x * power(x, n-1);
-
}
-
-
But the problem ist that i should use this formula x^2n = x^n x^n in
any way in order to have a runtime of log(n).
I read in the previous posting something like i should use this: -
if (0 == n%2)
-
{
-
return (x^((n-1)/2))*(x^((n-1)/2))
-
}
-
else
-
{
-
return x*(x^((n-1)/2))*(x^((n-1)/2))
-
}
-
Maybe someone could help me here once more in order to reach my final
aim...? :(
matti 9 1794
In article <11************ **********@i42g 2000cwa.googleg roups.com>,
<ma****@gmx.atw rote:
>hi,
i already posted an entry because of this problem, unfortunately i havent solved it so far..:(
I have created a recursion for the calculation of the power like this:
[code] - double power(double x, int n) {
-
if (n < 0)
-
return 1/power(x, -n);
-
else if (n == 0)
-
return 1.0;
-
else
-
return x * power(x, n-1);
- }
But the problem ist that i should use this formula x^2n = x^n x^n in any way in order to have a runtime of log(n). I read in the previous posting something like i should use this: -
if (0 == n%2)
-
{
-
return (x^((n-1)/2))*(x^((n-1)/2))
-
}
-
else
-
{
-
return x*(x^((n-1)/2))*(x^((n-1)/2))
-
}
>Maybe someone could help me here once more in order to reach my final aim...? :(
You're pretty close. Try:
if (0 == n%2) { double y = power(x,n/2); return y*y; }
else return x*power(x,n-1);
You may have been confused by the shorthand use of ^ which
shouldn't appear in your code.
Steve
hi,
ah you mean like that: -
double power(double x, int n)
-
{
-
if (n < 0)
-
return 1/power(x, -n);
-
else if (n == 0)
-
return 1.0;
-
-
if (0 == n%2)
-
{
-
double y = power(x,n/2);
-
return y*y;
-
}
-
else
-
return x*power(x,n-1);
-
}
-
Have you meant it in that way...?
matti
<ma****@gmx.atw rote:
>hi,
ah you mean like that:
- double power(double x, int n)
- {
-
if (n < 0)
-
return 1/power(x, -n);
-
else if (n == 0)
-
return 1.0;
-
if (0 == n%2)
-
{
- double y = power(x,n/2);
- return y*y;
-
}
-
else
- return x*power(x,n-1);
- }
Have you meant it in that way...?
Yes, that looks okay to me, but I haven't tried to run it.
Good luck.
Steve
> matti
yes it runs.
one last question, shouldnt i modify this line:
return 1/power(x,-n);
as well, to reach the runtime of log(n)?
matti
Steve Pope wrote:
<ma****@gmx.atw rote:
hi,
ah you mean like that: -
double power(double x, int n)
-
{
-
if (n < 0)
-
return 1/power(x, -n);
-
else if (n == 0)
-
return 1.0;
-
-
if (0 == n%2)
-
{
-
double y = power(x,n/2);
-
return y*y;
-
}
-
else
-
return x*power(x,n-1);
-
}
-
Have you meant it in that way...?
Yes, that looks okay to me, but I haven't tried to run it.
Good luck.
Steve
matti
<ma****@gmx.atw rote:
>yes it runs.
>one last question, shouldnt i modify this line:
>return 1/power(x,-n);
>as well, to reach the runtime of log(n)?
No, because that line gets run exactly once (and then only
if the input is negative). It will not affect the order
of your runtime.
S.
Steve Pope wrote:
>><ma****@gmx.a twrote:
>>> - double power(double x, int n)
- {
- if (n < 0)
- return 1/power(x, -n);
- else if (n == 0)
- return 1.0;
- if (0 == n%2)
- {
- double y = power(x,n/2);
- return y*y;
- }
- else
- return x*power(x,n-1);
- }
ma****@gmx.at wrote:
>
yes it runs.
one last question, shouldnt i modify this line:
return 1/power(x,-n);
as well, to reach the runtime of log(n)?
1. Please don't top-post.
2. Remove any greetings from the posts you're replying to (they have no
informational content, so they just lengthen the post).
3. If you put an exponent of the form 2^n - 1 into your power function,
you still end up with a complexity of O(n), since the step
return x*power(x,n-1) will be called 1/2 * 2^n - 1 times.
I will give you the advice not to try to tackle this problem
recursively, as you will need to have all potences of x available (you
still can do this recursively, but the resulting code would be rather
messy). I won't spoil your fun of finding the right solution, so all I'm
saying is that the solution you have found so far is good enough.
Regards,
Stuart
Stuart Redmann <De*******@web. dewrote:
>>><ma****@gmx. atwrote: - double power(double x, int n)
- {
- if (n < 0)
- return 1/power(x, -n);
- else if (n == 0)
- return 1.0;
- if (0 == n%2)
- {
- double y = power(x,n/2);
- return y*y;
- }
- else
- return x*power(x,n-1);
- }
>3. If you put an exponent of the form 2^n - 1 into your power function, you still end up with a complexity of O(n), since the step return x*power(x,n-1) will be called 1/2 * 2^n - 1 times.
That doesn't seem right. Any pair of consecutive calls
beginning with power(n) must reduce its argument by at least a factor
of 2 since the only possibilities are:
n = 2*k (n even) which results in a call to power(k)
n = 2*k+1 (n odd) which results in a call to power(2*k), then a
call to power(k)
Therefore the runtime is bounded by 2 * log2(n). The runtime
will be equal to this bound if n, (n-1)/2, ((n-1)/2)/2 etc. are
all odd. Otherwise it will be lower than this bound.
Or am I missing something?
Steve
I wrote,
>That doesn't seem right. Any pair of consecutive calls beginning with power(n) must reduce its argument by at least a factor of 2 since the only possibilities are:
n = 2*k (n even) which results in a call to power(k)
n = 2*k+1 (n odd) which results in a call to power(2*k), then a
call to power(k)
Therefore the runtime is bounded by 2 * log2(n). The runtime will be equal to this bound if n, (n-1)/2, ((n-1)/2)/2 etc. are all odd. Otherwise it will be lower than this bound.
Oops, that should be: n, (n-1)/2, ((n-1)/2 - 1)/2 etc.
S.
Steve Pope wrote:
Stuart Redmann <De*******@web. dewrote:
>>>><ma****@gmx .atwrote:
> - >double power(double x, int n)
- >{
- >if (n < 0)
- return 1/power(x, -n);
- >else if (n == 0)
- return 1.0;
- >
- if (0 == n%2)
- {
- > double y = power(x,n/2);
- > return y*y;
- }
- else
- > return x*power(x,n-1);
- >}
- >
>>3. If you put an exponent of the form 2^n - 1 into your power function, you still end up with a complexity of O(n), since the step return x*power(x,n-1) will be called 1/2 * 2^n - 1 times.
That doesn't seem right. Any pair of consecutive calls
beginning with power(n) must reduce its argument by at least a factor
of 2 since the only possibilities are:
n = 2*k (n even) which results in a call to power(k)
n = 2*k+1 (n odd) which results in a call to power(2*k), then a
call to power(k)
Therefore the runtime is bounded by 2 * log2(n). The runtime
will be equal to this bound if n, (n-1)/2, ((n-1)/2)/2 etc. are
all odd. Otherwise it will be lower than this bound.
Or am I missing something?
Nope. Obviously I did (*shame*). I didn't read your code properly (no
comments, BTW). Of course, the computational complexity you have given
is right. Using this algorithm is certainly even the most elegant
solution since recursion is the shortest way to implement it.
Sorry for giving bad advice (at least point 3 ;)
Stuart This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
by: Paul D. Sullivan |
last post by:
I've been trying to find out how to increase the font size in the
text entry fields in Invision Power Board 1.3 for a while. The
part where you enter your post and do the quick reply and all
that has a really small font by comparision to the display font
in the forum, and I wanted to at least have the same size if
possible.
After some hours of working the issue, I tested about every
relevant entry in the Style Sheet. I found one line...
|
by: Stephane Belzile |
last post by:
Is there a way I can detect in vb.Net the power has switched to a UPS
unit in case of power failure?
Thanks
|
by: Aaron Gallimore |
last post by:
Hi,
Pretty simple one I think...Is there a "power of" or squared function in
C++. This is what i'm trying to achieve.
(array-array)*2
this doesnt work with minus numbers so i need a square or power function.
also.. Is there a "sum of" function. Ultimately i'm trying to do a euclidean
|
by: Thiva Charanasri |
last post by:
http://www.poweroflanguage.org
Track: Computer Language
1st World Congress on the Power of Language:
Theory, Practice and Performance
Date: March 6 - 10, 2006
Bangkok, Thailand
On this very auspicious occasion, Thai people will join hands with
|
by: Florent |
last post by:
Hi all,
Like you may all have seen, Power AD 1.3 had this bug at start :
"PowerAD.exe - Common Language Runtime Debug Service
ID processus=0x96c (2412), ID thread=0x218 (536).
Click OK to terminate application.
Click CANCEL to debug."
This bug is now corrected with release 1.31, on air today.
| |
by: Gus007 |
last post by:
Hi all,
Need the community great support once more. :)
I need to know how to calculate the power of some numbers in C, the problem is that the number is too big , and the compiler gives a error when doing the arithmetics.
See the power function I am using:
unsigned long int power(int base, int n)
{
|
by: greek |
last post by:
the question is to calculate x^n(x power n) (whr n can be +ve or -ve) by using recursion. the algorithm is
x= 1, n=0
1/x^n, n<0
x*x^(n-1), n>0
ive written the program it runs but im not having the correct values..here is the code:
#include<iostream.h>
#include<conio.h>
|
by: =?Utf-8?B?VGVycmVsbA==?= |
last post by:
Hi I purchased a brand new computer 2 years ago. About the last 2 months I
noticed my blue power light wasn't as bright as it use to be, in fact you can
barely see it. I also noticed my fan was making a loud noise and now I don't
hear that either. Its like it isn't getting enough power. I start the
computer up and it allows me to get to my icons but once I go into something
or leave it for 5 mins, the power automatically shuts off and...
|
by: skanemupp |
last post by:
how do i solve power(5,1.3)?
def power(nbr, po):
if po==0:
return 1
if po>0:
return nbr*power(nbr, po-1)
if po<0:
return 1/power(nbr, -1*po)
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look !
Part I. Meaning of...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed.
This is as boiled down as I can make it.
Here is my compilation command:
g++-12 -std=c++20 -Wnarrowing bit_field.cpp
Here is the code in...
| |
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth.
The Art of Business Website Design
Your website is...
|
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own....
Now, this would greatly impact the work of software developers. The idea...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms.
Adolph will...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert into image.
Globals.ThisAddIn.Application.ActiveDocument.Select();...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
| |
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
| |