General Programming Help
 
Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
 
User Name:
Password:
Remember me
 



Go Back   Dev Articles Community ForumsProgrammingGeneral Programming Help

Reply
Add This Thread To:
  Del.icio.us   Digg   Google   Spurl   Blink   Furl   Simpy   Y! MyWeb 
Thread Tools Search this Thread Display Modes
 
Unread Dev Articles Community Forums Sponsor:
  #1  
Old April 5th, 2006, 03:06 AM
programmer programmer is offline
Registered User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Apr 2006
Posts: 1 programmer User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 6 m 32 sec
Reputation Power: 0
Question Algorithm to compute x^n in O(log n) steps

Hello everyone,

This is my first post

Does anyone know how to write a program to compute x^n (x to the power of n) in just O(log n) steps (log n base 2)?

Reply With Quote
  #2  
Old April 5th, 2006, 07:22 AM
Icon's Avatar
Icon Icon is offline
Command Line Warrior
Dev Articles Beginner (1000 - 1499 posts)
 
Join Date: Sep 2005
Posts: 1,021 Icon User rank is Private First Class (20 - 50 Reputation Level)Icon User rank is Private First Class (20 - 50 Reputation Level) 
Time spent in forums: 2 Weeks 8 h 12 m 36 sec
Reputation Power: 14
Hint:

X^8 could be seen as:
X^4 * X^4 or (X^4)^2

X^4 on its turn could be seen as:
X^2 * X^2 or (X^2)^2

so X^8 could also be seen as:
((X^2)^2)^2

Note that there are roughly (log 8)=3 operations here..

With this (rather big) hint you should be able to code the algorithm..

Good luck!

Reply With Quote
  #3  
Old April 6th, 2006, 06:16 PM
Cirus Cirus is offline
Contributing User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Mar 2005
Posts: 296 Cirus User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 1 Day 13 h 30 m 11 sec
Reputation Power: 13
Quote:
Originally Posted by Icon
Hint:

X^8 could be seen as:
X^4 * X^4 or (X^4)^2

X^4 on its turn could be seen as:
X^2 * X^2 or (X^2)^2

so X^8 could also be seen as:
((X^2)^2)^2

Note that there are roughly (log 8)=3 operations here..

With this (rather big) hint you should be able to code the algorithm..

Good luck!


Good Observation.

Reply With Quote
  #4  
Old July 22nd, 2007, 06:06 AM
lyanaz lyanaz is offline
Registered User
Dev Articles Newbie (0 - 499 posts)
 
Join Date: Jul 2007
Posts: 1 lyanaz User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 12 m 24 sec
Reputation Power: 0
To find x^n in 0(log n)

algo:

power (x,n)
{
if (n==0)
return 1;

if (n is even) // or if (n%2==0)
return (power(x,n/2) * power (x,n/2) );

else if (n is odd)
return (power (x,n/2) * power (x,n/2) * x );

}

Reply With Quote
Reply

Viewing: Dev Articles Community ForumsProgrammingGeneral Programming Help > Algorithm to compute x^n in O(log n) steps


Developer Shed Advertisers and Affiliates


Thread Tools  Search this Thread 
Search this Thread:

Advanced Search
Display Modes  Rate This Thread 
Rate This Thread:


Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
View Your Warnings | New Posts | Latest News | Latest Threads | Shoutbox
Forum Jump

Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
  
 


Powered by: vBulletin Version 3.0.5
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.

© 2003-2018 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap