[Haskell-cafe] Re: MonadFix

[apfelmus]

Joost Behrends wrote:
> apfelmus writes:
> 
>> Huh?  p < intsqrt n  is evaluated just as often as  p*p > n , with 
>> changing  n  . Why would that be less expensive? Btw, the code above 
>> test for  r==0  first, which means that the following  p*p > n  is 
>> tested exactly once for every prime candidate  p .
> 
> No. One point in the introduction of DivIter is, that intsqrt dividend is stored
> there and only recomputed, when a new factor is found.

Yes, I'm sorry, it didn't occur to me that recomputing per actual prime 
factor (with multiplicities, i.e. p^5 counted 5 times) is better than 
recomputing per candidate factor (without multiplicities, i.e. p^5 
counted only once).

> And concerning my cycled lists of summands as [2,4] or [2,4,2,4,2,4,2,6,2,6]:
> 
> an easily computable function stepping through all primes can only be
> a function, which yields primes plus some more odd numbers. This is, what i
> tried.

Yes, this scheme was my intention, too. The list  primes'  doesn't need 
to (and indeed shouldn't) be a list of actual primes, just a good guess like

   primes' = 2:[3,5]
   primes' = 2:3:scanl (+) 5 (cycle [2,4])

or something with [2,4,2,4,2,4,2,6,2,6]. So, it's an infinite list of 
numbers that qualify as candidates for being a prime factor of  n 
(which I called "prime candidates". Not a good name, since they don't 
need to be actual prime numbers.)


What I want to say is that using such an infinite is a nice way to 
separate the generate-prime-factor-candidates-logic from the 
test-all-those-candidates-loop. It's not necessary to hard-code it with 
a predicate like

> iterdivisors x | x == 0 = 3
>                | x == 1 = 5
>                | otherwise x = iterdivisors (x-1) + ((cycle [2,4]) !! x)

(which, in this particular form, is hopelessly inefficient) or special 
step functions like

> d2 :: DivIter                         -> DivIter
> d2 x |dividend x `mod` divisor x > 0  = x { divisor = divisor x + 2}
>      |otherwise                       = found x
> d4 :: DivIter                         -> DivIter
> d4 x |dividend x `mod` divisor x > 0  = x { divisor = divisor x + 4}
>      |otherwise                       = found x
> d6 :: DivIter                         -> DivIter
> d6 x |dividend x `mod` divisor x > 0  = x { divisor = divisor x + 6}
>      |otherwise                       = found x
>
> divisions :: DivIter             -> DivIter
> divisions y |or[divisor y == 3, 
>                 divisor y == 5]   = divisions (d2 y)
> 	    |divisor y <= bound y = divisions (d6$d2$d6$d4$d2$d4$d2$d4 y)
> 	    |otherwise            = y

It's not even necessary to treat 2 in a special way like

> twosect :: (Integer,[Integer]) -> (Integer,[Integer])
> twosect m |odd  (fst m) = m
>           |even (fst m) = twosect (div (fst m) 2, snd m ++ [2])

does, the  primes'  list handles it all.


Regards
apfelmus