c - 斯特拉森奇数矩阵的优化静态填充

Question

我正在尝试解决 strassen 算法的奇数矩阵问题。我的实现在某个点截断递归，称之为 Q，然后切换到标准实现。因此，在进行静态填充时，我实际上不需要填充到 2 的下一个幂。我只需要填充到比输入矩阵维度大的最小 m*2^k，使得 m < Q。

我在实现这一点时遇到了一些麻烦——主要是因为我不确定什么是最有效的。我需要遍历所有可能的 m 值，还是从每个给定的输入中递增，测试它们是否满足标准？

Answer 1

你是对的。填充到 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);
    }
}

Answer 2

以上述为灵感，我相信已经找到了一种更简洁的算法来找到最小填充

它的工作原理是重复使数字可被 2 整除，直到低于阈值，然后将其乘以 2**counter 以获得矩阵必须填充到的大小，以便重复被 2 整除，直到它小于临界点

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