Изменения

Перейти к: навигация, поиск

Метод четырёх русских для умножения матриц

26 байт убрано, 07:00, 22 декабря 2011
Нет описания правки
a[i][j] = cur;
}
// Чтение матриц
for i := 0 to n - 1
for j := 0 to n - 1 {
// Предподсчёт скалярных произведений
// Пусть precalcpreСalc[i][j] - "скалярное произведение для битовых представлений" чисел i и j // "&" - битовый and; "<<**" - битовый сдвиг влевовозведение в степень.
int k = ceil(log2(n)); //округление вверх
for i := 0 to (1 << 2 ** k) - 1 for j := 0 to (1 << 2 ** k) - 1 { int scalmul scalMul = 0;
for pos := 0 to k - 1
if (((1 << 2 ** pos) & i) != 0 and ((1 << 2 ** pos) & j) != 0) { scalmul scalMul = (scalmul scalMul + 1) mod 2;
}
precalcpreСalc[i][j] = scalmulscalMul;
}
for i := 0 to n - 1 {
while (start < n) {
int cursuma curSumA = 0, cursumb curSumB = 0, curpos curPos = start, deg = (1 << 2 ** (k - 1)); while (curpos curPos < start + k and curpos curPos < n) { cursuma curSumA = cursuma curSumA + a[i][curposcurPos] * deg; cursumb curSumB = cursumb curSumB + b[curposcurPos][i] * deg;
deg = deg div 2;
curpos curPos = curpos curPos + 1;
}
anew[i][start div k] = cursumacurSumA; bnew[start div k][i] = cursumbcurSumB;
start = start + k;
}
for i := 0 to n - 1
for j := 0 to n - 1 {
int curans curAns = 0;
for pos := 0 to m - 1 {
curans curAns = (curans curAns + precalcpreСalc[anew[i][pos]][bnew[pos][j]]) mod 2;
}
ans[i][j] = curanscurAns;
}
Анонимный участник

Навигация