recursive fuction

[joel_maina]

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).

 

[Walter Roberson]

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.

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 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).

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/math-faq/node40.html

 

[Richard Bos]

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

 

[Richard Heathfield]

(e-mail address removed) 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.

 

[osmium]

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).

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.

 

[Ben Bacarisse]

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).

 

[Richard Heathfield]

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.

 

[Ben Bacarisse]

Ben Bacarisse said:



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:

<snip>

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!

 

[Richard Heathfield]

Ben Bacarisse said:

Richard Heathfield <[email protected]> writes:

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]

<snip>

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.