我正在尝试在Haskell中生成 海明数,并试图改进显而易见的方法(请原谅函数的命名)。
我注意到如果我将数字表示为2、3和5指数的三元组,如
mergeUniq :: Ord a => [a] -> [a] -> [a]
mergeUniq (x:xs) (y:ys) = case x `compare` y of
EQ -> x : mergeUniq xs ys
LT -> x : mergeUniq xs (y:ys)
GT -> y : mergeUniq (x:xs) ys
powers :: [Integer]
powers = 1 : expand 2 `mergeUniq` expand 3 `mergeUniq` expand 5
where
expand factor = (factor *) <$> powers
我注意到如果我将数字表示为2、3和5指数的三元组,如
data Power = Power { k2 :: !Int, k3 :: !Int, k5 :: !Int }
,则可以避免(更慢的)任意精度Integer
。其中数字被理解为2k2 * 3k3 * 5k5
。然后两个Power
的比较变成了:instance Ord Power where
p1 `compare` p2 = toComp (p1 `divP` gcdP) `compare` toComp (p2 `divP` gcdP)
where
divP p1 p2 = Power { k2 = k2 p1 - k2 p2, k3 = k3 p1 - k3 p2, k5 = k5 p1 - k5 p2 }
gcdP = Power { k2 = min (k2 p1) (k2 p2), k3 = min (k3 p1) (k3 p2), k5 = min (k5 p1) (k5 p2) }
toComp Power { .. } = fromIntegral k2 * log 2 + fromIntegral k3 * log 3 + fromIntegral k5 * log 5
因此,粗略地比较 p₁ = 2i₁ * 3j₁ * 5k₁
和 p₂ = 2i₂ * 3j₂ * 5k₂
,我们比较 p₁
和 p₂
的对数,这些对数应该适合于 Double
。但实际上,我们做得更好:首先计算它们的 GCD(通过找到相应指数对的 min
- 目前仅涉及Int
算术!),将 p₁
和 p₂
除以 GCD(通过从相应指数中减去min
- 也仅涉及Int
算术),然后比较结果的对数。
但是,由于我们使用了 Double
,最终会存在精度损失。这就是我提问的原因所在:
- 什么时候双精度浮点数的有限精度会影响我?也就是说,如何估计, , 的顺序,使得比较
2i * 3j * 5k
与具有“类似”指数的数字的结果将变得不可靠? - 我们通过求GCD而进行的除法会降低此任务的指数,这样会如何修改上一个问题的答案?
我做了一个实验,将以这种方式生成的数字与通过任意精度算术生成的数字进行比较,所有Hamming数字都匹配到第1'000'000'000个(这花费了我大约15分钟和600兆字节的RAM来验证)。但这显然不是一个证明。
Double
中没有直接拥有$x$和$y$的对数,但是我们可以使用Double
算术从2、3和5的对数(每个对数乘以指数然后相加)中计算出它们?你是否将2、3和5的对数作为最接近可表示值在Double
中(尽管一些数学库可能存在更大的误差,尽管对数比某些超越函数容易计算)? - Eric Postpischil