strassenの奇数行列のための最適化された静的な埋め込み

Question

私はstrassenのアルゴリズムのための奇数行列の問題に取り組もうとしています。私の実装はある時点で再帰を切り捨て、Qと呼んで標準実装に切り替えます。したがって、静的なパディングを行う際には、実際には2の次のべき乗までパディングする必要はありません。入力行列の次元よりも最小のm * 2^kまでパッドする必要があります。

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

Answer 1

あなたは正しいですか？インスピレーションとして

上記を使用して

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); 
    } 
} 

Answer 2

：パディングメートルまで* 2^kが、私はあなたが値までパッドは、この関数によって計算すべきだと思う2.

次のパワーまでパディングするよりもはるかに良いを実行する必要があります私は、最小パディングを見つけるためのより簡潔なアルゴリズムを見つけたと信じています

これは、しきい値を下回るまで2を割り切れるように繰り返して動作し、次に2 **カウンタを掛けてサイズを求めますしきい値よりも小さくなるまで2で割り切れるようにするには、パッドを埋めなければならない。

unsigned int minPad(unsigned int inSize, unsigned int threshold) { 
    unsigned int counter = 0; 
    while (inSize > threshold) { 
     inSize++; 
     inSize >>= 1; 
     counter ++; 
    } 
    return inSize << counter; 
}