оптимизированное статическое заполнение для нечетных матриц Штрассена

Question

Я пытаюсь решить проблему нечетных матриц для алгоритма Штрассена. Моя реализация обрезает рекурсию в определенной точке, называет ее Q и переключается на стандартную реализацию. Поэтому, выполняя статическое заполнение, мне на самом деле не нужно дополнять до следующей степени 2. Мне просто нужно заполнить до наименьшего значения m * 2 ^ k больше, чем размер входной матрицы, так что m У меня возникли проблемы с реализацией этого - главным образом потому, что я не уверен, что будет наиболее эффективным. Нужно ли циклически проходить все возможные значения m или увеличивать с каждого заданного входа, проверяя, соответствуют ли они критериям?

Answer 1

Используя вышесказанное в качестве вдохновения, я считаю, что нашел более сжатый алгоритм для поиска минимального заполнения

Он работает, многократно делая число, делимое на 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;
}

Answer 2

Вы правы. Заполнение до 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);
    }
}