Ko'paytirish 2!
Ikkita butun sonni ko'paytirish algaritmi haqida gaplashgan edik. Endi matritsalar uchun shu masalani qarab chiqamiz:
Bizga A va B - n×n matritsalar berilgan bo'lsin. Bilamizki A×B ni topish uchun ularning elementlari ustida jami n³ marta ko'paytirish amalini bajarishimiz kerak. Bu esa n 1 ga oshganda ko'paytirish amallari soni 3n²+3n+1 ga oshadi degani (n 2 marta oshganda ko'paytirish amallari soni 8 marta oshadi!)
Yuqoridagidan, n=2 da A×B ni topish uchun 8 ta ko'paytirish amali bajarishimiz kerakligini ko'rishimiz mumkin. Buni 1969 yilda 7 ta amalga tushirishgan, va 1970 yilda ko'paytirishlar sonini 6 va undan kamiga tushirish mumkin emasligi isbotlangan. Bitta kamayganini nima axamiyati bor deysizmi? n=8 da A va B ni 2×2 lik blok matritsalarga ajratib, keyin A×B ni yangi algaritmni ketma-ket 3 marta qo'llash orqali 7³ yoki 343 marta ko'paytirish amali orqali topishimiz mumkinligi kelib chiqadi. Odatiy usulda esa 8³ yoki 512 ta amal edi. Demak ~33% kam ko'paytirish amalini bajaramiz.
TTT
Ikkita butun sonni ko'paytirish algaritmi haqida gaplashgan edik. Endi matritsalar uchun shu masalani qarab chiqamiz:
Bizga A va B - n×n matritsalar berilgan bo'lsin. Bilamizki A×B ni topish uchun ularning elementlari ustida jami n³ marta ko'paytirish amalini bajarishimiz kerak. Bu esa n 1 ga oshganda ko'paytirish amallari soni 3n²+3n+1 ga oshadi degani (n 2 marta oshganda ko'paytirish amallari soni 8 marta oshadi!)
Yuqoridagidan, n=2 da A×B ni topish uchun 8 ta ko'paytirish amali bajarishimiz kerakligini ko'rishimiz mumkin. Buni 1969 yilda 7 ta amalga tushirishgan, va 1970 yilda ko'paytirishlar sonini 6 va undan kamiga tushirish mumkin emasligi isbotlangan. Bitta kamayganini nima axamiyati bor deysizmi? n=8 da A va B ni 2×2 lik blok matritsalarga ajratib, keyin A×B ni yangi algaritmni ketma-ket 3 marta qo'llash orqali 7³ yoki 343 marta ko'paytirish amali orqali topishimiz mumkinligi kelib chiqadi. Odatiy usulda esa 8³ yoki 512 ta amal edi. Demak ~33% kam ko'paytirish amalini bajaramiz.
TTT