ΡΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ ΠΌΠ°ΡΡΠΈΡΡ Ρ ΠΊΠΎΠ΄
Π’ΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ ΠΌΠ°ΡΡΠΈΡΡ
Π’ΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°ΡΡ ΠΌΠ°ΡΡΠΈΡΡ(ΡΠ΄Π΅Π»Π°ΡΡ ΡΡΡΠΎΠΊΠΈ ΡΡΠΎΠ»Π±ΡΠ°ΠΌΠΈ)
Π’ΡΠ°Π½ΡΠΏΠΎΠ½ΡΠ²Π°ΡΠΈ ΠΌΠ°ΡΡΠΈΡΡ (Π·ΡΠΎΠ±ΠΈΡΠΈ ΡΡΠ΄ΠΊΠΈ ΡΡΠΎΠ²ΠΏΡΡΠΌΠΈ):
. 2 5 1 0
. z=0 3 2 4
. 1 2 0 3
ΠΠΎΠΌΠΎΡΡ Π² Π½Π°ΠΏΠΈΡΠ°Π½ΠΈΠΈ ΠΊΠΎΠ½ΡΡΠΎΠ»ΡΠ½ΡΡ , ΠΊΡΡΡΠΎΠ²ΡΡ ΠΈ Π΄ΠΈΠΏΠ»ΠΎΠΌΠ½ΡΡ ΡΠ°Π±ΠΎΡ Π·Π΄Π΅ΡΡ.
ΡΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ ΠΌΠ°ΡΡΠΈΡΡ
ΠΠ· ΠΊΠ²Π°Π΄ΡΠ°ΡΠ½ΠΎΠΉ ΠΌΠ°ΡΡΠΈΡΡ X ΠΏΠΎΡΡΡΠΎΠΈΡΡ ΠΌΠ°ΡΡΠΈΡΡ Y, Π·Π°ΠΌΠ΅Π½ΠΈΠ² ΡΡΡΠΎΠΊΠΈ ΡΡΠΎΠ»Π±ΡΠ°ΠΌΠΈ (ΡΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ ΠΌΠ°ΡΡΠΈΡΡ).
Π’ΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ ΠΌΠ°ΡΡΠΈΡΡ
ΠΠ²ΡΠΌΠ΅ΡΠ½ΡΠ΅ ΠΌΠ°ΡΡΠΈΠ²Ρ: 2)ΠΠ· ΠΌΠ°ΡΡΠΈΡΡ X=( xi,k) ΠΏΠΎΡΡΡΠΎΠΈΡΡ ΠΌΠ°ΡΡΠΈΡΡ Y=( yi,k), Π·Π°ΠΌΠ΅Π½ΠΈΠ² ΡΡΡΠΎΠΊΠΈ ΡΡΠΎΠ»Π±ΡΠ°ΠΌΠΈ.
Π’ΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ ΠΌΠ°ΡΡΠΈΡΡ
Π ΡΡΠ΅Π΄Π΅ MS Visual C++ ΡΠ°Π·ΡΠ°Π±ΠΎΡΠ°ΡΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ, ΠΊΠΎΡΠΎΡΠ°Ρ ΡΠΎΡΠΌΠΈΡΡΠ΅Ρ ΠΌΠ°ΡΡΠΈΡΡ ΡΠ°Π·ΠΌΠ΅ΡΠΎΠΌ n Ρ
m (Π·Π½Π°ΡΠ΅Π½ΠΈΡ n.
Π’ΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ ΠΌΠ°ΡΡΠΈΡΡ
ΠΠ°ΠΊ Π² C++ ΡΠ΄Π΅Π»Π°ΡΡ ΡΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°Π½Π½ΡΡ ΠΌΠ°ΡΡΠΈΡΡ?
Π±Π»ΡΠ½ Π½Π΅ ΡΠΎ ΡΠ΄Π°Π»ΠΈΠ» ΡΡ ΡΡΠΎ Π½Π°Π΄ΠΎ
ΠΠΎΠ±Π°Π²Π»Π΅Π½ΠΎ ΡΠ΅ΡΠ΅Π· 4 ΠΌΠΈΠ½ΡΡΡ
ΡΠΎΡΠΈΠΈΠΈ
Π’ΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ ΠΌΠ°ΡΡΠΈΡΡ
ΠΡΠΎΠ²Π΅ΡΡΡΠ΅ ΡΠ²ΠΎΠΉΡΡΠ²ΠΎ (A^T)^T = Π, Π³Π΄Π΅ A β ΠΈΡΡ
ΠΎΠ΄Π½Π°Ρ ΠΌΠ°ΡΡΠΈΡΠ° (n Ρ
n), Π’ ΠΎΠ·Π½Π°ΡΠ°Π΅Ρ ΡΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅.
Π’ΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ ΠΌΠ°ΡΡΠΈΡΡ
ΠΡΠ΅ΠΌ Π΄ΠΎΠ±ΡΠΎΠ³ΠΎ Π²ΡΠ΅ΠΌΠ΅Π½ΠΈ ΡΡΡΠΎΠΊ, Π΄ΠΎΡΠΎΠ³ΠΈΠ΅!:) ΠΠ°Π½Π°Π»ΡΠ½ΡΠΉ Π²ΠΎΠΏΡΠΎΡ ΡΠ°ΠΊΠΎΠΉ, Π½ΠΎ Π½Π΅ ΠΏΠΎΠΉΠΌΡ Π² ΡΡΠΌ Π΄Π΅Π»ΠΎ. ΠΠΈΡΡ ΡΡΡ.
Π’ΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ ΠΌΠ°ΡΡΠΈΡΡ
ΠΠ±ΡΡΡΠ½ΠΈΡΠ΅ Π³Π΄Π΅ ΠΎΡΠΈΠ±ΠΊΠ° ΠΈ ΠΊΠ°ΠΊ Π΅Π΅ ΠΈΡΠΏΡΠ°Π²ΠΈΡΡ ΠΠ°Π΄Π°Π½ΠΈΠ΅ Π½Π°ΠΏΠΈΡΠ°ΡΡ ΡΡΠ½ΠΊΡΠΈΡ ΠΏΠ΅ΡΠ΅Π²ΠΎΡΠ°ΡΠΈΠ²Π°ΡΡΠΈΠ΅ Π΄Π²ΡΠΌΠ΅ΡΠ½ΡΠΉ.
Π’ΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ ΠΌΠ°ΡΡΠΈΡΡ
ΠΠ΄ΡΠ°Π²ΡΡΠ²ΡΠΉΡΠ΅! ΠΠΈΡΡ ΡΡΠ½ΠΊΡΠΈΡ Π΄Π»Ρ ΡΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°Π½ΠΈΡ ΠΌΠ°ΡΡΠΈΡΡ. ΠΠΎΡ ΠΊΠΎΠ΄: void tran()< int n,m;.
Π’ΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ ΠΌΠ°ΡΡΠΈΡΡ
ΠΠ΄ΡΠ°Π²ΡΡΠ²ΡΠΉΡΠ΅! ΠΠ°ΠΊ ΠΏΠΎΠ²Π΅ΡΠ½ΡΡΡ Π½Π΅ ΠΊΠ²Π°Π΄ΡΠ°ΡΠ½ΡΡ ΠΌΠ°ΡΡΠΈΡΡ? Π’ΠΎ Π΅ΡΡΡ: 3 2 1 4 15 9 3 7.
Π’ΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ ΠΊΠ²Π°Π΄ΡΠ°ΡΠ½ΠΎΠΉ ΠΌΠ°ΡΡΠΈΡΡ
ΠΠΎΠΌΠΎΠ³ΠΈΡΠ΅ ΠΏΠΎΠΆΠ°Π»ΡΠΉΡΡΠ°,ΠΠ΅ΠΎΠ±Ρ ΠΎΠ΄ΠΈΠΌΠΎ Π·Π°ΠΌΠ΅Π½ΠΈΡΡ ΡΡΡΠΎΠΊΠΈ ΠΌΠ°ΡΡΠΈΡΡ Π΅Ρ ΡΡΠΎΠ»Π±ΡΠ°ΠΌΠΈ, Π° ΡΡΠΎΠ»Π±ΡΡ ΡΡΡΠΎΠΊΠ°ΠΌΠΈ. ΠΠ»Ρ ΡΡΠΎΠ³ΠΎ ΠΏΠΎΠΌΠ΅Π½ΡΡΡ ΠΌΠ΅ΡΡΠ°ΠΌΠΈ ΠΊΠ°ΠΆΠ΄ΡΠΉ ΠΊΠ°ΠΆΠ΄ΡΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ Π²Π΅ΡΡ Π½Π΅Π³ΠΎ ΡΡΠ΅ΡΠ³ΠΎΠ»ΡΠ½ΠΈΠΊΠ° ΠΌΠ°ΡΡΠΈΡΡ Ρ ΡΠΎΠΎΡΠ²Π΅ΡΡΡΠ²ΡΡΡΠΈΠΌ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠΌ Π½ΠΈΠΆΠ½Π΅Π³ΠΎ. ΠΡΡ ΠΎΠ΄Π½Π°Ρ ΠΌΠ°ΡΡΠΈΡΠ° Π·Π°Π΄Π°ΡΡΡΡ Π² Π²ΠΈΠ΄Π΅ Π΄Π²ΡΠΌΠ΅ΡΠΎΠ³ΠΎ ΠΌΠ°ΡΡΠΈΠ²Π° ΡΠ»ΡΡΠ°ΠΉΠ½ΡΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ (randomize). ΠΡΠ²Π΅ΡΡΠΈ Π½Π° ΡΠΊΡΠ°Π½ ΠΈΡΡ ΠΎΠ΄Π½ΡΡ ΠΈ ΡΠ΅Π·ΡΠ»ΡΡΠΈΡΡΡΡΡΡ ΠΌΠ°ΡΡΠΈΡΡ.
ΠΠΎΠ±Π°Π²Π»Π΅Π½ΠΎ ΡΠ΅ΡΠ΅Π· 11 ΡΠ°ΡΠΎΠ² 40 ΠΌΠΈΠ½ΡΡ
ΠΏΠΎ Π±ΡΠ°ΡΡΠΊΠΈ ΠΏΠ»ΠΈΠ·
ΠΠΎΠΌΠΎΡΡ Π² Π½Π°ΠΏΠΈΡΠ°Π½ΠΈΠΈ ΠΊΠΎΠ½ΡΡΠΎΠ»ΡΠ½ΡΡ , ΠΊΡΡΡΠΎΠ²ΡΡ ΠΈ Π΄ΠΈΠΏΠ»ΠΎΠΌΠ½ΡΡ ΡΠ°Π±ΠΎΡ Π·Π΄Π΅ΡΡ.
Π’ΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ ΠΊΠ²Π°Π΄ΡΠ°ΡΠ½ΠΎΠΉ ΠΌΠ°ΡΡΠΈΡΡ
ΠΠ°Π½Π° Π΄Π΅ΠΉΡΡΠ²ΠΈΡΠ΅Π»ΡΠ½Π°Ρ ΠΊΠ²Π°Π΄ΡΠ°ΡΠ½Π°Ρ ΠΌΠ°ΡΡΠΈΡΠ° ΠΏΠΎΡΡΠ΄ΠΊΠ° n.ΠΡΠ΅ΠΎΠ±ΡΠ°Π·ΠΎΠ²Π°ΡΡ ΠΌΠ°ΡΡΠΈΡΡ ΠΏΠΎ ΠΏΡΠ°Π²ΠΈΠ»Ρ: ΡΡΡΠΎΠΊΡ Ρ Π½ΠΎΠΌΠ΅ΡΠΎΠΌ.
ΠΡΠΏΠΎΠ»Π½ΠΈΡΡ ΡΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ ΠΊΠ²Π°Π΄ΡΠ°ΡΠ½ΠΎΠΉ ΠΌΠ°ΡΡΠΈΡΡ
ΠΠ΄ΡΠ°Π²ΡΡΠ²ΡΠΉΡΠ΅ Π΄Π°Π»ΠΈ ΡΠ°ΠΊΠΎΠ΅ Π·Π°Π΄Π°Π½ΠΈΠ΅. ΠΠ±ΡΡΠ²ΠΈΡΠ΅ Π΄Π²ΡΠΌΠ΅ΡΠ½ΡΠΉ ΡΠ΅Π»ΠΎΡΠΈΡΠ»Π΅Π½Π½ΡΠΉ ΠΌΠ°ΡΡΠΈΠ², Π² ΠΊΠΎΡΠΎΡΠΎΠΌ n ο΄ n.
Π’ΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ n ΠΌΠ΅ΡΠ½ΠΎΠΉ ΠΊΠ²Π°Π΄ΡΠ°ΡΠ½ΠΎΠΉ ΠΌΠ°ΡΡΠΈΡΡ(Π΄Π²ΡΠΌΠ΅ΡΠ½ΡΠΉ Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΈΠΉ ΠΌΠ°ΡΡΠΈΠ²)
«Π‘ΠΎΠ·Π΄Π°ΠΉΡΠ΅ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ Π΄Π»Ρ ΡΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°Π½ΠΈΡ ΠΊΠ²Π°Π΄ΡΠ°ΡΠ½ΠΎΠΉ ΠΌΠ°ΡΡΠΈΡΡ A. ΠΠ½Π°ΡΠ΅Π½ΠΈΠ΅ n Π²Π²ΠΎΠ΄ΠΈΡΡΡ Ρ ΠΊΠ»Π°Π²ΠΈΠ°ΡΡΡΡ.
ΠΠΏΠΈΡΠ°ΡΡ ΠΏΡΠΎΡΠ΅Π΄ΡΡΡ Π²ΡΠΏΠΎΠ»Π½ΡΡΡΡΡ ΡΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ ΠΊΠ²Π°Π΄ΡΠ°ΡΠ½ΠΎΠΉ Π²Π΅ΡΠ΅ΡΡΠ²Π΅Π½Π½ΠΎΠΉ ΠΌΠ°ΡΡΠΈΡΡ
ΠΠΏΠΈΡΠ°ΡΡ ΠΏΡΠΎΡΠ΅Π΄ΡΡΡ Transp(A,M), Π²ΡΠΏΠΎΠ»Π½ΡΡΡΡΡ ΡΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ ΠΊΠ²Π°Π΄ΡΠ°ΡΠ½ΠΎΠΉ Π²Π΅ΡΠ΅ΡΡΠ²Π΅Π½Π½ΠΎΠΉ ΠΌΠ°ΡΡΠΈΡΡ A.
Π’ΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°ΡΡ ΠΠ ΠΊΠ²Π°Π΄ΡΠ°ΡΠ½ΡΡ ΠΌΠ°ΡΡΠΈΡΡ
ΠΡΠΏΠΎΠ»Π½ΠΈΡΡ ΡΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ ΠΠ ΠΊΠ²Π°Π΄ΡΠ°ΡΠ½ΠΎΠΉ ΠΌΠ°ΡΡΠΈΡΡ 3 Π½Π° 5. ΠΠ°ΡΡΠΈΡΠ° Π΄ΠΎΠ»ΠΆΠ½Π° Ρ ΡΠ°Π½ΠΈΡΡΡΡ Π² ΠΏΠ°ΠΌΡΡΠΈ Π² Π²ΠΈΠ΄Π΅ Π΄Π²ΡΠΌΠ΅ΡΠ½ΠΎΠ³ΠΎ Π΄ΠΈΠ½Π°ΠΌΠΈΡΠ΅ΡΠΊΠΎΠ³ΠΎ ΠΌΠ°ΡΡΠΈΠ²Π°.
ΠΠ΅ ΠΌΠΎΠ³Ρ ΠΏΠΎΠ½ΡΡΡ ΠΊΠ°ΠΊ ΡΠ΅Π°Π»ΠΈΠ·ΠΎΠ²Π°ΡΡ ΡΡΠΎΡ Π°Π»Π³ΠΎΡΠΈΡΠΌ.
ΠΠΎΠΌΠΎΡΡ Π² Π½Π°ΠΏΠΈΡΠ°Π½ΠΈΠΈ ΠΊΠΎΠ½ΡΡΠΎΠ»ΡΠ½ΡΡ , ΠΊΡΡΡΠΎΠ²ΡΡ ΠΈ Π΄ΠΈΠΏΠ»ΠΎΠΌΠ½ΡΡ ΡΠ°Π±ΠΎΡ Π·Π΄Π΅ΡΡ.
Π‘ΡΠΎΡΠΌΠΈΡΠΎΠ²Π°ΡΡ ΠΊΠ²Π°Π΄ΡΠ°ΡΠ½ΡΡ ΠΌΠ°ΡΡΠΈΡΡ; ΡΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°ΡΡ ΠΌΠ°ΡΡΠΈΡΡ ΠΈ ΠΈΠ½Π²Π΅ΡΡΠΈΡΠΎΠ²Π°ΡΡ ΠΏΠΎΡΡΠ΄ΠΎΠΊ ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ² ΠΊΠ°ΠΆΠ΄ΠΎΠΉ Π΅Π΅ ΡΡΡΠΎΠΊΠΈ
ΠΠ°Π΄Π°Π½Ρ Π΄Π²Π° ΠΎΠ΄Π½ΠΎΠΌΠ΅ΡΠ½ΡΡ
ΠΌΠ°ΡΡΠΈΠ²Π° ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²ΠΎΠΉ Π΄Π»ΠΈΠ½Ρ: R ΠΈ S.Π‘ΡΠΎΡΠΌΠΈΡΠΎΠ²Π°ΡΡ ΠΊΠ²Π°Π΄ΡΠ°ΡΠ½ΡΡ ΠΌΠ°ΡΡΠΈΡΡ A, ΠΊΠ°ΠΆΠ΄ΡΠΉ.
Π’ΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°ΡΡ Π΄Π°Π½Π½ΡΡ Π²Π΅ΡΠ΅ΡΡΠ²Π΅Π½Π½ΡΡ ΠΊΠ²Π°Π΄ΡΠ°ΡΠ½ΡΡ ΠΌΠ°ΡΡΠΈΡΡ ΠΏΠΎΡΡΠ΄ΠΊΠ° n
ΠΠΎΠΌΠΎΠ³ΠΈΡΠ΅ ΡΡΠΎΡΠ½ΠΎ Π½ΡΠΆΠ½ΠΎ, ΠΏΠΎΠΆΠ°Π»ΡΠΉΡΡΠ°!
ΠΠ°Π΄Π°ΡΡ ΠΊΠ²Π°Π΄ΡΠ°ΡΠ½ΡΡ ΠΌΠ°ΡΡΠΈΡΡ ΠΊΠΎΠΌΠΏΠ»Π΅ΠΊΡΠ½ΡΡ
ΡΠΈΡΠ΅Π» ΠΈ ΡΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°ΡΡ Π΅Π΅
ΠΠ°Π΄Π°ΡΡ A(n*n) ΠΊΠΎΠΌΠΏΠ»Π΅ΠΊΡΠ½ΡΡ
ΡΠΈΡΠ΅Π» ΠΈ Π½Π°ΠΉΡΠΈ A^T ΠΡΠ΄Ρ ΠΎΡΠ΅Π½ Π±Π»Π°Π³ΠΎΠ΄Π°ΡΠ½Π° Π·Π° ΠΏΠΎΠΌΠΎΡΡ, Π΄Π°ΠΆΠ΅ ΡΠ°ΡΡΠΈΡΠ½ΡΡ)
Π Π΅ΡΠ΅Π½ΠΈΠ΅
Azero_Q, Π·Π΄ΡΠ°Π²ΡΡΠ²ΡΠΉΡΠ΅. ΠΠΎΡ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅:
Π‘ΠΎΠ·Π΄Π°ΡΡ ΠΊΠ²Π°Π΄ΡΠ°ΡΠ½ΡΡ ΠΌΠ°ΡΡΠΈΡΡ, ΡΡΠΎΡΠΌΠΈΡΠΎΠ²Π°ΡΡ Π½ΠΎΠ²ΡΡ ΠΌΠ°ΡΡΠΈΡΡ ΡΠ°ΠΊΠΎΠΉ ΠΆΠ΅ ΡΠ°Π·ΠΌΠ΅ΡΠ½ΠΎΡΡΠΈ ΠΏΡΡΡΠΌ ΡΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°Π½ΠΈΡ ΠΈΡΡ
ΠΎΠ΄Π½ΠΎΠΉ
Π‘ΠΎΠ·Π΄Π°ΡΡ ΠΊΠ²Π°Π΄ΡΠ°ΡΠ½ΡΡ ΠΌΠ°ΡΡΠΈΡΡ ΡΠ°Π·ΠΌΠ΅ΡΠ½ΠΎΡΡΠΈ (30, 30). ΠΠ°ΠΏΠΎΠ»Π½ΠΈΡΡ Π΅Ρ ΡΠ»ΡΡΠ°ΠΉΠ½ΡΠΌΠΈ ΡΠ΅Π»ΡΠΌΠΈ ΡΠΈΡΠ»Π°ΠΌΠΈ ΠΈΠ·.
Π’ΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°ΡΡ ΠΌΠ°ΡΡΠΈΡΡ
ΠΠ°Π½Π° ΠΌΠ°ΡΡΠΈΡΠ° n*n, Π½ΡΠΆΠ½ΠΎ ΡΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°ΡΡ Π΅Π΅. ΠΠΎΠΌΠΎΠ³ΠΈΡΠ΅ Π½Π°ΠΏΠΈΡΠ°ΡΡ ΠΊΠΎΠ΄, Π·Π°ΡΠ°Π½Π΅Π΅ ΡΠΏΠ°ΡΠΈΠ±ΠΎ!
Π’ΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°ΡΡ ΠΌΠ°ΡΡΠΈΡΡ [3][4] Π² [4][3]
ΠΠ΄ΡΠ°Π²ΡΡΠ²ΡΠΉΡΠ΅ ΠΠΎΠ΄ΡΠΊΠ°ΠΆΠΈΡΠ΅ ΠΊΠ°ΠΊ ΡΡΠ°Π½ΡΠΏΠΎΡΡΠΈΡΠΎΠ²Π°ΡΡ ΠΌΠ°ΡΡΠΈΡΡ #define SIZE1 3 #define SIZE2 4 //.
ΠΠ°ΠΊΠΎΠ² ΡΠ°ΠΌΡΠΉ Π±ΡΡΡΡΡΠΉ ΡΠΏΠΎΡΠΎΠ± ΡΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°ΡΡ ΠΌΠ°ΡΡΠΈΡΡ Π² C++?
Ρ ΠΌΠ΅Π½Ρ Π΅ΡΡΡ ΠΌΠ°ΡΡΠΈΡΠ° (ΠΎΡΠ½ΠΎΡΠΈΡΠ΅Π»ΡΠ½ΠΎ Π±ΠΎΠ»ΡΡΠ°Ρ), ΠΊΠΎΡΠΎΡΡΡ ΠΌΠ½Π΅ Π½ΡΠΆΠ½ΠΎ ΡΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°ΡΡ. ΠΠ°ΠΏΡΠΈΠΌΠ΅Ρ, ΠΏΡΠ΅Π΄ΠΏΠΎΠ»ΠΎΠΆΠΈΠΌ, ΡΡΠΎ ΠΌΠΎΡ ΠΌΠ°ΡΡΠΈΡΠ°
Π― Ρ ΠΎΡΡ, ΡΡΠΎΠ±Ρ ΡΠ΅Π·ΡΠ»ΡΡΠ°Ρ Π±ΡΠ» ΡΠ»Π΅Π΄ΡΡΡΠΈΠΌ:
ΠΊΠ°ΠΊΠΎΠΉ ΡΠ°ΠΌΡΠΉ Π±ΡΡΡΡΡΠΉ ΡΠΏΠΎΡΠΎΠ± ΡΠ΄Π΅Π»Π°ΡΡ ΡΡΠΎ?
8 ΠΎΡΠ²Π΅ΡΠΎΠ²:
ΡΡΠΎ Ρ ΠΎΡΠΎΡΠΈΠΉ Π²ΠΎΠΏΡΠΎΡ. ΠΡΡΡ ΠΌΠ½ΠΎΠ³ΠΎ ΠΏΡΠΈΡΠΈΠ½, ΠΏΠΎ ΠΊΠΎΡΠΎΡΡΠΌ Π²Ρ Ρ ΠΎΡΠ΅Π»ΠΈ Π±Ρ ΡΠ°ΠΊΡΠΈΡΠ΅ΡΠΊΠΈ ΠΏΠ΅ΡΠ΅Π½Π΅ΡΡΠΈ ΠΌΠ°ΡΡΠΈΡΡ Π² ΠΏΠ°ΠΌΡΡΡ, Π° Π½Π΅ ΠΏΡΠΎΡΡΠΎ ΠΏΠΎΠΌΠ΅Π½ΡΡΡ ΠΊΠΎΠΎΡΠ΄ΠΈΠ½Π°ΡΡ, Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, ΠΏΡΠΈ ΡΠΌΠ½ΠΎΠΆΠ΅Π½ΠΈΠΈ ΠΌΠ°ΡΡΠΈΡΡ ΠΈ ΡΠ°Π·ΠΌΠ°Π·ΡΠ²Π°Π½ΠΈΠΈ ΠΠ°ΡΡΡΠ°.
ΡΠ½Π°ΡΠ°Π»Π° ΠΏΠΎΠ·Π²ΠΎΠ»ΡΡΠ΅ ΠΌΠ½Π΅ ΠΏΠ΅ΡΠ΅ΡΠΈΡΠ»ΠΈΡΡ ΠΎΠ΄Π½Ρ ΠΈΠ· ΡΡΠ½ΠΊΡΠΈΠΉ, ΠΊΠΎΡΠΎΡΡΠ΅ Ρ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΡ Π΄Π»Ρ ΡΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°Π½ΠΈΡ (EDIT: ΠΏΠΎΠΆΠ°Π»ΡΠΉΡΡΠ°, ΡΠΌΠΎΡΡΠΈΡΠ΅ ΠΊΠΎΠ½Π΅Ρ ΠΌΠΎΠ΅Π³ΠΎ ΠΎΡΠ²Π΅ΡΠ°, Π³Π΄Π΅ Ρ Π½Π°ΡΠ΅Π» Π³ΠΎΡΠ°Π·Π΄ΠΎ Π±ΠΎΠ»Π΅Π΅ Π±ΡΡΡΡΠΎΠ΅ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅)
ΡΠ΅ΠΏΠ΅ΡΡ Π΄Π°Π²Π°ΠΉΡΠ΅ ΠΏΠΎΡΠΌΠΎΡΡΠΈΠΌ, ΠΏΠΎΡΠ΅ΠΌΡ ΡΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ ΠΏΠΎΠ»Π΅Π·Π½ΠΎ. Π Π°ΡΡΠΌΠΎΡΡΠΈΠΌ ΡΠΌΠ½ΠΎΠΆΠ΅Π½ΠΈΠ΅ ΠΌΠ°ΡΡΠΈΡΡ C = A*B. ΠΡ ΠΌΠΎΠ³Π»ΠΈ Π±Ρ ΡΠ΄Π΅Π»Π°ΡΡ ΡΡΠΎ ΡΠ°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ.
ΡΠ°ΠΊΠΈΠΌ ΠΎΠ±ΡΠ°Π·ΠΎΠΌ, ΠΎΠ΄Π½Π°ΠΊΠΎ, Π±ΡΠ΄Π΅Ρ ΠΈΠΌΠ΅ΡΡ ΠΌΠ½ΠΎΠ³ΠΎ ΠΏΡΠΎΠΌΠ°Ρ ΠΎΠ² ΠΊΡΡΠ°. ΠΠΎΡΠ°Π·Π΄ΠΎ Π±ΠΎΠ»Π΅Π΅ Π±ΡΡΡΡΠΎΠ΅ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ ΡΠΎΡΡΠΎΠΈΡ Π² ΡΠΎΠΌ, ΡΡΠΎΠ±Ρ ΡΠ½Π°ΡΠ°Π»Π° ΡΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°ΡΡ B
ΡΠΌΠ½ΠΎΠΆΠ΅Π½ΠΈΠ΅ ΠΌΠ°ΡΡΠΈΡΡ ΡΠ°Π²Π½ΠΎ O (n^3), Π° ΡΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅-O(n^2), ΠΏΠΎΡΡΠΎΠΌΡ Π²Π·ΡΡΠΈΠ΅ ΡΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°Π½ΠΈΡ Π΄ΠΎΠ»ΠΆΠ½ΠΎ ΠΈΠΌΠ΅ΡΡ Π½Π΅Π·Π½Π°ΡΠΈΡΠ΅Π»ΡΠ½ΠΎΠ΅ Π²Π»ΠΈΡΠ½ΠΈΠ΅ Π½Π° Π²ΡΠ΅ΠΌΡ Π²ΡΡΠΈΡΠ»Π΅Π½ΠΈΡ (Π΄Π»Ρ Π±ΠΎΠ»ΡΡΠΈΡ n ). Π ΡΠΈΠΊΠ»Π΅ ΡΠΌΠ½ΠΎΠΆΠ΅Π½ΠΈΡ ΠΌΠ°ΡΡΠΈΡ ΡΠ΅ΡΠ΅ΠΏΠΈΡΠ° ΠΡΠ΅ Π±ΠΎΠ»Π΅Π΅ ΡΡΡΠ΅ΠΊΡΠΈΠ²Π½Π°, ΡΠ΅ΠΌ ΠΏΡΠΈ ΡΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°Π½ΠΈΠΈ, Π½ΠΎ ΡΡΠΎ Π³ΠΎΡΠ°Π·Π΄ΠΎ ΡΠ»ΠΎΠΆΠ½Π΅Π΅.
Ρ Ρ ΠΎΡΠ΅Π» Π±Ρ Π·Π½Π°ΡΡ Π±ΠΎΠ»Π΅Π΅ Π±ΡΡΡΡΡΠΉ ΡΠΏΠΎΡΠΎΠ± ΡΠ΄Π΅Π»Π°ΡΡ ΡΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ (Edit: Ρ Π½Π°ΡΠ΅Π» Π±ΠΎΠ»Π΅Π΅ Π±ΡΡΡΡΠΎΠ΅ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅, ΡΠΌ. ΠΊΠΎΠ½Π΅Ρ ΠΌΠΎΠ΅Π³ΠΎ ΠΎΡΠ²Π΅ΡΠ°). ΠΠΎΠ³Π΄Π° Haswell / AVX2 Π²ΡΠΉΠ΄Π΅Ρ ΡΠ΅ΡΠ΅Π· Π½Π΅ΡΠΊΠΎΠ»ΡΠΊΠΎ Π½Π΅Π΄Π΅Π»Ρ, Ρ Π½Π΅Π³ΠΎ Π±ΡΠ΄Π΅Ρ ΡΡΠ½ΠΊΡΠΈΡ ΡΠ±ΠΎΡΠ°. Π― Π½Π΅ Π·Π½Π°Ρ, Π±ΡΠ΄Π΅Ρ Π»ΠΈ ΡΡΠΎ ΠΏΠΎΠ»Π΅Π·Π½ΠΎ Π² ΡΡΠΎΠΌ ΡΠ»ΡΡΠ°Π΅, Π½ΠΎ Ρ ΠΌΠΎΠ³Ρ ΠΏΡΠ΅Π΄ΡΡΠ°Π²ΠΈΡΡ ΡΠ΅Π±Π΅ ΡΠ±ΠΎΡ ΡΡΠΎΠ»Π±ΡΠ° ΠΈ Π·Π°ΠΏΠΈΡΡ ΡΡΡΠΎΠΊΠΈ. ΠΠΎΠΆΠ΅Ρ Π±ΡΡΡ, ΡΡΠΎ ΡΠ΄Π΅Π»Π°Π΅Ρ ΡΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ Π½Π΅Π½ΡΠΆΠ½ΡΠΌ.
Π΄Π»Ρ Π³Π°ΡΡΡΠΎΠ²ΡΠΊΠΎΠ³ΠΎ ΡΠ°Π·ΠΌΠ°Π·ΡΠ²Π°Π½ΠΈΡ ΡΠΎ, ΡΡΠΎ Π²Ρ Π΄Π΅Π»Π°Π΅ΡΠ΅, ΡΠ°Π·ΠΌΠ°Π·ΡΠ²Π°Π΅ΡΡΡ ΠΏΠΎ Π³ΠΎΡΠΈΠ·ΠΎΠ½ΡΠ°Π»ΠΈ, Π° Π·Π°ΡΠ΅ΠΌ ΡΠ°Π·ΠΌΠ°Π·ΡΠ²Π°Π΅ΡΡΡ ΠΏΠΎ Π²Π΅ΡΡΠΈΠΊΠ°Π»ΠΈ. ΠΠΎ ΡΠ°Π·ΠΌΠ°Π·ΡΠ²Π°Π½ΠΈΠ΅ Π²Π΅ΡΡΠΈΠΊΠ°Π»ΡΠ½ΠΎ Π΅ΡΡΡ ΠΏΡΠΎΠ±Π»Π΅ΠΌΠ° Ρ ΠΊΠ΅ΡΠ΅ΠΌ, ΡΠ°ΠΊ ΡΡΠΎ Π²Ρ Π΄Π΅Π»Π°Π΅ΡΠ΅
Π½Π°ΠΊΠΎΠ½Π΅Ρ, ΡΠΎ, ΡΡΠΎ Ρ Π½Π° ΡΠ°ΠΌΠΎΠΌ Π΄Π΅Π»Π΅ Π΄Π΅Π»Π°Ρ Π² ΠΌΠ°ΡΡΠΈΡΠ½ΠΎΠΌ ΡΠΌΠ½ΠΎΠΆΠ΅Π½ΠΈΠΈ (ΠΈ Π² Π³Π°ΡΡΡΠΎΠ²ΠΎΠΌ ΡΠ°Π·ΠΌΠ°Π·ΡΠ²Π°Π½ΠΈΠΈ), Π½Π΅ Π±Π΅ΡΠ΅Ρ ΡΠΎΡΠ½ΠΎ ΡΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅, Π° Π±Π΅ΡΠ΅Ρ ΡΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ ΠΏΠΎ ΡΠΈΡΠΈΠ½Π΅ ΠΎΠΏΡΠ΅Π΄Π΅Π»Π΅Π½Π½ΠΎΠ³ΠΎ ΡΠ°Π·ΠΌΠ΅ΡΠ° Π²Π΅ΠΊΡΠΎΡΠ° (Π½Π°ΠΏΡΠΈΠΌΠ΅Ρ, 4 ΠΈΠ»ΠΈ 8 Π΄Π»Ρ SSE/AVX). ΠΠΎΡ ΡΡΠ° ΡΡΠ½ΠΊΡΠΈΡ Π― ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΡ
EDIT:
Π΄Π»Ρ 3000×1001 ΡΡΠΎ Π²ΠΎΠ·Π²ΡΠ°ΡΠ°Π΅Ρ ldb = 3008 ΠΈ lda = 1008
Edit:
Ρ Π½Π°ΡΠ΅Π» Π΅ΡΠ΅ Π±ΠΎΠ»Π΅Π΅ Π±ΡΡΡΡΠΎΠ΅ ΡΠ΅ΡΠ΅Π½ΠΈΠ΅ Ρ ΠΏΠΎΠΌΠΎΡΡΡ SSE intrinsics:
ΠΡΠΎ Π±ΡΠ΄Π΅Ρ Π·Π°Π²ΠΈΡΠ΅ΡΡ ΠΎΡ Π²Π°ΡΠ΅Π³ΠΎ ΠΏΡΠΈΠ»ΠΎΠΆΠ΅Π½ΠΈΡ, Π½ΠΎ Π² ΡΠ΅Π»ΠΎΠΌ ΡΠ°ΠΌΡΠΉ Π±ΡΡΡΡΡΠΉ ΡΠΏΠΎΡΠΎΠ± ΡΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°ΡΡ ΠΌΠ°ΡΡΠΈΡΡ-ΡΡΠΎ ΠΈΠ½Π²Π΅ΡΡΠΈΡΠΎΠ²Π°ΡΡ Π²Π°ΡΠΈ ΠΊΠΎΠΎΡΠ΄ΠΈΠ½Π°ΡΡ, ΠΊΠΎΠ³Π΄Π° Π²Ρ ΡΠΌΠΎΡΡΠΈΡΠ΅ Π²Π²Π΅ΡΡ , ΡΠΎΠ³Π΄Π° Π²Π°ΠΌ Π½Π΅ Π½ΡΠΆΠ½ΠΎ ΡΠ°ΠΊΡΠΈΡΠ΅ΡΠΊΠΈ ΠΏΠ΅ΡΠ΅ΠΌΠ΅ΡΠ°ΡΡ ΠΊΠ°ΠΊΠΈΠ΅-Π»ΠΈΠ±ΠΎ Π΄Π°Π½Π½ΡΠ΅.
Π½Π΅ΠΊΠΎΡΠΎΡΡΠ΅ ΠΏΠΎΠ΄ΡΠΎΠ±Π½ΠΎΡΡΠΈ ΠΎ ΡΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°Π½ΠΈΠΈ 4×4 ΠΊΠ²Π°Π΄ΡΠ°ΡΠ½ΡΡ ΠΏΠΎΠΏΠ»Π°Π²ΠΊΠΎΠ²ΡΡ (Ρ Π±ΡΠ΄Ρ ΠΎΠ±ΡΡΠΆΠ΄Π°ΡΡ 32-ΡΠ°Π·ΡΡΠ΄Π½ΠΎΠ΅ ΡΠ΅Π»ΠΎΠ΅ ΡΠΈΡΠ»ΠΎ ΠΏΠΎΠ·ΠΆΠ΅) ΠΌΠ°ΡΡΠΈΡ Ρ ΠΎΠ±ΠΎΡΡΠ΄ΠΎΠ²Π°Π½ΠΈΠ΅ΠΌ x86. ΠΠΎΠ»Π΅Π·Π½ΠΎ Π½Π°ΡΠ°ΡΡ Π·Π΄Π΅ΡΡ, ΡΡΠΎΠ±Ρ ΡΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°ΡΡ Π±ΠΎΠ»ΡΡΠΈΠ΅ ΠΊΠ²Π°Π΄ΡΠ°ΡΠ½ΡΠ΅ ΠΌΠ°ΡΡΠΈΡΡ, ΡΠ°ΠΊΠΈΠ΅ ΠΊΠ°ΠΊ 8×8 ΠΈΠ»ΠΈ 16×16.
ΠΎΠ΄ΠΈΠ½ ΠΈΠ½ΡΠ΅ΡΠ΅ΡΠ½ΡΠΉ Π½Π°Π±Π»ΡΠ΄Π΅Π½ΠΈΠ΅ ΡΠΎΡΡΠΎΠΈΡ Π² ΡΠΎΠΌ, ΡΡΠΎ Π΄Π²Π΅ ΠΏΠ΅ΡΠ΅ΡΠ°ΡΠΎΠ²ΠΊΠΈ ΠΌΠΎΠ³ΡΡ Π±ΡΡΡ ΠΏΡΠ΅ΠΎΠ±ΡΠ°Π·ΠΎΠ²Π°Π½Ρ Π² ΠΎΠ΄Π½Ρ ΠΏΠ΅ΡΠ΅ΡΠ°ΡΠΎΠ²ΠΊΡ ΠΈ Π΄Π²Π΅ ΡΠΌΠ΅ΡΠΈ (SSE4.1), ΠΊΠ°ΠΊ ΡΡΠΎ.
ΡΡΠΎ ΡΡΡΠ΅ΠΊΡΠΈΠ²Π½ΠΎ ΠΏΡΠ΅ΠΎΠ±ΡΠ°Π·ΡΠ΅ΡΡΡ 4 ΠΏΠ΅ΡΠ΅ΡΠ°ΡΠΎΠ²ΠΊΠΈ Π² 2 ΠΏΠ΅ΡΠ΅ΡΠ°ΡΠΎΠ²ΠΊΠΈ ΠΈ 4 ΡΠΌΠ΅ΡΠΈ. ΠΡΠΎ ΠΈΡΠΏΠΎΠ»ΡΠ·ΡΠ΅Ρ 2 Π±ΠΎΠ»ΡΡΠ΅ ΠΈΠ½ΡΡΡΡΠΊΡΠΈΠΉ, ΡΠ΅ΠΌ ΡΠ΅Π°Π»ΠΈΠ·Π°ΡΠΈΡ GCC, ICC ΠΈ MSVC. ΠΡΠ΅ΠΈΠΌΡΡΠ΅ΡΡΠ²ΠΎ Π·Π°ΠΊΠ»ΡΡΠ°Π΅ΡΡΡ Π² ΡΠΎΠΌ, ΡΡΠΎ ΠΎΠ½ ΡΠ½ΠΈΠΆΠ°Π΅Ρ Π΄Π°Π²Π»Π΅Π½ΠΈΠ΅ Π² ΠΏΠΎΡΡΠ°Ρ , ΡΡΠΎ ΠΌΠΎΠΆΠ΅Ρ ΠΈΠΌΠ΅ΡΡ ΠΏΡΠ΅ΠΈΠΌΡΡΠ΅ΡΡΠ²ΠΎ Π² Π½Π΅ΠΊΠΎΡΠΎΡΡΡ ΠΎΠ±ΡΡΠΎΡΡΠ΅Π»ΡΡΡΠ²Π°Ρ . Π Π½Π°ΡΡΠΎΡΡΠ΅Π΅ Π²ΡΠ΅ΠΌΡ Π²ΡΠ΅ ΠΏΠ΅ΡΠ΅ΡΠ°ΡΠΎΠ²ΠΊΠΈ ΠΈ ΡΠ°ΡΠΏΠ°ΠΊΠΎΠ²ΠΊΠΈ ΠΌΠΎΠ³ΡΡ ΠΈΠ΄ΡΠΈ ΡΠΎΠ»ΡΠΊΠΎ Π² ΠΎΠ΄ΠΈΠ½ ΠΊΠΎΠ½ΠΊΡΠ΅ΡΠ½ΡΠΉ ΠΏΠΎΡΡ, ΡΠΎΠ³Π΄Π° ΠΊΠ°ΠΊ ΡΠΌΠ΅ΡΠΈ ΠΌΠΎΠ³ΡΡ ΠΈΠ΄ΡΠΈ Π² Π»ΡΠ±ΠΎΠΉ ΠΈΠ· Π΄Π²ΡΡ ΡΠ°Π·Π½ΡΡ ΠΏΠΎΡΡΠΎΠ² ΠΏΠΎΡΡΡ.
Π― ΠΏΠΎΠΏΡΡΠ°Π»ΡΡ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ 8 ΠΏΠ΅ΡΠ΅ΡΠ°ΡΠΎΠ²ΠΎΠΊ, ΡΠ°ΠΊΠΈΡ ΠΊΠ°ΠΊ MSVC, ΠΈ ΠΏΡΠ΅ΠΎΠ±ΡΠ°Π·ΠΎΠ²Π°ΡΡ ΠΈΡ Π² 4 ΠΏΠ΅ΡΠ΅ΡΠ°ΡΠΎΠ²ΠΊΠΈ + 8 ΡΠΌΠ΅ΡΠ΅ΠΉ, Π½ΠΎ ΡΡΠΎ Π½Π΅ ΡΡΠ°Π±ΠΎΡΠ°Π»ΠΎ. Π― Π²ΡΠ΅ Π΅ΡΠ΅ Π΄ΠΎΠ»ΠΆΠ΅Π½ Π±ΡΠ» ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ 4 ΡΠ°ΡΠΏΠ°ΠΊΠΎΠ²ΡΠ²Π°Π΅Ρ.
Ρ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°Π» ΡΡΡ ΠΆΠ΅ ΡΠ΅Ρ Π½ΠΈΠΊΡ Π΄Π»Ρ ΡΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°Π½ΠΈΡ ΠΏΠΎΠΏΠ»Π°Π²ΠΊΠ° 8×8 (ΡΠΌ. ΠΠ»ΠΈΠΆΠ΅ ΠΊ ΠΊΠΎΠ½ΡΡ ΡΡΠΎΠ³ΠΎ ΠΎΡΠ²Π΅ΡΠ°). https://stackoverflow.com/a/25627536/2542702. Π² ΡΡΠΎΠΌ ΠΎΡΠ²Π΅ΡΠ΅ ΠΌΠ½Π΅ Π²ΡΠ΅ Π΅ΡΠ΅ ΠΏΡΠΈΡΠ»ΠΎΡΡ ΠΈΡΠΏΠΎΠ»ΡΠ·ΠΎΠ²Π°ΡΡ 8 ΡΠ°ΡΠΏΠ°ΠΊΠΎΠ²ΠΎΠΊ, Π½ΠΎ Ρ ΡΠ΅ΡΠΈΠ» ΠΏΡΠ΅ΠΎΠ±ΡΠ°Π·ΠΎΠ²Π°ΡΡ 8 ΠΏΠ΅ΡΠ΅ΡΠ°ΡΠΎΠ²ΠΎΠΊ Π² 4 ΠΏΠ΅ΡΠ΅ΡΠ°ΡΠΎΠ²ΠΊΠΈ ΠΈ 8 ΡΠΌΠ΅ΡΠ΅ΠΉ.
Π΄Π»Ρ 32-ΡΠ°Π·ΡΡΠ΄Π½ΡΡ ΡΠ΅Π»ΡΡ ΡΠΈΡΠ΅Π» Π½Π΅Ρ Π½ΠΈΡΠ΅Π³ΠΎ ΠΊΠ°ΠΊ shufps (Π·Π° ΠΈΡΠΊΠ»ΡΡΠ΅Π½ΠΈΠ΅ΠΌ 128-Π±ΠΈΡΠ½ΡΡ ΠΏΠ΅ΡΠ΅ΡΠ°ΡΠΎΠ²ΠΎΠΊ Ρ AVX512), ΠΏΠΎΡΡΠΎΠΌΡ ΠΎΠ½ ΠΌΠΎΠΆΠ΅Ρ Π±ΡΡΡ ΡΠ΅Π°Π»ΠΈΠ·ΠΎΠ²Π°Π½ ΡΠΎΠ»ΡΠΊΠΎ Ρ ΡΠ°ΡΠΏΠ°ΠΊΠΎΠ²ΠΊΠ°ΠΌΠΈ, ΠΊΠΎΡΠΎΡΡΠ΅, ΠΊΠ°ΠΊ Ρ Π΄ΡΠΌΠ°Ρ, Π½Π΅ ΠΌΠΎΠ³ΡΡ Π±ΡΡΡ ΠΏΡΠ΅ΠΎΠ±ΡΠ°Π·ΠΎΠ²Π°Π½Ρ Π² ΡΠΌΠ΅ΡΠΈ (ΡΡΡΠ΅ΠΊΡΠΈΠ²Π½ΠΎ). Π‘ AVX512 vshufi32x4 ΡΡΡΠ΅ΠΊΡΠΈΠ²Π½ΠΎ Π΄Π΅ΠΉΡΡΠ²ΡΠ΅Ρ ΠΊΠ°ΠΊ shufps Π·Π° ΠΈΡΠΊΠ»ΡΡΠ΅Π½ΠΈΠ΅ΠΌ 128-Π±ΠΈΡΠ½ΡΡ ΠΏΠΎΠ»ΠΎΡ ΠΈΠ· 4 ΡΠ΅Π»ΡΡ ΡΠΈΡΠ΅Π» Π²ΠΌΠ΅ΡΡΠΎ 32-Π±ΠΈΡΠ½ΡΡ ΠΏΠΎΠΏΠ»Π°Π²ΠΊΠΎΠ², ΡΠ°ΠΊ ΡΡΠΎ ΡΡΠΎΡ ΠΆΠ΅ ΠΌΠ΅ΡΠΎΠ΄ ΠΌΠΎΠΆΠ΅Ρ Π±ΡΡΡ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎ Ρ vshufi32x4 Π² Π½Π΅ΠΊΠΎΡΠΎΡΡΡ ΡΠ»ΡΡΠ°ΡΡ . Π‘ ΡΡΡΠ°ΡΡΠΌΠΈ ΠΏΡΠΈΠ·Π΅ΠΌΠ»Π΅Π½ΠΈΡ ΠΏΠ΅ΡΠ΅ΡΠ°ΡΠΎΠ²ΠΊΠΈ Π² ΡΠ΅ΡΡΡΠ΅ ΡΠ°Π·Π° ΠΌΠ΅Π΄Π»Π΅Π½Π½Π΅Π΅ (ΠΏΡΠΎΠΏΡΡΠΊΠ½Π°Ρ ΡΠΏΠΎΡΠΎΠ±Π½ΠΎΡΡΡ), ΡΠ΅ΠΌ ΡΠΌΠ΅ΡΠΈ.
Π’ΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°ΡΡ ΠΌΠ°ΡΡΠΈΡΡ. ΠΡΠ²Π΅ΡΡΠΈ Π½Π° ΠΏΠ΅ΡΠ°ΡΡ Π½Π°ΡΠ°Π»ΡΠ½ΡΠΉ ΠΈ ΠΊΠΎΠ½Π΅ΡΠ½ΡΠΉ Π²Π°ΡΠΈΠ°Π½Ρ ΠΌΠ°ΡΡΠΈΡΡ
ΠΠ°Π½Π° ΠΊΠ²Π°Π΄ΡΠ°ΡΠ½Π°Ρ ΠΌΠ°ΡΡΠΈΡΠ° Π½Π°ΡΡΡΠ°Π»ΡΠ½ΡΡ ΡΠΈΡΠ΅Π», (ΠΏΠΎΠ»ΡΡΠ°Π΅ΠΌΠ°Ρ ΡΠ΅ΡΠ΅Π· rand()). Π’ΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°ΡΡ ΠΌΠ°ΡΡΠΈΡΡ. ΠΡΠ²Π΅ΡΡΠΈ Π½Π° ΠΏΠ΅ΡΠ°ΡΡ Π½Π°ΡΠ°Π»ΡΠ½ΡΠΉ ΠΈ ΠΊΠΎΠ½Π΅ΡΠ½ΡΠΉ Π²Π°ΡΠΈΠ°Π½Ρ ΠΌΠ°ΡΡΠΈΡΡ.
Π Π΅Π±ΡΡΠ° ΠΏΠΎΠΌΠΎΠ³ΠΈΡΠ΅ ΠΏΠΎΠΆΠ°Π»ΡΠΉΡΡΠ° Ρ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΠΎΠΉ
ΠΠΎΠΌΠΎΡΡ Π² Π½Π°ΠΏΠΈΡΠ°Π½ΠΈΠΈ ΠΊΠΎΠ½ΡΡΠΎΠ»ΡΠ½ΡΡ , ΠΊΡΡΡΠΎΠ²ΡΡ ΠΈ Π΄ΠΈΠΏΠ»ΠΎΠΌΠ½ΡΡ ΡΠ°Π±ΠΎΡ Π·Π΄Π΅ΡΡ.
ΠΠΎ Π²Π²Π΅Π΄Π΅Π½Π½ΠΎΠΌΡ Π½ΠΎΠΌΠ΅ΡΡ ΠΌΠ°ΡΡΡΡΡΠ° Π²ΡΠ²Π΅ΡΡΠΈ Π½Π° ΠΏΠ΅ΡΠ°ΡΡ Π²ΠΈΠ΄ ΡΡΠ°Π½ΡΠΏΠΎΡΡΠ°, Π½Π°ΡΠ°Π»ΡΠ½ΡΠΉ ΠΈ ΠΊΠΎΠ½Π΅ΡΠ½ΡΠΉ ΠΏΡΠ½ΠΊΡ ΠΌΠ°ΡΡΡΡΡΠ°
ΠΠ°ΠΏΠΈΡΠ°ΡΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ ΠΏΠΎ ΡΠΎΠ·Π΄Π°Π½ΠΈΡ ΡΠ°ΠΉΠ»Π° Π·Π°ΠΏΠΈΡΠ΅ΠΉ, ΡΠΎΠ΄Π΅ΡΠΆΠ°ΡΠΈΡ
ΡΠ²Π΅Π΄Π΅Π½ΠΈΡ ΡΠΎΠ³Π»Π°ΡΠ½ΠΎ ΡΡΠ»ΠΎΠ²ΠΈΡ Π·Π°Π΄Π°ΡΠΈ: ΠΠΎΠΌΠ΅Ρ.
ΠΡΠ΅ ΠΏΠΎΠ»ΠΎΠΆΠΈΡΠ΅Π»ΡΠ½ΡΠ΅ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ ΠΌΠ°ΡΡΠΈΡΡ A ΡΠ²Π΅Π»ΠΈΡΠΈΡΡ Π½Π° 10 ΠΈ Π²ΡΠ²Π΅ΡΡΠΈ Π½Π° ΠΏΠ΅ΡΠ°ΡΡ Π΄Π°Π½Π½ΡΡ ΠΌΠ°ΡΡΠΈΡΡ ΠΈ ΠΏΡΠ΅ΠΎΠ±ΡΠ°Π·ΠΎΠ²Π°Π½Π½ΡΡ ΠΌΠ°ΡΡΠΈΡΡ
ΠΡΠ΅ ΠΏΠΎΠ»ΠΎΠΆΠΈΡΠ΅Π»ΡΠ½ΡΠ΅ ΡΠ»Π΅ΠΌΠ΅Π½ΡΡ ΠΌΠ°ΡΡΠΈΡΡ A ΡΠ²Π΅Π»ΠΈΡΠΈΡΡ Π½Π° 10 ΠΈ Π²ΡΠ²Π΅ΡΡΠΈ Π½Π° ΠΏΠ΅ΡΠ°ΡΡ Π΄Π°Π½Π½ΡΡ ΠΌΠ°ΡΡΠΈΡΡ ΠΈ.
Π° ΠΊΠ°ΠΊ ΠΏΠΎΠ»Π½ΠΎΡΡΡΡ Π±ΡΠ΄Π΅Ρ,Ρ ΠΏΡΠΎΡΡΠΎ Π²ΠΎΠΎΠ±ΡΠ΅ Π½Π΅ ΠΏΠΎΠ½ΠΈΠΌΠ°Ρ
ΠΠΎΠ±Π°Π²Π»Π΅Π½ΠΎ ΡΠ΅ΡΠ΅Π· 7 ΡΠ°ΡΠΎΠ² 56 ΠΌΠΈΠ½ΡΡ
ΠΡΠ΅Π½Ρ Π½ΡΠΆΠ½Π° ΡΡΠ° Π·Π°Π΄Π°ΡΠ°!ΠΠΎΠΌΠΎΠ³ΠΈΡΠ΅ ΠΊΡΠΎ Π½ΠΈΠ±ΡΠ΄Ρ
Π Π΅ΡΠ΅Π½ΠΈΠ΅
ΠΠΎΡ ΠΏΡΠΈΠΌΠ΅Ρ ΠΊΠΎΠ΄Π°, ΠΊΠΎΡΠΎΡΡΠΉ Π±ΡΠ» Ρ ΠΌΠ΅Π½Ρ.
ΠΠ²Π΅ΡΡΠΈ ΠΌΠ°ΡΡΠΈΡΡ, Π·Π°ΠΌΠ΅Π½ΠΈΡΡ ΡΠ΄Π²ΠΎΠ΅Π½Π½ΡΠΌ Π·Π½Π°ΡΠ΅Π½ΠΈΠ΅ΠΌ ΠΏΠ΅ΡΠ²ΡΠΉ ΠΈ ΠΏΠΎΡΠ»Π΅Π΄Π½ΠΈΠΉ ΡΠ»Π΅ΠΌΠ΅Π½Ρ ΠΌΠ°ΡΡΠΈΡΡ, ΠΌΠ°ΡΡΠΈΡΡ Π²ΡΠ²Π΅ΡΡΠΈ Π½Π° ΠΏΠ΅ΡΠ°ΡΡ
ΠΠ²Π΅ΡΡΠΈ ΠΌΠ°ΡΡΠΈΡΡ Π(n,m) Π²Π΅ΡΠ΅ΡΡΠ²Π΅Π½Π½ΠΎΠ³ΠΎ ΡΠΈΠΏΠ° Π½Π°ΠΉΡΠΈ ΡΡΠ΅Π΄Π½Π΅Π΅ Π°ΡΠΈΡΠΌΠ΅ΡΠΈΡΠ΅ΡΠΊΠΎΠ΅ ΠΏΠΎΠ»ΠΎΠΆΠΈΡΠ΅Π»ΡΠ½ΡΡ
ΡΠ»Π΅ΠΌΠ΅Π½ΡΠΎΠ².
ΠΠ°Π½Ρ ΠΌΠ°ΡΡΠΈΡΡ Π(5,5), B(5,5). ΠΡΠ²Π΅ΡΡΠΈ Π½Π° ΠΏΠ΅ΡΠ°ΡΡ ΠΌΠ°ΡΡΠΈΡΡ 2*Π-3*B.
ΠΠ°Π½Ρ ΠΌΠ°ΡΡΠΈΡΡ Π(5,5), B(5,5). ΠΡΠ²Π΅ΡΡΠΈ Π½Π° ΠΏΠ΅ΡΠ°ΡΡ ΠΌΠ°ΡΡΠΈΡΡ 2*Π-3*B. ΠΠ°ΠΏΡΠ΅ΡΠ΅Π½ΠΎ ΡΠΎΠ·Π΄Π°Π²Π°ΡΡ ΡΠ΅ΠΌΡ Ρ.
Π’ΡΠ°Π½ΡΠΏΠΎΠ½ΠΈΡΠΎΠ²Π°ΡΡ ΠΌΠ°ΡΡΠΈΡΡ ΠΈ Π²ΡΠ²Π΅ΡΡΠΈ ΠΏΠΎΠ»ΡΡΠ΅Π½Π½ΡΡ ΠΌΠ°ΡΡΠΈΡΡ Π½Π° ΡΠΊΡΠ°Π½
1. ΠΠΎΡΡΡΠΎΠΈΡΡ ΠΌΠ°ΡΡΠΈΡΡ ΡΠ°Π·ΠΌΠ΅ΡΠΎΠΌ n Π½Π° n. ΠΠ°ΠΏΠΎΠ»Π½ΠΈΡΡ ΠΊΠ°ΠΆΠ΄ΡΡ ΡΡΡΠΎΠΊΡ ΠΌΠ°ΡΡΠΈΡΡ ΠΎΠ΄ΠΈΠ½Π°ΠΊΠΎΠ²ΡΠΌΠΈ ΡΠΈΡΠ»Π°ΠΌΠΈ, ΡΠ°Π²Π½ΡΠΌΠΈ.