3

Strassen のアルゴリズムの奇数行列の問題に対処しようとしています。私の実装では、特定の時点で再帰を切り捨て、それを Q と呼び、標準の実装に切り替えます。したがって、静的なパディングを行う場合、実際には次の 2 のべき乗までパディングする必要はありません。m < Q となるように、入力行列の次元よりも大きい最小の m*2^k までパディングする必要があるだけです。

これを実装するのに問題があります-主に、何が最も効率的かがわからないためです。可能なすべての m 値をループする必要がありますか?それとも、与えられた各入力からインクリメントして、それらが基準を満たしているかどうかをテストする必要がありますか?

4

2 に答える 2

0

上記をインスピレーションとして使用して、最小パディングを見つけるためのより簡潔なアルゴリズムを見つけたと思います

数値がしきい値を下回るまで繰り返し 2 で割り切れる数を作成し、それを 2**counter で乗算して、行列をパディングする必要があるサイズを取得します。しきい値

unsigned int minPad(unsigned int inSize, unsigned int threshold) {
    unsigned int counter = 0;
    while (inSize > threshold) {
        inSize++;
        inSize >>= 1;
        counter ++;
    }
    return inSize << counter;
}
于 2016-11-02T17:58:11.243 に答える
0

あなたは正しいです。m * 2^k までのパディングは、次の 2 の累乗までのパディングよりもはるかに優れたパフォーマンスを発揮するはずです。

この関数で計算された値までパディングする必要があると思います:

int get_best_pud_up_value(int actual_size, int Q) {
    int cnt = 0;
    int n = actual_size;
    while(n > Q) {
        cnt++;
        n /= 2;
    }

    // result should be smallest value such that:
    // result >= actual_size AND
    // result % (1<<cnt) == 0

    if (actual_size % (1<<cnt) == 0) {
        return actual_size;
    } else {
        return actual_size + (1<<cnt) - actual_size % (1<<cnt);
    }
}
于 2012-03-28T14:56:38.403 に答える