Perfect Powers
Source: Appeared in 1977 High School Programming Contest. Taken from http://www.ocf.berkeley.edu/~wwu/riddles/cs.shtml
Problem:
Write a fast program that prints perfect powers (integers of the form mn, with m,n>1) in increasing numerical order.
So the first few outputs should be 4, 8, 9, 16, 25, 27, 32, ...
Find an algorithm that prints all perfect powers less than equal to N.
Update (05/03/2010):
Solution:
Nikhil Garg (CSE, IITD Sophomore) posted a solution which takes O(N) space and O(log N*sqrt N) time. Printing takes time O(N) though.
I posted a solution which takes O((sqrt N)*(log N)) space and O((sqrt N)*(log N)*(log N)) time.
Rajendran Thirupugalsamy (Research Assistant, Stony Brook University) posted a solution which takes O(log(N)) space and O(sqrt N * log N * log(log(N))) time. {Analysis done by Ramdas}
Aaditya Ramdas (CSE IITB Alumnus and working at Tower Research Capital) posted a solution which takes O(sqrt N) space and O((sqrt N)*(log N)*(log N)) time.
Interesting discussion and all solutions in comments!!
Problem:
Write a fast program that prints perfect powers (integers of the form mn, with m,n>1) in increasing numerical order.
So the first few outputs should be 4, 8, 9, 16, 25, 27, 32, ...
Find an algorithm that prints all perfect powers less than equal to N.
Update (05/03/2010):
Solution:
Nikhil Garg (CSE, IITD Sophomore) posted a solution which takes O(N) space and O(log N*sqrt N) time. Printing takes time O(N) though.
I posted a solution which takes O((sqrt N)*(log N)) space and O((sqrt N)*(log N)*(log N)) time.
Rajendran Thirupugalsamy (Research Assistant, Stony Brook University) posted a solution which takes O(log(N)) space and O(sqrt N * log N * log(log(N))) time. {Analysis done by Ramdas}
Aaditya Ramdas (CSE IITB Alumnus and working at Tower Research Capital) posted a solution which takes O(sqrt N) space and O((sqrt N)*(log N)*(log N)) time.
Interesting discussion and all solutions in comments!!
So how fast is really fast ?
ReplyDeleteO(log N * sqrt N ) seems trivial :
(I am essentially going to mimick Seive.) Maintain an array of length N with i'th entry true if i is perfect power , false else.
Starting from 2 whenever we see a non perfect power , mark all its powers as true. No number would have more then log N powers. Also we dont need to scan any number greater then sqrt N.
I don't know the best solution. Lets discuss :)
ReplyDelete@Nikhil..Seems good. Your algorithm is takes O(N) and O(logN*sqrtN) time.
Any algorithm using constant space?
Checking whether a number k is a perfect power or not (without using floating point computations) takes sigma (i varies from 2 to k) (log k/log i) operations which is O(klogk) operations.
So, this algorithm takes O(sigma (i varies from 2 to N) ilogi) which is O(N^2logN) operations.
This is trivial. Anything better?
@Nikhil : I liked your algo!
ReplyDeleteNever thought in this direction.
Another variant of Nikhil's algorithm.
ReplyDeleteIt will take approximately the same amount of time but less space.
Prepare sqrt N lists. For each i from 1 to sqrt N, prepare a list of all numbers i^2, i^3, ... i^k. Length of the list for an i would be (log_i N).
Now we have (sqrt N) sorted lists. Some lists have some common elements. We have to merge these lists. Number of elements in each list is less than equal to (log_2 N). Lets us assume that all lists are of equal length and have length (log_2 N)
If we have two lists of length a and b, merging takes a+b.
If we have three lists of length a,b, and c (c>b>a), merging takes 2(a+b)+c
and so on..
Let the total number of elements be totalnum <= (sqrt N)(log_2 N)
For (sqrt N) "equal" lists, time taken to merge is (log (sqrt N))*(Total Number of elements). {Standard merging equal lists algorithm}
So, time taken is O(logN*Total Number of elements) and space taken is O(Total Number of elements)
Time taken is O((sqrt N)*(log N)*(log N))
Space taken is O((sqrt N)*(log N))
So, space better :)
time approximately the same :)
yo! yo!
Nice...
ReplyDeleteGood part is- same scheme can infact be replicated to original seive as well. So that means I can seive upto 10^12 now without getting seg fault ! :)
:) Right..
ReplyDeleteInteresting problem.
ReplyDeleteI have a solution with O(3 * log(N)) space and O(N * log(log(N))) time complexity.
This follows from Pratik's solution.
Have two lists of length log(N). Let list A represent the base values. Init all elements in this list with '2'. Let list B represent the perfect power values. Fill ith element in B by value A[i]^i.
As you fill list B, create a min heap to find the least element in B.
S1: Using the min heap, pick the least perfect power in B and output it.
S2: Let i be the index of the least power element. Now increment A[i] and fill B[i] with value A[i]^i.
S3: Update the min heap according to the addition of this new element.
S4: Goto S1.
S1 and S3 require log(log(N)) and the loop will iterate for N times.
So total time complexity is O(N*log(log(N))).
Two log(N) size lists and a log(N) size min heap is used. So total memory complexity is O(3*log(N)).
@Rajendran.. looks awesome :) Thanx
ReplyDeleteSeems that we have got enough good solutions. Anyone can think of anything better?
ReplyDeletethe first solution that came to me seems simple n good. Everything is stored as a pair just so that you know how to calculate its next power.
ReplyDeleteForm a min heap of elements using the first value of the pairs (2^2,2)...((sqrt N)^2,sqrt N). Keep a variable which keeps the last output made.
Pick the minimum, output it (if it is greater than last output). Calculate its next power using the second element of the pair, and put it back into the min heap. Keep repeating. Each step of the update takes log N time since it is a min heap of sqrt N elements.
What is a good upper bound on the number of steps? O(sqrt N * log_2 N) seems correct but weak.
Takes O(sqrt N) space. And takes O(sqrt N * log N * log N) time which is pretty good.
I just want to clarify that Nikhil's first solution actually takes O(n) time, since he has to linearly go through the final list to output the true values. Or am I wrong?
Also rajendran's uses great space, but this trivial solution seems to be the best time till now. im sure we can do better.
i have a feeling rajendran underestimates his solution :P
ReplyDeletethe loop shudnt run N times as he said. since there is one output per loop, it runs equal times as the number of outputs which we have presently bounded at sqrt N * log N
so his soln shud really be O(sqrt N * log N * log(log N)) time right? or do i blabber? :P
@Ramdas..
ReplyDelete1) Your solution seems awesome. Takes same time as mine but directly improves the space by noting that you do not need to make all the lists beforehand. You just need to calculate the smallest element. Thanx.
2) Thanx for pointing out the flaw in Nikhil's solution. But I still believe that using appropriate data structures, the same thing can be done in less time.
3) \m/ \m/ Rajendran's solution improved :) Too good. Thanx!
@Ramdos, Good observation.
ReplyDeleteIn your solution if you form the min heap of elements using the first value of the pairs (2^2,2), (2^3,3) ...(2^log2_N,log2_N). You will get the same solution as mine.
Just to clarify, your S1 doesnt require log(log N) time. But your S2 does (calculating a power, which itself is at max logN will take log(logN) time).
ReplyDeleteAlso note that to implement that I need to store triplets (2^2,2,2), (2^3,2,3), ..., (2^logN, 2, logN), so that when I update (x^y, x, y) I can make it (x+1 ^ y, x+1, y). If I didn't store the x, I wouldn't be able to calculate the next element.
Also, yes, I agree, in my "simple" method (it's really simple isn't it?) if I store those triplets, it's the same as your solution.
Lastly, note that implicitly mine works on the assumptions k^n < k^n+1 < k^n+2 for each k... (since it bothered to consider k^n+1 only after using k^n, which caused the sqrt(N) space, and yours implicitly works on the assumption k^n < k+1^n < k+2^n... (since it bothered to consider k+1^n only after k^n was done with) which causes log(N) space. Subtle, beautiful, and makes a big difference.
So we now surely have a simple solution taking O(logN) space and O(sqrtN * logN * log(logN)) time. Any better in either space or time will be uber-cool.
PS: It's Ramdas, not Ramdos :)
@Ramdas..
ReplyDeleteSure, S2 requires O(log (log N)) time. Rajendran wrongly took that as an O(1) operation. Overall complexity does not change though.
Regarding S1, I too was tempted to believe that S1 requires O(log (log N)) as after "extracting" the minimum element, I was making it into a heap again, which is not needed. Another nice observation. Thanx.
S3 surely is O(log (log N)).
\m/ \m/ I am loving it. Thanx
@Ramdas,
ReplyDeleteSure, we need to keep the (x^y,x,y) triplets to calculate the next power.
Another good point. We need to take into account the complexity of multiplication/addition.
But I don't understand when you say my S2 step takes log(log N) time. It seems small to me ;)
Step S2 calculates triplet (x+1 ^y, x+1, y) from the triplet (x^y, x, y)
Max value of x, y respectively is sqrt(N), log N. And x has max of log(sqrt N) digits.
Assuming a multiplication of two 'd' digit numbers takes O(d*log d*log(log d)).
And naive exponentiation(a^b) uses b multiplications of log a digits, thus O(b * log a*log log a*log log log a). For simplicity denote this as O(b * log a*log log a). Refer here
Now calculating exponentiation for our case takes O(log N * log(sqrt N) * log log(sqrt N)), which seems very high.
Is there a way to achieve exponentiation in a better way ?
Or am I missing something ?
And naive exponentiation(a^b) uses b multiplications of log a digits, thus O(b * log a*log log a*log log log a).
ReplyDeleteI don't think that generalisation is correct. The first multiplication gives a 2*log a number, but the number of mult. is not a small number for you to call it O(log a), the bits will reach O(b loga), so you will later be multiplying O(b loga) digit numbers, and so possibly you will have another b hanging out there.
Waise, doing exponentiation the binary way makes more sense. ie a^37 = a^32*a^4*a and a^32 takes just 5 steps to compute from a. I tried analysing the complexity of this and got a very dirty expression.
It would help if someone could directly give us info about how what is the order of the C++ func pow(a,b) since that is probably implemented in the best possible way. However the problem with that is that pow(a,b) might be doing modular exponentiation since we are in a bounded space. So, we should probably google for the complexity of the best possible exponentiation a^b in terms of a,b. Can someone find this?
Sophie Nikhil, do help :D
Maybe it will end up being the case that because of this exponentiation step, this algo isn't the best in time.