Algorytm Strassena

0

Witam, szukłem w internecie pseudokodu alogrtmu strassena i nigdzie nie mogłem znaleźć. Dlatego postanowiłem poprosić Was o pomoc. Czy poniższy pseudokod jest poprawny dla tego algorytmu? Dodam tylko, że notacja A[1,1] oznacza element macierzy a A[1,2][4,5] oznacza podmacierz macierzy A skladajaca sie z elementow: A[1,4] A[2,4] A[1,5] i A[2,5].

Strassen-multiply(A,B)
	n=A.length
	if n ==2{
            S1 = B[1,2]-B[2,2]
            S2 = A[1,1]+A[1,2]
            S3 = A[2,1]+A[2,2]
            S4 = B[2,1]-B[1,1]
            S5 = A[1,1]+A[2,2]
            S6 = B[1,1]+B[2,2]
            S7 = A[1,2]+A[2,2]
            S8 = B[2,1]+B[2,2]
            S9 = A[1,1]-A[2,1]
            S10= B[1,1]+B[1,2]

            P1 = A[1,1]*S1
            .....
            P7 = S9*S10
            C[1,1] = P5 +P4 - P2 +P6
            ....
            C[2,2] = P5 +P1 -P3 - P7
            return C
        }
        else{
            S1 = B[1,n/2][n/2+1,n]-B[n/2,n/2][n,n]
            S2 = A[1,n/2][1,n/2]+A[1,n/2][1,n/2]
            S3 = A[n/2,n][1,n/2]+A[n/2,n][n/2,n]
            ....
            P1 = Strassen-multiply(A[1,n/2][1,n/2],S1)
            ....
            P7 = S9*S10
            C[1,n/2][1,n/2] = P5 + P4 -P2 + P3
            ....
            return C
        }

0

Masz na wikipedii gotowy algorytm. W tym twoim pseudokodzie wypisanym w jednej linijce prawie nic nie widać. Podziel go na wiersze i porównaj z tym na wikipedii.

Tak swoją drogą, w dzisiejszych czasach, będzie szybszy jedynie w przypadku dużych macierzy kwadratowych.

1 użytkowników online, w tym zalogowanych: 0, gości: 1