[Haskell-cafe] Re: Importing Data.Char speeds up ghc around 70%

22 Dec 2007

      Daniel Fischer  writes:
...
I can't reproduce it, both run in 130s here (SuSE 8.2, 1200MHz Duron).
However, it's running over 30 minutes now trying to factorise 2^88+1 without 
any sign of approaching success, which suggests your code has a bug (the 
factorization is [257,229153,119782433,43872038849], so even a naive approach 
shouldn't take much longer than a minute).
I have found the problem: We must possibly work recursive on a found factor.
This was done in former versions, but got lost when isolating the function 
"found". Here is a corrected version - complete again for reproducing easily
the strange behavior with Data.Char. It decomposes 2^88+1 in 13 seconds.

module Main
    where

import IO
import System.Exit
--import Data.Char

main = do
    hSetBuffering stdin LineBuffering
    putStrLn "Number to decompose ?"
    s <- getLine
    if s == [] then
        exitWith ExitSuccess
        else do
            putStrLn (show$primefactors$read s)
            main

data DivIter = DivIter {dividend :: Integer, 
                        divisor  :: Integer,
                        bound    :: Integer, 
                        result   :: [Integer]}

intsqrt m = floor (sqrt $ fromInteger m)

primefactors :: Integer -> [Integer]
primefactors n | n<2       = []
               | even n    = o2 ++ (primefactors o1)
               | otherwise = if z/=1 then result res ++[z] else result res
                   where 
                       res = divisions (DivIter {dividend = o1, 
                                                 divisor = 3, 
                                                 bound = intsqrt(o1),
                                                 result = o2})
                       z = dividend res  -- is 1 sometimes
                       (o1,o2) = twosect (n,[])

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

found :: DivIter -> DivIter
found x = x {dividend = xidiv,
	        bound = intsqrt(xidiv), 
	       result = result x ++ [divisor x]}
    where xidiv = (dividend x) `div` (divisor x)

d2 :: DivIter                         -> DivIter
d2 x |dividend x `mod` divisor x > 0  = x {divisor = divisor x + 2}
     |otherwise                       = d2$found x
d4 :: DivIter                         -> DivIter
d4 x |dividend x `mod` divisor x > 0  = x {divisor = divisor x + 4}
     |otherwise                       = d4$found x
d6 :: DivIter                         -> DivIter
d6 x |dividend x `mod` divisor x > 0  = x {divisor = divisor x + 6}
     |otherwise                       = d6$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

And now it uses also 1.34 minutes for 2^61+1 without importing Data.Char.
Hmmm ...

Cheers, Joost

[Haskell-cafe] Re: Importing Data.Char speeds up ghc around 70%

Joost Behrends