Haskell求解AoC第6天第2题结果错误，疑因浮点精度问题

你的代码出现结果偏差的核心原因是**Float类型精度不足**：Float的尾数仅24位，只能精确表示2^24（约1677万）以内的整数，而你的输入参数d=434104122191218远超出这个范围，导致t²-4*d的计算、平方根求解都出现精度丢失，最终根的整数部分判断错误，结果差了3。

方案1：改用更高精度的Double类型 #

Double的尾数有53位，能精确表示2^53（约9e15）以内的整数，完全覆盖你的输入规模。只需将代码中所有Float替换为Double即可：

isInteger :: RealFrac a => a -> Bool
isInteger x = x == fromIntegral (round x)

big :: Double -> Int
big x | x <= 0 = error "big x"
    | otherwise = if isInteger x then round (x+1) else ceiling x

small :: Double -> Int
small x | x <= 0 = error "small x"
    | otherwise = if isInteger x then round (x-1) else floor x

numWays :: Double -> Double -> Int
numWays t d = small ((t + sqrt (t^2 - 4*d))/2) - big ((t- sqrt (t^2-4*d))/2) + 1

main :: IO ()
main = do
    print $ numWays 58819676.0 434104122191218.0

运行这段代码会输出正确结果41513103。

方案2：完全用整数运算避免浮点误差 #

如果想彻底规避浮点运算的精度风险，可以基于整数判别式计算：

1. 计算判别式disc = t*t - 4*d
2. 求disc的整数平方根s，判断disc是否为完全平方数
3. 根据是否为完全平方数，直接用整数运算计算满足条件的x数量

代码示例：

import Data.Function (fix)

-- 求整数平方根（更精确的实现，避免Double的潜在问题）
integerSqrt :: Integer -> Integer
integerSqrt n
    | n < 0     = error "integerSqrt: negative number"
    | otherwise = fix (\f s -> let s' = (s + n `div` s) `div` 2 in if s' >= s then s else f s') (n `div` 2 + 1)

numWaysInt :: Integer -> Integer -> Integer
numWaysInt t d =
    let disc = t*t - 4*d
        s = integerSqrt disc
    in if s*s == disc
        then -- 根为整数，需排除等于根的情况
             (t + s) `div` 2 - (t - s) `div` 2 - 1
        else -- 根为无理数，直接计算区间内整数个数
             (t + s) `div` 2 - ((t - s) + 1) `div` 2 + 1

main :: IO ()
main = do
    print $ numWaysInt 58819676 434104122191218

这段代码用自定义的整数平方根函数确保精度，完全不需要浮点运算，同样能得到正确结果。

内容的提问来源于stack exchange，提问作者qwertyuiop