haskell - 除法返回 NaN

Question

我必须除以两个非常大的整数(7000+位是标准)。第一个总是小于第二个:

> let a = prod fp'
> let b = prod fq'
> a / b
NaN
> length . show $ a
7309
> length . show $ b
7309
> logBase 10 a  -- Ehm what? Whatever...
Infinity

我确信有一种方法可以除这些整数。实际代码有点长:

module Main
    where

import Data.List (transpose, sort, groupBy)
import Math.Sieve.Factor (factor, sieve)


thueMorse :: [Int]
thueMorse = 0 : interleave (map (1-) thueMorse) (tail thueMorse)
    where interleave (x:xs) ys = x : interleave ys xs


cc :: [[Integer]]
cc = zipWith (\n b -> [[2*n+1, 2*n+2], [2*n+2,2*n+1]]!!b) [0..] thueMorse


mapGroup f = map f . groupBy eq . sort
    where eq a b = fst a == fst b


takeOut xs = takeOut' xs [] []
    where takeOut' [] fs qs = [fs,qs]
          takeOut' ([b,e]:xs) fs qs
              | e > 0     = takeOut' xs ([b,e]:fs) qs
              | e < 0     = takeOut' xs fs ([b,-e]:qs)
              | otherwise = takeOut' xs fs qs


sub x y = takeOut . mapGroup collapse $ x ++ y'
    where y' = [(b, -e) | (b,e) <- y]
          collapse l = [fst $ head l, sum [e | (b,e) <- l]]


factor' :: (Integral a) => Int -> a -> [(a, a)]
factor' l = factor (sieve l)


factorize :: (Integral a) => Int -> [a] -> [(a, a)]
factorize l ns = mapGroup getsum $ concatMap (factor' l) ns
    where getsum l = (fst $ head l, sum . map snd $ l)


approx :: Int -> Double
approx n = prod fp' / prod fq'  -- <-- The problem is here
    where limit = 2^(n-1)
          [1:ps,qs] = transpose $ take limit cc
          [fp,fq] = map (factorize (2*limit)) [ps,qs]
          [fp',fq'] = sub fp fqb 
          prod l = fromIntegral . product $ [b^e | [b,e] <- l]

要运行的函数大约为。从 1 到 10 没有问题，但从 大约 11 开始，结果是 NaN...

> map approx [1..13]
[0.5,0.6666666666666666,0.7,0.7061728395061728,0.7070239390108867,0.7071021244800849,0.7071066220582782,0.707106777975181,0.7071067811490775,0.7071067811862988,NaN,NaN,NaN]

Answer 1

a 和 b 不是整数。

Prelude> :t (/)
(/) :: Fractional a => a -> a -> a
Prelude> :i Fractional
class Num a => Fractional a where
  (/) :: a -> a -> a
  recip :: a -> a
  fromRational :: Rational -> a
        -- Defined in ‘GHC.Real’
instance Fractional Float -- Defined in ‘GHC.Float’
instance Fractional Double -- Defined in ‘GHC.Float’

因此，您遇到的问题是浮点除法最终可能会产生 NaN 或 Infinity。

您可以为数字使用不同的类型，而不会丢失精度，或者以某种方式缩放结果。