Ən sürətli vurma alqoritmlərindən biri. Karatsuba metodu

Ens.az saytı maraqlı hesablama metodlarının kolleksiyasından birini təqdim edir...

İnsanlarımızın hər biri üçün ənənəvi və ən sadə vurma metodu  -  "sütunla" vurma üsuludur.  Məktəbdə bizə onu öyrədirlər və insandan bir az beyin gərginliyi tələb edən digər üsullara çox əhəmiyyət vermədən onunla həyatı yaşayırıq. Onun  necə işlədiyinə baxaq ...

 Bu gün sonsuz və geniş şəbəkədə  əvvəllər heç görmədiyimiz bir şeyə rast gələ bilirik.

 Bu metod riyaziyyat tarixində böyük  sayların sürətli vurulmasının ilk metodu hesab olunur və Sovet və Rus riyaziyyatçısı Anatoli Alekseyeviç Karatsuba tərəfindən 1960-cı ildə hazırlanmışdır.

 O zamanlar, hələ 23 yaşı olan Karatsuba XX əsrin ən böyük riyaziyyatçısı olan  Andrey Nikolay Kolmaqorovun seminarına qatılıb. Kolmaqorov,  n ^ 2 əməliyatından az olan vurma üsulu olmadığını bildirib.

 Harada n - vurulan saylarda rəqəmlərin miqdarıdır. Nümunə üçün, 4-rəqəmli sayların vurulması vaxtı 16 əməliyyat tələb olunur. 

 Anatoli Alekseyev bir həftə boyunca beynini işlətdi və tamamilə yeni bir üsul tapdı.

 Onun mahiyyəti bir rəqəmin saylarının  bölünməsində və müəyyən bir şəkildə yenidən birləşməsindədir.  Ən asan yol bunu bir nümunə ilə göstərməkdir!

1, 2 və 3 -cü addım

 Sayları rəqəmlərə bölürük və  sonra onları onlara,  vahidləri vahidlərə vururuq .

4-cü və 5-ci addım

 Əvvəlcə, birinci sayın rəqəmlərini, sonra ikinci sayın rəqəmlərini əlavə edirik . Və sonda  öz aralarında alınmış cəmləri vururuq.

 6-cı addım

 5-ci addımda əldə etdiyimiz rəqəmdən  2 və 3-cü addımda aldığımız rəqəmi çıxırıq.

 _{Ümid edirik haradan gəldiyi aydın olur}

 7-ci addım

 "Adım 2" + "Adım 6" + "Adım 3" - bu şəkildə  rəqəmləri əlavə edirik.

 _{Dəyişikliyə diqqət yetirin!  Tam olaraq yazdığımız qaydada əlavə etməlisiniz.}

 Düzünü desəm, bu həll etdiyim ilk nümunədir  və ilk dəfədən hər şey alındı!

 Təəccüblü deyil ki, məktəbdə bu barədə danışmırlar.  Burada əməliyyatları təsvir etməlisiniz və bu  "sütun" üsulu qədər rahat deyil ...

 Əsaslandırılmış şəkildə  sual verə bilərsiniz:

 Burada sürət haradadır?

 Hər şey alqoritmlər və əməliyyatın sadəliyi ilə bağlıdır.  Məsələn, 4 rəqəmli ədədin sütun vurulmasında - 16 vurma əməliyyatı varsa, bu üsulda cəmi  9 əməliyyat var . Bir çox vurma əməliyyatı  bu üsulda toplama və çıxma əməliyyatları ilə əvəz olunur, hesablama üçün çox asandır, burada toplama və çıxma vurulma ilə müqayisədə daha sürətli olur, ən azından əvvəl belə idi.

 _{4 rəqəmli ədədlərin vurulması}

 Əslində Karatsuba sürətli alqoritmlər nəzəriyyəsinin əsasını qoydu.  İndi bu, ən sürətli alqoritm deyil, daha sürətli olanları da var. 

 60 il əvvəl bu metod ən sürətli sayılırdı, amma indi yazdığımız kimi daha sürətli metodlar var ...

 İstədiyiniz vurma üsulundan istifadə edin! "Sütun"un  daha asan olduğunu bilirəm!  Ən yaxşısı, bunu kalkulyatorda etməkdir!

Mənbə: zen.yandex.az