11

規則的な数は、60 の累乗を均等に分割する数です。例として、60 2 = 3600 = 48 × 75 であるため、48 と 75 は両方とも 60 のべき乗の約数です。したがって、これらも規則的な数です。

これは、次の 2 の累乗への切り上げの拡張です。

大きな素因数を含む可能性のある整数値Nがあり、小さな素因数 (2、3、および 5) のみで構成される数値に切り上げたい

例:

  • f(18) == 18 == 21 * 32
  • f(19) == 20 == 22 * 51
  • f(257) == 270 == 21 * 33 * 51

この要件を満たす最小の数を見つける効率的な方法は何でしょうか?

関連する値は大きい可能性があるため、1 から始まるすべての通常の数値を列挙したり、すべての可能な値の配列を維持したりすることは避けたいと思います。

4

8 に答える 8

6

となるようにトリプルを直接列挙することにより、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)^2m log m~ mN

一定の幅 (対数) でも非常に高速に実行され、ハミング シーケンスの 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 のハミング数)。このような大きな数に対してこれが本当に必要な場合は、アルゴリズムを対数の代わりに整数値自体を使用するように切り替えることができますが、これは遅くなります。

于 2012-08-20T16:51:09.410 に答える
5

よし、願わくば 3 回目の魅力がここにあります。p の初期入力に対する再帰的な分岐アルゴリズム。ここで、N は各スレッド内で「構築」される数です。ここでの NB 3a-c は、個別のスレッドとして起動されるか、または (準) 非同期で実行されます。

  1. p の次に大きい 2 の累乗を計算し、これを R と呼びます。N = p.

  2. N > R ですか? このスレッドを終了します。p は小さな素因数だけで構成されていますか? あなたは終わった。それ以外の場合は、手順 3 に進みます。

  3. 3a ~ c​​ のいずれかの後、手順 4 に進みます。

    a) p を最も近い 2 の倍数に切り上げます。この数値は m * 2 として表すことができます。
    b) p を最も近い 3 の倍数に切り上げます。この数値は m * 3 として表すことができます。
    c) p を次のように切り上げます。最も近い 5 の倍数。この数値は m * 5 として表すことができます。

  4. p = m としてステップ 2 に進みます。

N の追跡に関する記帳は省きましたが、それはかなり簡単だと思います。

編集:6を忘れました、ypercubeに感謝します。

編集 2: これを 30 まで (5, 6, 10, 15, 30) 必要ないことに気づき、削除しました。

編集 3: (最後に約束します!) 30 の累乗チェックを追加しました。これにより、このアルゴリズムがすべての RAM を使い果たすのを防ぐことができます。

編集 4: finnw の観察により、30 の累乗を 2 の累乗に変更しました。

于 2012-02-11T18:40:48.167 に答える
3

m最小の数とすべての場所m >= Nを見つけたいと思います。m = 2^i * 3^j * 5^ki,j,k >= 0

対数を取ると、方程式は次のように書き直すことができます。

 log m >= log N
 log m = i*log2 + j*log3 + k*log5

log2、、およびto(サイズlog3に応じて十分に高い)の精度を計算できます。この場合、この問題は整数線形計画問題のように見え、このNP困難問題の既知のアルゴリズムの1つを使用して解決を試みることができます。log5logNN

于 2012-02-11T18:58:45.753 に答える
0

ここに私が考えた別の可能性があります:

NXビット長の場合、最小の正規数RNが範囲内になります
[2X-1, 2X]

たとえば、N = 257 (バイナリ100000001)の場合、 Rが次の 2 の累乗 (512) と正確に等しくない限り、R1xxxxxxxx

この範囲内のすべての正規数を生成するには、最初に奇数の正規数 (つまり、3 と 5 の累乗の倍数) を生成し、次に各値を取得して (ビットシフトによって) 2 を必要な回数だけ乗算します。この範囲にします。

Python の場合:

from itertools import ifilter, takewhile
from Queue import PriorityQueue

def nextPowerOf2(n):
    p = max(1, n)
    while p != (p & -p):
        p += p & -p
    return p

# Generate multiples of powers of 3, 5
def oddRegulars():
    q = PriorityQueue()
    q.put(1)
    prev = None
    while not q.empty():
        n = q.get()
        if n != prev:
            prev = n
            yield n
            if n % 3 == 0:
                q.put(n // 3 * 5)
            q.put(n * 3)

# Generate regular numbers with the same number of bits as n
def regularsCloseTo(n):
    p = nextPowerOf2(n)
    numBits = len(bin(n))
    for i in takewhile(lambda x: x <= p, oddRegulars()):
        yield i << max(0, numBits - len(bin(i)))

def nextRegular(n):
    bigEnough = ifilter(lambda x: x >= n, regularsCloseTo(n))
    return min(bigEnough)
于 2012-02-12T15:10:50.660 に答える
-1

この問題を解決するために、小さな c# プログラムを作成しました。あまり最適化されていませんが、開始です。このソリューションは、11 桁の数字の場合は非常に高速です。

private long GetRegularNumber(long n)
{
    long result = n - 1;
    long quotient = result;

    while (quotient > 1)
    {
        result++;
        quotient = result;

        quotient = RemoveFactor(quotient, 2);
        quotient = RemoveFactor(quotient, 3);
        quotient = RemoveFactor(quotient, 5);
    }

    return result;
}

private static long RemoveFactor(long dividend, long divisor)
{
    long remainder = 0;
    long quotient = dividend;
    while (remainder == 0)
    {
        dividend = quotient;
        quotient = Math.DivRem(dividend, divisor, out remainder);
    }
    return dividend;
}
于 2012-02-11T19:17:41.083 に答える
-1

あのね?私は、実際には「ダム」アルゴリズムが最速であるという命題にお金をかけます。これは、通常、次の通常の数値は、与えられた入力よりもはるかに大きくないように見えるという観察に基づいています。したがって、単にカウントアップを開始し、各増分後にリファクタリングして、通常の数値が見つかったかどうかを確認してください。ただし、使用可能なコアごとに 1 つの処理スレッドを作成し、N コアの場合、各スレッドは N 番目ごとに検査します。各スレッドが数値を検出するか、2 のべき乗のしきい値を超えたら、結果を比較します (実行中の最良の数値を維持します)。

于 2012-02-12T16:02:38.163 に答える