Yiren Lu - 7 months ago 38

C Question

I'm trying to address the issue of odd matrices for strassen's algorithm. My implementation truncates the recursion at a certain point, call it Q, and switches over to the standard implementation. Therefore in doing static padding, I don't actually need to pad up to the next power of 2. I just need to pad up to the least m*2^k greater than the input matrix dimension such that m < Q.

I'm having some trouble implementing this - mainly because I'm not sure what would be most efficient. Do I need to loop through all possible m values, or do I increment from each given input, testing if they fulfill the criteria?

Answer

You are correct. Padding up to m * 2^k should perform much better than padding up to next power of 2.

I think you should pad up to value calculated by 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 (Stackoverflow)