[Haskell-cafe] List of all powers

[Brent Yorgey]

On Nov 14, 2007 12:32 PM, Kurt Hutchinson <kelanslists at gmail.com> wrote:

> As part of a solution I'm working on for Project Euler problem 119, I
> wanted to create an ordered list of all powers of all positive
> integers (starting with squares). This is what I came up with:
>
> powers = ( uniq . map fst . iterate next ) ( 1, ( 0, powertable ) )
>
> powertable = map (\ n -> map (\ p -> n ^ p ) [ 2 .. ] ) [ 2 .. ]
>
> next ( _, ( lim, ps ) ) =
>    ( p, ( lim', ps' ) )
>    where
>    ( c, p ) = minimumBy ( compare `on` snd ) . zip [ 0 .. lim ] .
> head . transpose $ ps
>    lim' = lim + ( if c == lim then 1 else 0 )
>    ( front, b : back ) = splitAt c ps
>    ps' = front ++ ( tail b : back )
>
> -- like the unix utility
> uniq [] = []
> uniq [x] = [x]
> uniq (x:y:ys)
>    | x == y    =     uniq (y:ys)
>    | otherwise = x : uniq (y:ys)
>
> Basically, think of a grid of numbers, each row is the list of powers
> for one integer. To find the next power in the sequence, look at the
> the first number in each row (since that will be the smallest number
> in the row), up to limit number of rows. The limit is calculated as
> the number of rows that we've already taken one number from, plus one.
> This exploits the fact that the row heads are initially ordered. If we
> use a number from a row, shift that row down to remove the number
> used.
>
> It does pretty well, but I'd welcome any comments, or even suggestions
> of a completely different algorithm (for this little exercise, or
> problem 119). Thanks.
>

The merging can be done much more simply and efficiently (this is code I
wrote when computing squarefree numbers in a blog
post<http://byorgey.wordpress.com/2007/09/01/squarefree-numbers-in-haskell/>a
few months ago):

-- merge two nondecreasing lists.
( # ) :: (Ord a) => [a] -> [a] -> [a]
[] # ys = ys
xs # [] = xs
xs@(x:xt) # ys@(y:yt) | x < y = x : (xt # ys)
                      | x > y = y : (xs # yt)
                      | otherwise = x : (xt # yt)

-- merge an infinite list of lists, assuming that each list
-- is nondecreasing and the lists occur in order of their first
-- element.
mergeAll :: (Ord a) => [[a]] -> [a]
mergeAll ([] : zs) = mergeAll zs
mergeAll (xxs@(x:xs) : yys@(y:ys) : zs)
    | x < y = x : mergeAll (xs : yys : zs)
    | otherwise = mergeAll ((xxs # yys) : zs)


Then you can simply define

powers = 1 : mergeAll powertable

I wrote some code to sum the first n powers and print the result, and
compiled (using -O2) first with your method, then with mergeAll.  Summing
the first 7000 powers took ~8s and ~0.1s respectively, so that's a pretty
big speedup. Based on seeing how the times scale, I suspect that your code
is O(n^2) or something of that sort, whereas mergeAll is essentially linear,
although without scrutinizing your code more closely I'm not exactly sure
why that would be the case.

-Brent
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20071114/3f9c277d/attachment-0001.htm