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). 8 2196
In article <11**********************@j27g2000cwj.googlegroups .com>,
<jo********@yahoo.comwrote:
>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...aq/node40.html
--
"law -- it's a commodity"
-- Andrew Ryan (The Globe and Mail, 2005/11/26) 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 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.
<jo********@yahoo.comwrote:
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.
"osmium" <r1********@comcast.netwrites:
<jo********@yahoo.comwrote:
>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,
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.
Ben Bacarisse said:
<snip>
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.
Richard Heathfield <rj*@see.sig.invalidwrites:
Ben Bacarisse said:
<snip>
>The OP wants to 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
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!
--
Ben.
Ben Bacarisse said:
Richard Heathfield <rj*@see.sig.invalidwrites:
<snip>
>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.
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 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!
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. This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: |
last post by:
OK:
Purpose: Using user's input and 3 recursive functions, construct an hour
glass figure. Main can only have user input, loops and function calls.
Recursive function 1 takes input and displays...
|
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
{
|
by: Szaki |
last post by:
I use a BulkLoad to import file.xml to my base MS Server 2000.
To import this xml file I need schema file. Mayby you know how to do this
file mechanicy f.g. mayby somebody have some script in .net...
|
by: Victor |
last post by:
Hello,
I've got a situation in which the number of (valid) recursive calls I
make will cause stack overflow. I can use getrlimit (and setrlimit)
to test (and set) my current stack size. ...
|
by: mike |
last post by:
i've already used static fuction to make website
i wanna common module that's why i used static fuctions.
may be it's more than 100 fuction ...is it ok?
|
by: seberino |
last post by:
I'm a compiler newbie and curious if Python grammar is able to
be parsed by a recursive descent parser or if it requires
a more powerful algorithm.
Chris
|
by: joel_maina |
last post by:
using the following recursive defination how do i write a fuction to
compute this.
X0=1
Xn= (Xn/2)2, if n>0 and n is even.
Xn=X*(Xn/2)2, if n>0and n is odd
|
by: champ1979 |
last post by:
I wrote an algorithm to get all the relatives of a person in a family tree. I'm basically getting all the users from the DB and am doing the recursive logic in code, so that there is only 1 call...
|
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...
|
by: taylorcarr |
last post by:
A Canon printer is a smart device known for being advanced, efficient, and reliable. It is designed for home, office, and hybrid workspace use and can also be used for a variety of purposes. However,...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: ryjfgjl |
last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
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,...
|
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...
| |