473,836 Members | 1,277 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Recursive Functions

I am trying to write a recursive version of Power(x,n) that works by
breaking n down into halves(where half of n=n/2), squaring
Power(x,n/2), and multiplying by x again if n was odd, and to find a
suitable base case to stop the recursion. Can someone give me an
example of this?

Thanks!
Nov 13 '05
64 7335
Marcus Lessard wrote:

Maybe it's just me but doesn't the contrived nature of the function scream
out "Homework Assignment?" Maybe I'm missing something but I just can't see
why you'd ever want to compute this value..


<off-topic>

If computing positive integer powers is of so little
interest, it's hard to see why Knuth gives the topic an
entire section of its own in "The Art of Computer Programming,
Volume II: Seminumerical Algorithms."

The method outlined is the first serious power-computing
algorithm Knuth introduces in that section. He writes that
some authors have declared the method optimal, but he is
kind enough to spare them embarrassment by omitting their
names; clearly they forgot to consider cases like n==15.

</off-topic>

--
Er*********@sun .com
Nov 13 '05 #21

"James Hu" <jx*@despammed. com> wrote in message
news:Nv******** ************@co mcast.com...
On 2003-10-28, Glen Herrmannsfeldt <ga*@ugcs.calte ch.edu> wrote:
"James Hu" <jx*@despammed. com> wrote in message
news:x9******** ************@co mcast.com...
On 2003-10-27, dmattis <dm*****@yahoo. com> wrote:
> I am trying to write a recursive version of Power(x,n) that works by
> breaking n down into halves(where half of n=n/2), squaring
> Power(x,n/2), and multiplying by x again if n was odd, and to find a
> suitable base case to stop the recursion. Can someone give me an
> example of this?

This is not a C question... but the C answer is use pow() (unless you
are purposefully avoiding floating point, in which case a table lookup
is in order).


The algorithm described, in non-recursive form, is commonly used in
languages that supply an integer exponentiation operator.


Yes, but those typically take a floating point type for the x argument,
and an int type for the n argument.


The languages I know of supply routines for integer n, and integer, float,
double, complex, and complex double x.

The OP didn't supply the type of x, but the algorithm works for any type
where mulitply is defined.
A table dimensioned INT_MAX-INT_MIN+1 will take up a lot of memory.


That is an imaginative approach, but not what I had in mind.

#include <stdint.h>

static int8_t hbit[256] =
{-1
,0
,1,1
,2,2,2,2
,3,3,3,3,3,3,3, 3
,4,4,4,4,4,4,4, 4,4,4,4,4,4,4,4 ,4
,5,5,5,5,5,5,5, 5,5,5,5,5,5,5,5 ,5,5,5,5,5,5,5, 5,5,5,5,5,5,5,5 ,5,5
,6,6,6,6,6,6,6, 6,6,6,6,6,6,6,6 ,6,6,6,6,6,6,6, 6,6,6,6,6,6,6,6 ,6,6
,6,6,6,6,6,6,6, 6,6,6,6,6,6,6,6 ,6,6,6,6,6,6,6, 6,6,6,6,6,6,6,6 ,6,6
,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7 ,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7 ,7,7
,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7 ,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7 ,7,7
,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7 ,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7 ,7,7
,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7 ,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7 ,7,7
};

int int_pow(int x, uint8_t n)
{
int t = 1;
if (n == 0) return 1;
if (x == 0) return 0;
switch (hbit[n]) {
case 7: if (n & 1) t *= x; n >>= 1; x *= x;
case 6: if (n & 1) t *= x; n >>= 1; x *= x;
case 5: if (n & 1) t *= x; n >>= 1; x *= x;
case 4: if (n & 1) t *= x; n >>= 1; x *= x;
case 3: if (n & 1) t *= x; n >>= 1; x *= x;
case 2: if (n & 1) t *= x; n >>= 1; x *= x;
case 1: if (n & 1) t *= x; n >>= 1; x *= x;
default: if (n & 1) t *= x;
}
return t;
}


The algorithm also works for n > 255.

-- glen
Nov 13 '05 #22

"Marcus Lessard" <sp****@spam.co m> wrote in message
news:bn******** **@pyrite.mv.ne t...
Maybe it's just me but doesn't the contrived nature of the function scream
out "Homework Assignment?" Maybe I'm missing something but I just can't see why you'd ever want to compute this value..


Computing integer powers of numbers is fairly common in scientific
programming, and is one of the relatively few things missing from C used in
scientific programming.

However, requiring it as a recursive function does scream of homework. A
simple for loop should be easier and faster.

-- glen
Nov 13 '05 #23

On Tue, 28 Oct 2003, Eric Sosman wrote:

<off-topic>
If computing positive integer powers is of so little
interest, it's hard to see why Knuth gives the topic an
entire section of its own in "The Art of Computer Programming,
Volume II: Seminumerical Algorithms."

The method outlined is the first serious power-computing
algorithm Knuth introduces in that section. He writes that
some authors have declared the method optimal, but he is
kind enough to spare them embarrassment by omitting their
names; clearly they forgot to consider cases like n==15.


What's wrong with n==15? The algorithm given is still O(lg N)
in such cases. No, probably Knuth was thinking of *better*
algorithms that could compute powers more quickly -- I don't
know of any, but perhaps a couple of exp() and log() lookup
tables, plus iteration, could do things faster than straight
recursion.

-Arthur

Nov 13 '05 #24
On 2003-10-28, Glen Herrmannsfeldt <ga*@ugcs.calte ch.edu> wrote:

"James Hu" <jx*@despammed. com> wrote in message
news:Nv******** ************@co mcast.com...
On 2003-10-28, Glen Herrmannsfeldt <ga*@ugcs.calte ch.edu> wrote:
> "James Hu" <jx*@despammed. com> wrote in message
> news:x9******** ************@co mcast.com...
>> On 2003-10-27, dmattis <dm*****@yahoo. com> wrote:
>> > I am trying to write a recursive version of Power(x,n) that works by
>> > breaking n down into halves(where half of n=n/2), squaring
>> > Power(x,n/2), and multiplying by x again if n was odd, and to find a
>> > suitable base case to stop the recursion. Can someone give me an
>> > example of this?
>>
>> This is not a C question... but the C answer is use pow() (unless you
>> are purposefully avoiding floating point, in which case a table lookup
>> is in order).
>
> The algorithm described, in non-recursive form, is commonly used in
> languages that supply an integer exponentiation operator.
Yes, but those typically take a floating point type for the x argument,
and an int type for the n argument.


The languages I know of supply routines for integer n, and integer, float,
double, complex, and complex double x.


Well, lets just call most of those floating point, except for integer
and complex x (which I assume you mean A+Bi with A and B integers, but
C has no such type).
The OP didn't supply the type of x, but the algorithm works for any type
where mulitply is defined.
Since the proposed algorithm does not deal with negative powers, it
is safe to assume the the type of n is unsigned.
> A table dimensioned INT_MAX-INT_MIN+1 will take up a lot of memory.


That is an imaginative approach, but not what I had in mind.

[.. snip .. ]
The algorithm also works for n > 255.


But not without overflowing the int type. My function does not
prevent overflow from happening, but the caller can check to
make sure overflow will not before invoking the function. And
the caller can then discover the degenerate unity cases and
dispatch it without incurring the function call overhead.

However, here is an alternate implementation (now, with two
table lookups):

#include <stdint.h>
#include <limits.h>

static int32_t xpow[32] =
{0,INT_MAX,4634 1,1291,216,74,3 6,22,15,11,9,8, 6,6,5,5,4,4,4,4 ,3,3
,3,3,3,3,3,3,3, 3,3,2
};

static int8_t hbit[32] =
{-1
,0
,1,1
,2,2,2,2
,3,3,3,3,3,3,3, 3
,4,4,4,4,4,4,4, 4,4,4,4,4,4,4,4 ,4
};

int32_t int_pow(int32_t x, unsigned n)
{
int32_t t = 1;
int32_t ax;
if (n == 0) return 1;
if (x == 0) return 0;
if (n == 1) return x;
if (x == INT_MIN) return 0;
if (((x<0)?-x:x) >= xpow[(n<32)?n:31])
return (x<0)?((n&1)?IN T_MIN:INT_MAX): INT_MAX;
if (x == 1 || x == -1) n &= 1;
switch (hbit[n]) {
case 4: if (n & 1) t *= x; n >>= 1; x *= x;
case 3: if (n & 1) t *= x; n >>= 1; x *= x;
case 2: if (n & 1) t *= x; n >>= 1; x *= x;
case 1: if (n & 1) t *= x; n >>= 1; x *= x;
default: t *= x;
}
return t;
}
-- James
Nov 13 '05 #25
"Arthur J. O'Dwyer" wrote:

On Tue, 28 Oct 2003, Eric Sosman wrote:

<off-topic>
If computing positive integer powers is of so little
interest, it's hard to see why Knuth gives the topic an
entire section of its own in "The Art of Computer Programming,
Volume II: Seminumerical Algorithms."

The method outlined is the first serious power-computing
algorithm Knuth introduces in that section. He writes that
some authors have declared the method optimal, but he is
kind enough to spare them embarrassment by omitting their
names; clearly they forgot to consider cases like n==15.


What's wrong with n==15? The algorithm given is still O(lg N)
in such cases. No, probably Knuth was thinking of *better*
algorithms that could compute powers more quickly -- I don't
know of any, but perhaps a couple of exp() and log() lookup
tables, plus iteration, could do things faster than straight
recursion.


The binary method starts with x and then computes x^2,
x^3, x^6, x^7, x^14, x^15 -- six multiplications .

The factor method starts with x and then computes x^2
and x^3 with two multiplications . Letting y = x^3 it then
computes y^2, y^4, y^5 (= x^15) in three more multiplications ,
for five in all.

Perhaps not a big deal when `x' is something simple like
a floating-point number -- but worth paying heed to if `x'
is, say, a large matrix.

--
Er*********@sun .com
Nov 13 '05 #26
On 2003-10-28, James Hu <jx*@despammed. com> wrote:
[ ... ]
{0,INT_MAX,4634 1,1291,216,74,3 6,22,15,11,9,8, 6,6,5,5,4,4,4,4 ,3,3 [ ... ] if (x == INT_MIN) return 0; [ ... ] return (x<0)?((n&1)?IN T_MIN:INT_MAX): INT_MAX;

[ ... ]

References to INT_MAX and INT_MIN should be changed to INT32_MAX
and INT32_MIN respectively.

-- James
Nov 13 '05 #27
gc
My take

double Power(double x, unsigned int n) {
if(n==0) return 1.;
else return (n&1) ? x*Power(x*x,(n-1)/2) : Power(x*x,n/2);
}
Nov 13 '05 #28
Glen Herrmannsfeldt wrote:

"Marcus Lessard" <sp****@spam.co m> wrote in message
news:bn******** **@pyrite.mv.ne t...
Maybe it's just me but doesn't the contrived nature of the function
scream
out "Homework Assignment?" Maybe I'm missing something but I just can't

see
why you'd ever want to compute this value..


Computing integer powers of numbers is fairly common in scientific
programming, and is one of the relatively few things missing from C used
in scientific programming.

However, requiring it as a recursive function does scream of homework. A
simple for loop should be easier and faster.


Hmmm. I raised 7 to the power 7777 using recursion and iteration. (Since the
result occupies over 6500 decimal digits, I won't display it here!)

The recursive calculation took 0.22 seconds, and the iterative version 1.06
seconds - almost five times slower. Perhaps you could demonstrate an
iterative version that can hold a candle to the recursive technique?

--
Richard Heathfield : bi****@eton.pow ernet.co.uk
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton
Nov 13 '05 #29
In article
<Pi************ *************** ********@unix48 .andrew.cmu.edu >,
"Arthur J. O'Dwyer" <aj*@nospam.and rew.cmu.edu> wrote:
What's wrong with n==15? The algorithm given is still O(lg N)
in such cases. No, probably Knuth was thinking of *better*
algorithms that could compute powers more quickly -- I don't
know of any, but perhaps a couple of exp() and log() lookup
tables, plus iteration, could do things faster than straight
recursion.


Knuth was thinking of the fact that this algorithm uses six
multiplications to calculate x^15, but it can be done using five
multiplications .
Nov 13 '05 #30

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

4
1924
by: Magnus Lie Hetland | last post by:
Hi! I've been looking at ways of dealing with nested structures in regexps (becuase I figured that would be faster than the Python parsing code I've currently got) and came across a few interesting things... First there is this, mentioning the (?<DEPTH>) and (?<-DEPTH>) constructs of the .NET regexp matcher: http://www.rassoc.com/gregr/weblog/archive.aspx?post=590
7
567
by: Jon Slaughter | last post by:
#pragma once #include <vector> class empty_class { }; template <int _I, int _J, class _element, class _property> class RDES_T {
7
6134
by: Aloo | last post by:
Dear friends, If we declare a recursive function as 'inline' then does it actually convert to an iterative form during compilation ( the executable code is iterative)? Is it possible ? Please reply.
9
16850
by: Csaba Gabor | last post by:
Inside a function, I'd like to know the call stack. By this I mean that I'd like to know the function that called this one, that one's caller and so on. So I thought to do: <script type='text/javascript'> function myFunc(lev) { // if (lev) return myFunc(lev-1); var aStack=; nextFunc = arguments.callee;
41
3396
by: Harry | last post by:
Hi all, 1)I need your help to solve a problem. I have a function whose prototype is int reclen(char *) This function has to find the length of the string passed to it.But the conditions are that no local variable or global variable should be used.I have to use recursive functions.
5
4951
by: Digital Puer | last post by:
I got this on an interview: Is it possible to write inline recursive functions? I said yes, but there is no guarantee that the compiler will definitely inline your code even if you write "inline". Is this a right answer? It seems to be independent of whether or not the function is recursive. Another question: how can you tell if the compiler has inlined your
10
2574
by: AsheeG87 | last post by:
Hello Everyone! I have a linked list and am trying to include a recursive search. However, I am having trouble understanding how I would go about that. I don't quite understand a recursive search....would any of you be so kind to explain it to me...maybe include some examples. I would GREATLY appreciate it!!!
9
2643
by: pereges | last post by:
Hello I need some ideas for designing a recursive function for my ray tracing program. The idea behind ray tracing is to follow the electromagnetic rays from the source, as they hit the object.The object is triangulated. The rays can undergo multiple reflections, diffractions etc of the same object i.e. a ray hits a surface of the object, undergoes reflection resulting in a reflected ray which can again hit a surface, corner or edge...
3
4249
by: from.future.import | last post by:
Hi, I encountered garbage collection behaviour that I didn't expect when using a recursive function inside another function: the definition of the inner function seems to contain a circular reference, which means it is only collected by the mark-and-sweep collector, not by reference counting. Here is some code that demonstrates it: === def outer():
6
9619
KevinADC
by: KevinADC | last post by:
This snippet of code provides several examples of programming techniques that can be applied to most programs. using hashes to create unique results static variable recursive function serialization The code itself generates a list of strings comprised of random numbers. No number will be repeated within a string, and no string will be repeated within the list of strings. Following the code is a brief discussion of how the above...
0
9814
marktang
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...
0
10836
Oralloy
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...
1
10585
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,...
0
10249
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
1
7786
isladogs
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...
0
6976
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();...
0
5645
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
2
4009
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
3
3108
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.