Am Samstag, 22. Dezember 2007 21:28 schrieb Joost Behrends: Of course, one minute after I sent my previous mail, I receive this one :( However, one point, it might be faster to factor out all factors p in found and only then compute the intsqrt, like
found x = x{dividend = xstop, bound = intsqrt xstop, result = result x ++ replicate k p} where p = divisor x (xstop,k) = go (dividend x) 0 go n m | r == 0 = go q (m+1) | otherwise = (n,m) where (q,r) = n `divMod` p and then leaving out the recursive call in d2 etc. For a measurable difference, you'd need a number with some high prime powers as factors, but still, saves some work even for squares. > > 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 mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe