我正在尝试生成 Hamming numbers在 Haskell 中,尝试改进显而易见的东西(请原谅函数的命名)
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
我注意到我可以避免(较慢的)任意精度 Integer
如果我将数字表示为 2、3 和 5 指数的三元组,例如 data Power = Power { k2 :: !Int, k3 :: !Int, k5 :: !Int }
,其中数字被理解为 2<sup>k2</sup> * 3<sup>k3</sup> * 5<sup>k5</sup>
.两者的比较Power
s 然后变成
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₁ = 2<sup>i₁</sup> * 3<sup>j₁</sup> * 5<sup>k₁</sup>
和 p₂ = 2<sup>i₂</sup> * 3<sup>j₂</sup> * 5<sup>k₂</sup>
我们比较 p₁
的对数和 p₂
,大概适合 Double
.但实际上我们做得更好:我们首先计算它们的 GCD(通过找到相应指数对的 min
s——到目前为止只有 Int
算术!),除以 p₁
和 p₂
通过 GCD(通过从相应的指数中减去 min
s——也只是 Int
算术),并比较结果的对数。
但是,考虑到我们要遍历 Double
s,最终会有精度损失。这是我提出问题的基础:
Double
的有限精度何时可用咬我?即如何估计i, j, k
的顺序2<sup>i</sup> * 3<sup>j</sup> * 5<sup>k</sup>
的比较结果具有“相似”指数的数字会变得不可靠吗?- 我们除以 GCD(这可能会大大降低该任务的指数)这一事实如何修改对上一个问题的回答?
我做了一个实验,将以这种方式产生的数字与通过任意精度算法产生的数字进行比较,所有海明数直到第 1'000'000'000 个完全匹配(我花了大约 15 分钟和 600 megs 的 RAM 来验证)。但这显然不是证明。
最佳答案
Empirically ,它高于约 10 万亿分之一的汉明数,或更高。
使用你的好 GCD 技巧在这里对我们没有帮助,因为一些相邻的汉明数之间必然没有公因数。
更新:在 on ideone 和其他地方在线尝试,我们得到
4T 5.81s 22.2MB -- 16 digits used.... still good
-- (as evidenced by the `True` below), but really pushing it.
((True,44531.6794,7.275957614183426e-11),(16348,16503,873),"2.3509E+13405")
-- isTruly max min logval nth-Hamming approx.
-- Sorted logval difference as i,j,k value
-- in band in band in decimal
10T 11.13s 26.4MB
((True,60439.6639,7.275957614183426e-11),(18187,23771,1971),"1.4182E+18194")
13T 14.44s 30.4MB ...still good
((True,65963.6432,5.820766091346741e-11),(28648,21308,1526),"1.0845E+19857")
---- same code on tio:
10T 16.77s
35T 38.84s
((True,91766.4800,5.820766091346741e-11),(13824,2133,32112),"2.9045E+27624")
70T 59.57s
((True,115619.1575,5.820766091346741e-11),(13125,13687,34799),"6.8310E+34804")
---- on home machine:
100T: 368.13s
((True,130216.1408,5.820766091346741e-11),(88324,876,17444),"9.2111E+39198")
140T: 466.69s
((True,145671.6480,5.820766091346741e-11),(9918,24002,42082),"3.4322E+43851")
170T: 383.26s ---FAULTY---
((False,155411.2501,0.0),(77201,27980,14584),"2.80508E+46783")
关于algorithm - 汉明数和 double ,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/60803224/