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?
source to share
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);
}
}
source to share
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;
}
source to share