Geek Answers Handbook

Haskell Performance Optimization

I am writing code to find the nth number of Ramanujan-Hardy. The Ramanujan Hardy number is defined as

n = a^3 + b^3 = c^3 + d^3

means that n can be expressed as the sum of two cubes.

I wrote the following code in haskell:

-- my own implementation for cube root. Expected time complexity is O(n^(1/3))
cube_root n = chelper 1 n
                where
                        chelper i n = if i*i*i > n then (i-1) else chelper (i+1) n

-- It checks if the given number can be expressed as a^3 + b^3 = c^3 + d^3 (is Ramanujan-Hardy number?)
is_ram n = length [a| a<-[1..crn], b<-[(a+1)..crn], c<-[(a+1)..crn], d<-[(c+1)..crn], a*a*a + b*b*b == n && c*c*c + d*d*d == n] /= 0
        where
                crn = cube_root n

-- It finds nth Ramanujan number by iterating from 1 till the nth number is found. In recursion, if x is Ramanujan number, decrement n. else increment x. If x is 0, preceding number was desired Ramanujan number.    
ram n = give_ram 1 n
        where
                give_ram x 0 = (x-1)
                give_ram x n = if is_ram x then give_ram (x+1) (n-1) else give_ram (x+1) n

In my opinion, the time complexity for checking whether a number is a Ramanujan number is O (n ^ (4/3)).

When running this code in ghci, it takes time even to search for the second Ramanujan number.

What are the possible ways to optimize this code?

+4
source share
2 answers

, . - - , , .. A ^ 3 + b ^ 3 = c ^ 3 + d ^ 3, a < b a < c < .

, , , .

start - , :

cubes a = [ (a^3+b^3, a, b) | b <- [a+1..] ]

:

allcubes = sort $ concat [ cubes 1, cubes 2, cubes 3, ... ]

, , , concat sort . , cubes a , :

allcubes = cubes 1 `merge` cubes 2 `merge` cubes 3 `merge` ...

. merge :

 merge [] bs = bs
 merge as [] = as
 merge as@(a:at) bs@(b:bt)
  = case compare a b of
      LT -> a : merge at bs
      EQ -> a : b : merge at bt
      GT -> b : merge as bt

, , . cubes a cubes (a+1) ,

cubes a = ...an initial part... ++ (...the rest... `merge` cubes (a+1) )

span:

 cubes a = first ++ (rest `merge` cubes (a+1))
   where
     s = (a+1)^3 + (a+2)^3
     (first, rest) = span (\(x,_,_) -> x < s) [ (a^3+b^3,a,b) | b <- [a+1..]]

, cubes 1 - a ^ 3 + b ^ 3, a < b .

-, , :

 sameSum (x,a,b) (y,c,d) = x == y
 rjgroups = groupBy sameSum $ cubes 1

- , > 1:

 rjnumbers = filter (\g -> length g > 1) rjgroups

:

ghci> take 10 rjnumbers

[(1729,1,12),(1729,9,10)]
[(4104,2,16),(4104,9,15)]
[(13832,2,24),(13832,18,20)]
[(20683,10,27),(20683,19,24)]
[(32832,4,32),(32832,18,30)]
[(39312,2,34),(39312,15,33)]
[(40033,9,34),(40033,16,33)]
[(46683,3,36),(46683,27,30)]
[(64232,17,39),(64232,26,36)]
[(65728,12,40),(65728,31,33)]
+7

is_ram Ramanujan, a, b, c, d cuberoot, n.

a b a ^ 3 + b ^ 3 1 .

Ramanujan , , a >= 2 ( , 2 ).

, O (n ^ (2/3)) , O (n.n ^ (4/3)).

0

More articles:


All Articles