apfelmus apfelmus at quantentunnel.de
Sat Dec 22 16:38:48 EST 2007

```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

```