Optimized static padding for stratified odd matrices

I am trying to solve the odd matrix problem for the strassen algorithm. My implementation truncates the recursion at some point, calls it Q, and switches to the standard implementation. So when doing static fill I don't need to gain up to next cardinality 2. I just need to minimize m * 2 ^ k larger than the size of the input matrix, so m <Question.

I have some problems implementing this - mainly because I'm not sure which would be most efficient. Do I need to iterate over all possible values ​​of m, or am I incrementing from each given input, checking if they meet the criteria?

+3


source to share


2 answers


You're right. Filling up to m * 2 ^ k should perform much better than filling up to the next power of 2.

I think you should be flipping the value calculated with this function:



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

      

0


source


Using the above as inspiration, I believe I have found a more concise algorithm for finding the minimal complement

It works by repeating a number that is divisible by 2 until it is below a threshold, then multiplying it by 2 ** a counter to get the size to which the matrix must be added to be multiple divisible by two until will be less than the threshold



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

      

0


source







All Articles