Числа Хэмминга и двойная точность

Question

Я играл с генерацией чисел Хэмминга в 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 с становится

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 arithmeti c!), Делим p₁ и p₂ на GCD (вычитая min s из соответствующих показателей - также только Int arithmeti c), и сравниваем логарифмы результатов.

Но, учитывая, что мы go - Double s, со временем произойдет потеря точности. И это основание для моих вопросов:

1. Когда конечная точность в Double s укусит меня? То есть как оценить порядок i, j, k, для которого результаты сравнения 2<sup>i</sup> * 3<sup>j</sup> * 5<sup>k</sup> с числами с «похожими» показателями станут ненадежными?
2. Как влияет тот факт, что мы go делим GCD (который, по-видимому, значительно снижает показатели для этой задачи) изменить ответ на предыдущий вопрос?

Я провел эксперимент, сравнивая числа, полученные таким образом, с числами, полученными путем прохождения произвольно точность арифметики c, и все числа Хэмминга вплоть до 1 000 000 000 тысяч точно совпадают (что потребовало у меня около 15 минут и 600 мегабайт оперативной памяти для проверки). Но это явно не доказательство.

Answer 1

Эмпирически , оно выше примерно 10 триллионных чисел Хэмминга или выше.

Использование вашего приятного трюка с GCD здесь не поможет, потому что некоторые соседние числа Хэмминга непременно не имеют общие факторы между ними.

обновление: пробная онлайн на 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")

Answer 2

Полагаю, что вы можете использовать адаптивную произвольную точность для вычисления журнала.

Если вы выберете базу журнала 2, то log2(2^i) тривиально. Это исключает 1 фактор, и log2 имеет то преимущество, что его легче вычислять, чем натуральный логарифм (https://en.wikipedia.org/wiki/Binary_logarithm дает алгоритм, например, есть также Шенкс ...).

Для log2 (3) и log2 (5), вы бы разработали достаточно терминов, чтобы различить guish обоих операндов. Я не знаю, приведет ли это к большему количеству операций, чем непосредственное возведение в степень 3 ^ j и 5 ^ k в большой целочисленной арифметике c и подсчет старшего бита ... Но они могут быть предварительно сведены в таблицу до необходимого количества цифр.