Вычислить n-ую степень матрицы
Я пытаюсь оптимизировать мой код для вычисления n-й степени матрицы.
Прежде чем я просто позвоню multiplySquare n раз, но это было слишком медленно. Проблема в том, что он работает нормально, но когда я его запускаю, я получаю ошибку с выходным значением 1, Я полагаю, что мой алгоритм правильный, так что это вызывает?
n, Мне придется побольше поиграть с этим. Любая помощь будет оценена.
void multiplySquare(long long A[2][2], long long B[2][2]){
long long result[2][2];
for (int i = 0; i < 2; i++){
for (int j = 0; j < 2; j++){
result[i][j] = 0;
for (int k = 0; k < 2; k++){
result[i][j] += A[i][k] * B[k][j];
}
}
}
for (int i=0; i<2; i++){
for (int j=0; j<2; j++){
A[i][j] = result[i][j];
}
}
}
void power(long long A[2][2], long long B[2][2], long long n){
if(n/2 != 0){
power(A, B, n/2);
}
if(n%2 != 0){
multiplySquare(A, B);
}
}
Решение
Кажется, твой фрагмент — не то, к чему ты стремишься. Я предполагаю, что вы имеете в виду что-то вроде этого:
void power(long long A[2][2], long long B[2][2], long long n){
if (n == 1) {
multiplySquare(A, B);
}
else if(n % 2 == 0) {
power(A, B, n / 2);
multiplySquare(A, A);
}
else {
power(A, B, (n - 1) / 2);
multiplySquare(A, A);
multiplySquare(A, B);
}
Другие решения
Алгоритм для вычисления N-я степень числа x эффективно это:
Если N ноль, возврат 1,
Если N 1, возврат x,
вычисление (N/2)Сила y = x^(N/2)
Если N Равенство, возвращение y*y
Если N странно, возврат x*y*y
Если вы переведете эту логику в ваш случай, вам понадобится что-то вроде:
// Assuming that the result is returned in B.
void power(long long A[2][2], long long B[2][2], long long n)
{
if ( n == 0 )
{
makeIdentity(B);
return;
}
if ( n == 1 )
{
assign(A, B); // Make B same as A.
return;
}
power(A, B, n/2);
multiplySquare(B, B);
if(n % 2 != 0)
{
multiplySquare(B, A);
}
}
Я пытаюсь оптимизировать мой код для вычисления n-й степени матрицы.
Поскольку ваша цель — это оптимизация, было бы неплохо учесть, что диагональные матрицы имеют тривиальную n-ю степень, то есть n-ю степень у элементов главной диагонали.
Итак, во-первых, вы должны по диагонали матрицу. Один из способов сделать это — найти собственные векторы и собственные значения вашей исходной матрицы A и использовать следующие соотношения:
A = P D P-1
где P — матрица, содержащая (столбцы) собственных векторов A, P-1
является его обратной и D является диагональной матрицей, содержащей собственные значения.
ЗатемN = P DN п-1
Выше уравнение:
- Поднимает А в место, где восхождение к n-й степени тривиально.
- Рассчитывает n-ую степень.
- Возвращает А обратно в исходное место.
detector