446,389 Members | 1,857 Online
Need help? Post your question and get tips & solutions from a community of 446,389 IT Pros & Developers. It's quick & easy.

# recursive fuction

 P: n/a Due to my question not well understood i have briefly explained in words what i ment.i.e x0 was to mean x raised to power 0=1.NOW THE QUESTION WAS AS BELOW. Pliz i need to know this thank you. using the following recursive defination how do i write a fuction to compute this. X0=1(x raised to power 0=1) Xn= (Xn/2)2, if n>0 and n is even i.e(x raised to power n =(x raised to power n/2)power 2) Xn=X*(Xn/2)2, if n>0and n is odd i.e(x raised to power n= x MULTIPLIED BY(x raised to power n/2)power 2). Feb 20 '07 #1
8 Replies

 P: n/a In article <11**********************@j27g2000cwj.googlegroups .com>, Due to my question not well understood i have briefly explained inwords what i ment.i.e x0 was to mean x raised to power 0=1.NOW THEQUESTION WAS AS BELOW. Pliz i need to know this thank you.using the following recursive defination how do i write a fuction tocompute this. What do you have so far in the code? What particular parts of the code do you need assistance with? >X0=1(x raised to power 0=1)Xn= (Xn/2)2, if n>0 and n is even i.e(x raised to power n =(x raisedto power n/2)power 2)Xn=X*(Xn/2)2, if n>0and n is odd i.e(x raised to power n= x MULTIPLIEDBY(x raised to power n/2)power 2). You haven't defined what is to happen if n is not an integer, or if n is an integer less than 0. Also, you need to determine whether the defined formula is correct for evaluating 0 to the power 0, as there is important evidence that 0 to the power 0 is -not- 1. http://www.cs.uwaterloo.ca/~alopez-o...aq/node40.html -- "law -- it's a commodity" -- Andrew Ryan (The Globe and Mail, 2005/11/26) Feb 20 '07 #2

 P: n/a jo********@yahoo.com wrote: Due to my question not well understood i have briefly explained in words what i ment.i.e x0 was to mean x raised to power 0=1.NOW THE QUESTION WAS AS BELOW. Pliz i need to know this thank you. The answer is still: do your own goddamn homework. Richard Feb 20 '07 #3

 P: n/a jo********@yahoo.com said: Due to my question not well understood It was understood just fine, thank you. The onus is still on you to do your own homework. -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at the above domain, - www. Feb 20 '07 #4

 P: n/a 0 and n is even i.e(x raised to power n =(x raised to power n/2)power 2) Xn=X*(Xn/2)2, if n>0and n is odd i.e(x raised to power n= x MULTIPLIED BY(x raised to power n/2)power 2). I do not understand your notation at all, part of this is due to the clumsy typewriter keyboard we have to use. I would start by adopting some intuitive notation such as n^p is the same as f(n, p) where n and p are integers. Then note that f(n, 0) = 1; f(n, 1) = n. Which is missing, as far as I can tell, from what you have above. It may be that I simply don't understand what you intended. In the simple minded recursive solution - without the even odd stuff, the additional factoid is not used or needed. But the dim understanding I have of your notation can give me n/2 = 0 (your n, not mine) which is undefined as far as I can see. Feb 20 '07 #5

 P: n/a "osmium" Due to my question not well understood i have briefly explained inwords what i ment.i.e x0 was to mean x raised to power 0=1.NOW THEQUESTION WAS AS BELOW. Pliz i need to know this thank you.using the following recursive defination how do i write a fuction tocompute this.X0=1(x raised to power 0=1)Xn= (Xn/2)2, if n>0 and n is even i.e(x raised to power n =(x raisedto power n/2)power 2)Xn=X*(Xn/2)2, if n>0and n is odd i.e(x raised to power n= x MULTIPLIEDBY(x raised to power n/2)power 2). I do not understand your notation at all, Richard Heathfield decoded the notation elsethread. part of this is due to the clumsy typewriter keyboard we have to use. I would start by adopting some intuitive notation such as n^p is the same as f(n, p) where n and p are integers. Then note that f(n, 0) = 1; f(n, 1) = n. Which is missing, as far as I can tell, from what you have above. It may be that I simply don't understand what you intended. The OP wants the code the function defined by: f(x, 0) = 1 f(x, n) = f(x, n/2)**2 if n is even f(x, n) = x * f(x, n/2)**2 if n is odd using ** to mean "to the power of" and * and / to mean what they do in C. It then becomes clear what f is (x**n) and why one would want it written this way (speed). -- Ben. Feb 21 '07 #6

 P: n/a Ben Bacarisse said: The OP wants the code the function defined by: f(x, 0) = 1 f(x, n) = f(x, n/2)**2 if n is even f(x, n) = x * f(x, n/2)**2 if n is odd using ** to mean "to the power of" and * and / to mean what they do in C. It then becomes clear what f is (x**n) and why one would want it written this way (speed). Knuth demonstrates that this is not *always* the fastest way to calculate an integer power. He points out, for example, that x**15 requires six multiplications using the binary technique: a = x * x b = x * a c = x * b * b d = x * c * c but only five if you do this: a = x * x * x b = a * a c = a * b * b If I understand him correctly, he suggests reducing n to its prime factors wherever possible - e.g. for n=63 you would do this: a = x * x * x b = a * a * a c = b * b * b d = b * c * c for eight multiplications, compared to: a = x * x * x b = x * a * a c = x * b * b d = x * c * c e = x * d * d for ten, using the binary method. Having said that, for best results I suggest the OP consult TAOCP2, section 4.6.3 rather than rely on my lossily compressed summary. -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at the above domain, - www. Feb 21 '07 #7

 P: n/a Richard Heathfield >The OP wants to code the function defined by:f(x, 0) = 1f(x, n) = f(x, n/2)**2 if n is evenf(x, n) = x * f(x, n/2)**2 if n is oddusing ** to mean "to the power of" and * and / to mean what they do inC. It then becomes clear what f is (x**n) and why one would want itwritten this way (speed). Knuth demonstrates that this is not *always* the fastest way to calculate an integer power. He points out, for example, that x**15 requires six multiplications using the binary technique: a = x * x b = x * a c = x * b * b d = x * c * c but only five if you do this: a = x * x * x b = a * a c = a * b * b and that for n=33 the factor method takes more multiplications than the binary one.[1] If I understand him correctly, he suggests reducing n to its prime factors wherever possible - e.g. for n=63 you would do this: I suspect that in all practical situations (cryptography is the one that I am familiar with) factorising the power is either impractical or unproductive. In typical Knuth style, one does not end up with a practical suggestion but one is much better informed! [1] Following an unsubtle hint before Christmas, I now have a copy of TAOCP1-3! -- Ben. Feb 21 '07 #8

 P: n/a Ben Bacarisse said: Richard Heathfield >Knuth demonstrates that this is not *always* the fastest way tocalculate an integer power. He points out, for example, that x**15requires six multiplications using the binary technique:a = x * xb = x * ac = x * b * bd = x * c * cbut only five if you do this:a = x * x * xb = a * ac = a * b * b and that for n=33 the factor method takes more multiplications than the binary one. Right. Observing that 33 = 2**k + 1, whereas 15 = 2**k - 1 (where, in each case, k is some integer), I find myself wondering whether the binary technique's efficiency is respectively maximal and minimal in those cases. [1] > >If I understand him correctly, he suggests reducing n to its primefactors wherever possible - e.g. for n=63 you would do this: I suspect that in all practical situations (cryptography is the one that I am familiar with) factorising the power is either impractical or unproductive. In typical Knuth style, one does not end up with a practical suggestion but one is much better informed! Well, you might know the power in advance, in which case you can pre-calculate its factors. Or you might even choose its factors in advance! For example, if you're doing Diffie-Hellman, you need to raise a public value by a secret value. You might reasonably choose a secret value of a * b * c * d * e * f * g * h + i, so that Step 1 of the D-H looks like this: k1 = p1 ** (a * b * c * d * e * f * g * h + i) % p2 which would obviously make it very simple to use the factoring method Knuth is recommending. In typical Knuth style, one ends up with a practical suggestion if only one is prepared to think a little. :-) -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at the above domain, - www. Feb 21 '07 #9

### This discussion thread is closed

Replies have been disabled for this discussion.