Re: Powers of 5
- From: Rick Decker <rdecker@xxxxxxxxxxxx>
- Date: Mon, 04 Sep 2006 20:13:43 -0400
Josh wrote:
Hi, I'm an undergrad studying computer science. I discovered, whilePowers of 5 of the form 2^k (i.e. 5^(2^k)) can be computed quickly
studying for a computer science final, that I still haven't come up
with an answer to a question that was offered as extra credit on our
first quiz in the course. We were given the following Pascal code.
function power(n: integer): integer;
begin
if n <= 1 then
return (5)
else
return (5 * power(n-1))
end; {power}
We were then asked: "Can you modify the function in such a way that for
arguments of the form 2^k it computes the result with just k+1 calls?"
I'm not especially adept with math, and I have no idea how to approach
the question. Please point me in the right direction; I would really
like to understand this.
by successive squaring. For example,
5^16 = (5^8)^2
5^8 = (5^4)^2
5^4 = (5^2)^2
5^2 = (5^1)^2
This should give you the modified algorithm almost immediately.
If not, since you indicated this isn't homework just ask for
clarification.
Regards,
Rick
BTW, the argument doesn't have to be a power of 2 for a modification
to work in time less than a multiple of log n. It's a well-known
way of speeding up exponentiation.
Also, I'm sort of curious what school is still using Pascal as an
introductory language. Not that I'm complaining--I think Pascal
could still be a righteous choice for an intro vehicle; I'd just
like to know what school still has the stones to resist jumping
on the C#/C++/C/Java bandwagons.
.
- Follow-Ups:
- Re: Powers of 5
- From: Josh
- Re: Powers of 5
- References:
- Powers of 5
- From: Josh
- Powers of 5
- Prev by Date: Re: SAT is in P, CLIQUE is in P
- Next by Date: Re: Arguments against Cantor's diagonal
- Previous by thread: Powers of 5
- Next by thread: Re: Powers of 5
- Index(es):
Relevant Pages
|
