c - Strassen 奇数矩阵的优化静态填充

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