performance - Trying to optimize this algorithm/code to compute the largest subset of mutually coprime integers between a and b -

i'm writing function in haskell takes in 2 integers , b , computes length of largest subset(s) of [a,b] such elements mutually coprime. now, reason because believe investigating such values might yield means of producing trivial lesser bounds (possibly one's large enough imply actual primes in various per conjectured ranges such consecutive squares). naturally i'm trying run pretty large numbers.

unfortunately below code not running fast enough practical me use. think flaw haskell's laziness policy causing issues, neither know syntax nor place need force execution prevent operations accumulating.

subsets [] = [[]] subsets (x:xs) = subsets xs ++ map (x:) (subsets xs)  divides b = (mod b == 0)  coprime b = ((gcd b) == 1)  mutually_coprime []  = true mutually_coprime (x:xs) | (coprime_list x xs) = mutually_coprime xs                         | otherwise = false  coprime_list _ [] = true coprime_list (x:xs) | (coprime x) = coprime_list xs                       | otherwise = false  coprime_subsets b = coprime_subsets_helper (subsets [a..b])  coprime_subsets_helper [] = [] coprime_subsets_helper (x:xs) | (mutually_coprime x) = [x] ++ (coprime_subsets_helper xs)                               | otherwise = coprime_subsets_helper xs  coprime_subset_length b = max_element (map list_length (coprime_subsets b))  list_length [] = 0 list_length (x:xs) = 1 + list_length xs  max_element = max_element_helper 0  max_element_helper [] = max_element_helper (x:xs) | (x > a) = max_element_helper xs x                             | otherwise = max_element_helper xs 

just make clear sort of input hanging upon, "coprime_subsets 100 120" never seems halt me. left running, got up, did other stuff , came later. it still running. suspect large bottleneck computing subsets immediately. however, don't want put artificial lower bound on subsets generated. might sieve out of coprime sets leaving me nothing.

what have tried far:

• i replaced original coprime function had gcd. used modulo , iterative checking integers. presume gcd used euclid's algorithm should run faster, in theory.

• i've been trying think of way build generation of subsets coprime set generator. far haven't been able come anything. i'm not sure if anything.

• i've been looking anywhere haskell's laziness policy might hurting me. nothing stands out, i'm sure.

i'm aware efficiency issue environment use (winhugs). i'd issue; however, when asked how determine largest subset (for general n sized ranges) on math stack exchange answers received indicated computationally speaking slow thing calculate. if so, that's fine. hoping maybe able run through of ranges interested in without taking forever.

i know efficiency not allowed on site; however, have tried quite bit , i'm not trying lazy here. know haskell has quite few weird quirks can force being deceptively inefficient. it's been while since i've coded in it, , suspect i've landed in 1 of quirks.

first, must find out slow.

when working numbers, 1 should use fastest representation provides required accuracy , range. code doesn't have top-level type signatures, ghc infers type signature coprime_subsets as

coprime_subsets :: integral => -> -> [[a]] 

this allows ghc choose integral , happily choose integer, slower int. integer, program spends huge amount of time computing gcds. forcing ghc use int takes run time down 6 seconds 1 second, since ghc can integer math on machine integers directly.

nb: practice provide top-level type signatures. when compiler doesn't benefit them, humans do.

now, on meat of problem. running

main = print . length $ coprime_subsets (100 :: int) 120 main :: io () 

with profiling enabled (stack build --profile stack) , passing +rts -p -h executable (-p time , -h space) gives breakdown:

cost centre            module  src                            %time %alloc  subsets                coprime src/coprime.hs:(4,1)-(5,52)     52.5  100.0 coprime                coprime src/coprime.hs:11:1-26          25.5    0.0 coprime_list           coprime src/coprime.hs:(19,1)-(21,41)   18.5    0.0 coprime_subsets_helper coprime src/coprime.hs:(27,1)-(29,69)    1.8    0.0 mutually_coprime       coprime src/coprime.hs:(14,1)-(16,43)    1.7    0.0 

when using integer, vast majority (~78%) of time spent in coprime test. majority spent constructing powerset, let's there first.

next, must understand why slow.

there 3 strategies speed up:

1. improve asymptotic complexity.
2. improve constant factors.
3. call fewer times.

which of these might apply subsets? (1) obvious choice. constructing powerset o(2^n), asymptotic improvements here helpful indeed. can find any? theoretically, should able to. daniel suggests, problem equivalent maximal cliques problem, exponential. however, maximal cliques has solution smaller base, means should able find asymptotic improvement problem well.

the key insight reducing asymptotic complexity (and number of times call it) generating vast majority of subsets throw them away later on when check them coprimality. if can avoid generating bad subsets initially, generate fewer subsets , perform fewer checks coprimality. if number of pruned results proportional size of entire computation tree, yield asymptotic improvement. sort of pruning common in functional algorithm optimization; can see instructive example in richard bird's sudoku solver. in fact, if can write function generates non-mutually-coprime subsets, have solved entire problem!

finally, ready fix it!

we can modifying original generator subsets filter out non-coprime terms goes:

coprimesubsets [] = [[]] coprimesubsets (x:xs)   = coprimesubsets xs ++ map (x :) (coprimesubsets (filter (coprime x) xs)) 

(there clever fold can use here if think hard explicit recursion fine too.)

once this, can find coprime subsets of [100..120] in ~0.1 seconds, order of magnitude improvement. cost centre report tells story:

cost centre    module          src                            %time %alloc  main           main            <built-in>                      42.9    0.5 coprimesubsets coprime         src/coprime.hs:(33,1)-(35,75)   28.6   67.4 caf            ghc.io.encoding <entire-module>                 14.3    0.1 coprime        coprime         src/coprime.hs:13:1-26          14.3   31.1 

now spend of our time doing io , such. furthermore, number of calls our coprime test 3,848, improvement of several orders of magnitude. can find coprime subsets of [100..150] in 3 seconds, compared to... well, didn't wait finish, @ least few minutes.

the next place speedups might in memoizing coprime function, since problem involves computing same arguments many times.