[Haskell-cafe] Re: FASTER primes

[Will Ness]

Daniel Fischer <daniel.is.fischer <at> web.de> writes:

> 
> Am Freitag 08 Januar 2010 19:45:47 schrieb Will Ness:
> > Daniel Fischer <daniel.is.fischer <at> web.de> writes:
> 
> 
> It's not tail-recursive, the recursive call is inside a celebrate.

It is (spMerge that is). It calls tail-recursive celebrate in a tail position. 
What you've done, is to eliminate the outstanding context, buy moving it 
inward. Your detailed explanation is more clear than that. :)

BTW when I run VIP code it is consistently slower than using just pairs, 
modified with wheel and feeder and all. So what's needed is to re-implement 
your approach for pairs:

 mergeSP (a,b) ~(c,d) = let (bc,bd) = spMerge b c d 
                           in (a ++ bc, bd)
     where 
      spMerge u [] d = ([], merge u d)           
      spMerge u@(x:xs) w@(y:ys) d = case compare x y of
               LT -> consSP x $ spMerge xs w  d
               EQ -> consSP x $ spMerge xs ys d
               GT -> consSP y $ spMerge u  ys d

 consSP x ~(a,b) = (x:a,b)   -- don't forget that magic `~` !!!


BTW I'm able to eliminate sharing without a compiler switch by using


 mtwprimes () = 2:3:5:7:primes 
   where
    primes = doPrimes 121 primes

 doPrimes n prs = let (h,t) = span (< n) $ rollFrom 11 
                  in h ++ t `diff` comps prs
 doPrimes2 n prs = let (h,t) = span (< n) $ rollFrom (12-1)
                   in h ++ t `diff` comps prs

 mtw2primes () = 2:3:5:7:primes
   where
    primes  = doPrimes 26 primes2
    primes2 = doPrimes2 121 primes2


Using 'splitAt 26' in place of 'span (< 121)' didn't work though.


How about them wheels? :)



> 
> Yes. It's still a "do what I tell you to" compiler, even if a pretty slick 
> one, not a "do what I mean" compiler. Sometimes, what you tell the compiler 
> isn't what you wanted.
> It's easier to predict when you give detailed step by step instructions.
>