4

2つのnビット数AとBの乗算は、シフトの合計として理解できます。

 (A << i1) + (A << i2) + ...

ここで、i1、i2、...は、Bで1に設定されているビット数です。

次に、PLUSをORに置き換えて、実際に必要な新しい操作を取得しましょう。

 (A << i1) | (A << i2) | ...

この操作は、多くのより高速なアルゴリズム（Schönhage-Strassenなど）が存在する通常の乗算​​と非常によく似ています。ここで紹介した操作の同様のアルゴリズムはありますか？

数値のサイズは6000ビットです。

編集： 何らかの理由でコメントを投稿するためのリンク/ボタンがないので（理由はわかりますか？）、質問を股間で編集します。私は確かに、上記で定義された操作に対してO（n ^ 2）アルゴリズムよりも高速なものを検索します。そして、はい、私はそれが通常の乗算​​ではないことを知っています。

4

5 に答える 5

0


「ここで提示した操作に類似したアルゴリズムはありますか?」と書いたときに、指定した加算手法の名前を尋ねていると思います...

農民の乗算法を見たことがありますか？
この例の 3 列目が表示されない場合は、Wikipedia の説明を読んでください。

 B X  A
27 X  15  : 1
13    30  : 1
 6    60  : 0
 3   120  : 1
 1   240  : 1

B is 27 == binary form 11011b

27x15 = 15 + 30 + 120 + 240
      = 15<<0 + 15<<1 + 15<<3 + 15<<4
      = 405

おなじみですね。

これがあなたのアルゴリズムです。

  1. 小さい方の数字をAとして選択してください
    • 結果領域としてCを初期化します
    • Bはゼロではありませんが 、
      1. Bのがの場合lsb、Aを Cに追加します。1
    • 左シフトAを 1 回
    • 右シフトB 1 回
    • Cには乗算結果があります（ sizeof Cをロールオーバーしない限り）

更新6000 ビットにわたるシフトおよび OR 演算の高速アルゴリズムを取得しようとしている場合、
実際には 1 つある可能性があります。そこはもう少し考えます。

ある数字を他の数字の上に「ぼかす」ように見えます。面白い。
ここではかなり大まかな例を示しますが、

110000011 X 1010101 would look like
      110000011
    110000011
  110000011
110000011
---------------
111111111111111

2 つの数値の の数1によって、すべてのビットが設定された数値に対するブラーの量が決まります。
あなたはそれで何をしたいのだろうか...

Update2これは、2 つの 6000 ビット数を使用したシフト + OR 操作の性質です。

  1. 結果はもちろん12000ビットになります
    • 操作は 2 つのビット ストリームで実行できます。しかし、完全に行う必要はありません
    • 12000 ビット ストリームの「中間」部分はほぼ確実にすべて1になります(両方の数値がゼロでない場合)
    • 問題は、12000 ビット ストリームの両端を取得するためにこの操作を処理する必要がある深さを特定することです。
    • ストリームの両端のパターンは、両方の数値に存在する連続する1の最大数に依存します。

私はまだこれのためのきれいなアルゴリズムを手に入れていません。再確認したい、またはここから先に進みたい他の人のために更新しました。また、そのような操作の必要性を説明すると、さらに興味をそそられるかもしれません:-)

于 2009-07-02T14:12:46.093 に答える
0

私が思いついた最善の方法は、ループ ロジックで高速アウトを使用することです。themis で説明されている非ゼロ アプローチを使用する可能性と組み合わせると、N^2 問題の 2% 未満を検査することで質問に答えることができます。

以下は、80% から 99% の間の数値のタイミングをゼロにするコードです。数値が約 88% ゼロになると、themis のアプローチを使用すると、より良い結果が得られます (ただし、以下のサンプルではコード化されていません)。

これは高度に理論的な解決策ではありませんが、実用的です。

OK、ここに問題空間の「理論」があります。

基本的に、X (出力) の各ビットは、A のビットを上部 (MSB から LSB へ、左から右へ) に沿って配置し、B のビットを側面 (上から下にMSBからLSBへ）。対角線のいずれかが 1 の場合、X のビットは 1 であるため、セル トラバーサルでアーリー アウトを実行できます。

以下のコードはこれを行っており、~87% ゼロの数値であっても、~2% のセルをチェックするだけでよいことを示しています。密度の高い (1 の数が多い) 数の場合、その割合はさらに低下します。

言い換えれば、トリッキーなアルゴリズムを気にせず、効率的なロジック チェックを行うだけです。秘訣は、出力のビットをグリッドの対角線として見ることだと思います。A のビットと B のビットのシフト OR を比較するのではありません。 A と B の at と、ビットに適切にインデックスを付ける方法。

うまくいけば、これは理にかなっています。これについてもう少し説明する必要がある場合はお知らせください (または、このアプローチに問題がある場合)。

注: 問題空間をもう少しよく知っていれば、それに応じてアルゴリズムを最適化できます。数値がほとんどゼロでない場合、このアプローチはより多くの計算と必要なストレージ スペース (sizeof(int) * NNZ) になるため、themis よりも優れています。

注 2: これはデータが基本的にビットであることを前提としており、.NET の BitArray を使用してデータを格納およびアクセスしています。これが他の言語に翻訳されたときに大きな頭痛の種になるとは思いません。基本的な考え方は今でも通用します。

using System;
using System.Collections;

namespace BigIntegerOr
{
    class Program
    {
        private static Random r = new Random();

        private static BitArray WeightedToZeroes(int size, double pctZero, out int nnz)
        {
            nnz = 0;
            BitArray ba = new BitArray(size);
            for (int i = 0; i < size; i++)
            {
                ba[i] = (r.NextDouble() < pctZero) ? false : true;
                if (ba[i]) nnz++;
            }
            return ba;
        }

        static void Main(string[] args)
        {
            // make sure there are enough bytes to hold the 6000 bits
            int size = (6000 + 7) / 8;
            int bits = size * 8;

            Console.WriteLine("PCT ZERO\tSECONDS\t\tPCT CELLS\tTOTAL CELLS\tNNZ APPROACH");
            for (double pctZero = 0.8; pctZero < 1.0; pctZero += 0.01)
            {
                // fill the "BigInts"
                int nnzA, nnzB;
                BitArray a = WeightedToZeroes(bits, pctZero, out nnzA);
                BitArray b = WeightedToZeroes(bits, pctZero, out nnzB);

                // this is the answer "BigInt" that is at most twice the size minus 1
                int xSize = bits * 2 - 1;
                BitArray x = new BitArray(xSize);

                int LSB, MSB;
                LSB = MSB = bits - 1;

                // stats
                long cells = 0;
                DateTime start = DateTime.Now;

                for (int i = 0; i < xSize; i++)
                {
                    // compare using the diagonals
                    for (int bit = LSB; bit < MSB; bit++)
                    {
                        cells++;
                        x[i] |= (b[MSB - bit] && a[bit]);
                        if (x[i]) break;
                    }

                    // update the window over the bits
                    if (LSB == 0)
                    {
                        MSB--;
                    }
                    else
                    {
                        LSB--;
                    }

                    //Console.Write(".");
                }

                // stats
                TimeSpan elapsed = DateTime.Now.Subtract(start);
                double pctCells = (cells * 100.0) / (bits * bits);
                Console.WriteLine(pctZero.ToString("p") + "\t\t" +elapsed.TotalSeconds.ToString("00.000") + "\t\t" +
                    pctCells.ToString("00.00") + "\t\t" + cells.ToString("00000000") + "\t" + (nnzA * nnzB).ToString("00000000"));
            }

            Console.ReadLine();
        }
    }
}
于 2009-07-06T20:01:59.707 に答える