となるようにトリプルを直接列挙することにより、n 番目のメンバーの周りに任意に薄いハミング シーケンスのスライスを生成できます。~ n^(2/3)
(i,j,k)
N = 2^i * 3^j * 5^k
アルゴリズムは から機能しlog2(N) = i+j*log2(3)+k*log2(5)
ます。可能なすべての s を列挙し、可能なすべてk
の s ごとにj
トップi
を見つけてトリプルを見つけ(k,j,i)
、指定された高い対数トップ値より下の指定された「幅」内にある場合は「バンド」に保持します ( width
< 1 の場合、最大である可能性があります)そのような 1 つi
) は、それらを対数で並べ替えます。
WP はn ~ (log N)^3
、つまりランタイムと言ってい~ (log N)^2
ます。ここでは、シーケンス内で見つかったトリプルの正確な位置は気にしないため、元のコードからのカウント計算はすべて破棄できます。
slice hi w = sortBy (compare `on` fst) b where -- hi>log2(N) is a top value
lb5=logBase 2 5 ; lb3=logBase 2 3 -- w<1 (NB!) is log2(width)
b = concat -- the slice
[ [ (r,(i,j,k)) | frac < w ] -- store it, if inside width
| k <- [ 0 .. floor ( hi /lb5) ], let p = fromIntegral k*lb5,
j <- [ 0 .. floor ((hi-p)/lb3) ], let q = fromIntegral j*lb3 + p,
let (i,frac)=properFraction(hi-q) ; r = hi - frac ] -- r = i + q
-- properFraction 12.7 == (12, 0.7)
-- update: in pseudocode:
def slice(hi, w):
lb5, lb3 = logBase(2, 5), logBase(2, 3) -- logs base 2 of 5 and 3
for k from 0 step 1 to floor(hi/lb5) inclusive:
p = k*lb5
for j from 0 step 1 to floor((hi-p)/lb3) inclusive:
q = j*lb3 + p
i = floor(hi-q)
frac = hi-q-i -- frac < 1 , always
r = hi - frac -- r == i + q
if frac < w:
place (r,(i,j,k)) into the output array
sort the output array's entries by their "r" component
in ascending order, and return thus sorted array
スライス内のトリプルを列挙したら、上の最初のトリプルを見つけるのに(任意に薄いスライスの場合)実際O(1)
に時間がかかり、並べ替えと検索を行うのは簡単なことです。実際には、一定の幅 (対数) の場合、スライス内の数値の量 (平面の下の -spaceの「上部地殻」のメンバー) は再び、並べ替えに時間がかかります(そのため、線形であっても検索に時間がかかります)。その時)。しかし、いくつかの経験的観察に従って、幅をより大きな s に合わせて小さくすることができます。とにかく、トリプルの列挙の定数係数は、その後の並べ替えの係数よりもはるかに高くなります。N
(i,j,k)
log(N)
m ~ n^2/3 ~ (log N)^2
m log m
~ m
N
一定の幅 (対数) でも非常に高速に実行され、ハミング シーケンスの 1,000,000 番目の値を即座に計算し、0.05 秒で10 億番目の値を計算します。
「トリプルのトップ バンド」という最初のアイデアは、2008 年の DDJ ブログのディスカッションに関する私の投稿で引用されているように、Louis Klauder によるものです。
更新:コメントでGordonBGoodが指摘したように、バンド全体は必要ありませんが、ターゲットの上下に約 1 つまたは 2 つの値が必要です。アルゴリズムは、その趣旨で簡単に修正できます。倍精度での丸めの問題を回避するために、アルゴリズムを続行する前に、入力がハミング数自体であるかどうかもテストする必要があります。異なることが事前にわかっているハミング数の対数を比較する丸めの問題はありません (ただし、数列の 1 兆番目のエントリまで行くと、対数の値に約 14 桁の有効数字が使用されるため、1 ~ 2 桁の空きが残ります。実際には状況が不安定になっている可能性がありますが、10 億分の 1 の場合、有効数字は 11 桁しか必要ありません)。
update2:対数の倍精度は、これを約 20,000 から 40,000 桁未満の数値に制限することが判明しました (つまり、10 兆分の 1 から 100 兆分の 1 のハミング数)。このような大きな数に対してこれが本当に必要な場合は、アルゴリズムを対数の代わりに整数値自体を使用するように切り替えることができますが、これは遅くなります。