Ədədlərin vurulması insanların gündəlik həyatında ən sadə riyazi əməliyyatlardan biri kimi görünsə də, bu proses kompüter elmi və müasir texnologiyalar üçün hələ də böyük əhəmiyyət daşıyır. Şifrələmə sistemlərindən süni intellektə, maliyyə hesablamalarından kosmik tədqiqatlara qədər bir çox sahədə çox böyük ədədlərin dəfələrlə vurulması tələb olunur. Buna görə də riyaziyyatçılar və kompüter alimləri uzun illərdir bu əməliyyatı daha sürətli yerinə yetirməyin yollarını araşdırırlar.
“Tehsil365” xəbər verir ki, ibtidai məktəbdə öyrəndiyimiz klassik vurma üsulu minilliklər boyu dəyişmədən istifadə olunub. Bu üsulda bir ədəd digərinin altına yazılır və hər rəqəm qarşı tərəfdəki bütün rəqəmlərlə vurulur. Sadə görünən bu metod kiçik ədədlər üçün kifayət qədər effektiv olsa da, ədədlərin ölçüsü artdıqca hesablamaların sayı sürətlə çoxalır.
İki rəqəmli iki ədəd vurulduqda dörd əsas vurma əməliyyatı aparılır. Üçrəqəmli ədədlərdə bu rəqəm doqquza, dördrəqəmli ədədlərdə isə on altıya yüksəlir. Başqa sözlə, tələb olunan hesablamaların sayı rəqəmlərin sayının kvadratı ilə artır. Kompüter elmində bu artım tempi Böyük O (Big O) notasiyası ilə O(n²) kimi ifadə olunur. Bu isə o deməkdir ki, ədədlərin uzunluğu iki dəfə artdıqda hesablama yükü təxminən dörd dəfə çoxalır.
Uzun illər riyaziyyatçılar hesab edirdilər ki, O(n²) sərhədini keçmək mümkün deyil. Məşhur sovet riyaziyyatçısı Andrey Kolmoqorov da bu fikri 1960-cı ildə Moskva Dövlət Universitetində keçirilən seminarda rəsmi fərziyyə kimi irəli sürüb. Lakin bu fərziyyə gözlənilməz şəkildə cəmi bir həftə sonra təkzib edilib.
Seminarda iştirak edən 23 yaşlı tələbə Anatoli Karatsuba ənənəvi vurma üsulundan daha sürətli alqoritm hazırladığını Kolmoqorova təqdim edib. Gənc alimin nəticələri o qədər təsirli idi ki, Kolmoqorov onun sübutunu özü yazaraq Karatsubanı məqalənin birinci müəllifi kimi SSRİ Elmlər Akademiyasının jurnalına göndərib. Maraqlıdır ki, Karatsuba məqalənin dərc olunduğunu yalnız jurnalın çap nüsxəsini aldıqdan sonra öyrənib.
Karatsubanın əsas ideyası vurma əməliyyatlarının sayını azaltmaq idi. Ənənəvi üsul iki hissəyə ayrılmış ədədlərin hasilini hesablamaq üçün dörd vurma əməliyyatı tələb edib.. Karatsuba isə xüsusi cəbr çevrilməsindən istifadə edərək həmin nəticəni cəmi üç vurma əməliyyatı ilə əldə etməyin mümkün olduğunu göstərdi. Əvəzində isə daha sürətli yerinə yetirilən toplama və çıxma əməliyyatlarından istifadə edilirdi.
Bu yanaşma kiçik ədədlər üçün ciddi üstünlük yaratmasa da, milyonlarla və milyardlarla rəqəmdən ibarət ədədlərlə işləyərkən böyük fərq yaradır. Məsələn, klassik üsul minrəqəmli iki ədəd üçün təxminən bir milyon elementar vurma əməliyyatı tələb etdiyi halda, Karatsuba alqoritmi eyni hesablamanı təxminən 57 min vurma əməliyyatı ilə yerinə yetirə bilir. Bu səbəbdən onun alqoritminin mürəkkəbliyi O(n¹·⁵⁸⁵) kimi qiymətləndirilir və bu göstərici klassik üsuldan xeyli daha səmərəlidir.
Karatsuba alqoritmi bu gün də bir çox proqramlaşdırma dillərində və riyazi kitabxanalarda istifadə olunur. Məsələn, Python proqramlaşdırma dili kiçik tam ədədləri vurarkən klassik məktəb üsulundan istifadə edir. Lakin hesablamalara daxil olan ədədlər müəyyən həddi keçdikdə sistem avtomatik olaraq Karatsuba alqoritminə keçir. Bunun səbəbi ondan ibarətdir ki, alqoritmin özü də əlavə bölmə və birləşdirmə əməliyyatları tələb etdiyindən yalnız böyük ədədlər üçün üstünlük verir.
Karatsubanın kəşfi yeni və daha sürətli vurma alqoritmlərinin hazırlanmasına təkan verdi. Sonrakı onilliklərdə müxtəlif metodlar təklif olunsa da, ən mühüm nəticələrdən biri 2019-cu ildə əldə edildi. Riyaziyyatçılar David Harvey və Joris van der Hoeven çox böyük ədədlər üçün nəzəri baxımdan daha sürətli işləyən yeni vurma alqoritmi təqdim etdilər. Bu metodun hesablama mürəkkəbliyi təxminən O(n log n) səviyyəsindədir və hazırda məlum olan ən sürətli nəzəri yanaşma hesab olunur.
Bununla belə, yeni alqoritmin praktik tətbiqində ciddi məhdudiyyət mövcuddur. O, yalnız təsəvvür edilməyəcək qədər böyük ədədlərlə işləyərkən üstünlük qazandığından gündəlik proqramlaşdırma və adi kompüter hesablamalarında istifadə edilmir. Kompüter alimləri belə alqoritmləri "qalaktik alqoritmlər" adlandırırlar. Çünki onların nəzəri üstünlükləri yalnız real həyatda rast gəlinməyəcək qədər böyük məlumatlar üzərində özünü göstərir.
Bu gün riyaziyyatçılar hesab edirlər ki, O(n log n) vurma əməliyyatı üçün mümkün olan ən aşağı mürəkkəblik həddi ola bilər. Lakin bunu qəti şəkildə sübut edən heç bir nəzəri nəticə yoxdur. Bu səbəbdən "ədədləri vurmağın ən sürətli mümkün üsulu hansıdır?" sualı riyaziyyat və kompüter elminin hələ də açıq qalan fundamental problemlərindən biri hesab olunur. Gələcəkdə bu sahədə əldə ediləcək yeni kəşflər təkcə nəzəri riyaziyyatı deyil, həm də süni intellektdən kibertəhlükəsizliyə qədər bir çox texnologiyanın inkişaf sürətini müəyyən edə bilər.