бърза аритметика
Един от върховете на "аритметичната мъдрост" е таблицата за умножение. Учим го в началното училище и трябва да го помним цял живот - или вече не трябва да се доверяваме на калкулатори и компютри?
Дори най-простият калкулатор може лесно да умножи шестцифрени числа. Това е напълно достатъчно не само за домашни нужди, но и за повечето инженерни изчисления. В научните изследвания се налага да се борави с по-„дълги“ числа – с десетки и стотици десетични знаци. В нашето ежедневие обаче има области, в които се извършват аритметични операции с такива числа, въпреки че повечето хора не подозират това.
Пример е криптографията. Когато правим покупка в Интернет, ние естествено не искаме данните от банковата карта, които предаваме, да станат известни на някой друг и следователно целият обмен на информация с банката е криптиран. Много други мрежови услуги също използват защитения https протокол вместо обикновения http. Шифрите често се основават на големи прости числа.
Степента на защита на информацията пряко зависи от стойността на използваните прости числа. Преди десет години $128$-битовите (т.е. имащи 128 цифри в двоична нотация) прости числа осигуряваха достатъчна надеждност. Сега, с напредъка както на компютърните технологии, така и на математическите методи, такива кодове се "разбиват" успешно и трябва да се използват $512$- и дори $1024$-битови прости числа за надеждно криптиране.
Ясно е, че работата с големи числа е работа на компютрите. Изглежда, че не е трудно да „научим“ компютъра да прави аритметика, но за нас е важно той да ги изпълнява не само правилно, но и бързо.
От четирите операции събирането и изваждането изглеждат по-лесни от умножението и делението, но как да сравните тяхната сложност?(труд) математически? За да направите това, можете да видите как броят на извършените елементарни стъпки се увеличава с нарастването на дължината на числата, върху които се извършва действието. Една стъпка може да се счита за елементарна, ако трудността й не зависи от дължината на числата. Ще разгледаме броя на извършените елементарни стъпки като мярка за сложността на операцията.
За операцията по добавяне елементарна стъпка може да се счита за добавяне на две цифри в една цифра, като се вземе предвид прехвърлянето от предишната цифра и прехвърлянето към следващата цифра (представете си добавянето „в колона“). Броят на такива елементарни стъпки е пропорционален на дължината на добавяните числа и, да речем, ако тази дължина се удвои, сложността също се удвоява.
За операцията за умножение мярката за сложност може да се счита за броя пъти, в които се осъществява достъп до таблицата за умножение за цифри. С „училищния“ метод за умножаване на две числа „в колона“ броят на достъпите до таблицата за умножение ще бъде равен на произведението на дължините на числата (всяка цифра от първото число трябва да се умножи по всяка цифра от второто). Когато дължините на факторите се удвоят, броят на достъпите до таблицата се увеличава 4 пъти. Именно тази разлика - увеличаването на сложността с 4, а не 2 пъти - прави този алгоритъм за умножение много по-труден при работа с "дълги" числа, отколкото алгоритъма за добавяне.
Дълго време за всички беше „очевидно“, че не може да има нищо по-добро от училищния метод за умножение на многоцифрени числа. Основният аргумент беше следният: ако имаше по-бърз начин, той отдавна щеше да бъде намерен. Пълна изненада беше публикуването през 1961 г. на нов метод, открит от Анатолий Алексеевич Карацуба, който по това време беше аспирант. Този метод е толкова прост, че дори учениците могат да разкажат за него.
Нека обясним основната идея на метода Карацуба, използвайки примера за умножениедве осемцифрени числа $a$ и $b$. Нека ги представим като $$ a=10^4a_1+a_2,\quad b=10^4b_1+b_2, $$ където $a_1$, $a_2$, $b_1$, $b_2$ са четирицифрени числа. Тогава $$ a\times b= (10^4a_1+a_2)(10^4b_1+b_2)=10^8a_1b_1+10^4(a_1b_2+a_2b_1)+a_2b_2. $$Обърнете внимание, че се нуждаем от произведенията на $a_1b_2$ и $a_2b_1$ не сами по себе си, а само като сума. Тази сума може да бъде изчислена, ако вече знаем продуктите на $a_1b_1$ и $a_2b_2$, с цената само на едно допълнително умножение на две четирицифрени числа и няколко "лесни" операции събиране-изваждане, защото $$ a_1b_2+a_2b_1=a_1b_1+a_2b_2-(a_1-a_2)(b_1-b_2). $$ Ето пример за изчисление по описаната по-горе схема. Нека $$ a=63511377\quad\mbox\quad b=81026989,$$тогава $$ a_1=6351,\ a_2=1377,\quad b_1=8102,\ b2=6989. $$ Последователно изчислете: $$a_1−a_2=6351−1377=4974,$$ $$b_1−b_2=8102−6989=1113,$$ $$a_1b_1=6351\times 8102=51455802,$$ $$a_2b_2=1377\times 698 9=9623853,$$ $$(a_1−a_2)(b_1−b_2)=4974\times 1113=5536062,$$ $$a_1b_2+a_2b_1=51455802+9623853−5536062=55543593.$$ е равно на $$ 5145 580200000000 + 555435930000 + 9623853 = 5146135645553853 $$ Нека сравним сложността на новия метод със сложността на традиционния, използвайки примера за умножение на осемцифрени числа.
Когато използвате училищния метод, таблицата за умножение трябва да бъде достъпна $8\times8=64$ пъти.
При изчисленията по новия метод ще трябва да намерите три произведения на четирицифрени числа. Ако това се прави по училищния метод, тогава таблицата за умножение ще трябва да бъде достъпна $3\times 4\times 4=48$ пъти (умножаването на степен 10 е просто добавяне на нули, което не изисква достъп до таблицата).
Но в края на краищата „по нов начин“ можете да умножите четирицифрени числа, като разделите всяко от тях на дведвуцифрено число. По аналогия с примера, разгледан по-горе, за умножаване на четирицифрени числа е достатъчно да се намерят три произведения на двуцифрени числа. Ако тези продукти се изчисляват "по училищен начин", тогава ще са необходими $3\times (3\times 2 \times 2)=36$ извиквания към таблицата за умножение. Друго приложение на същата идея ще намали броя на достъпите до таблицата за умножение до $3^3=27$. В крайна сметка: пътят на изчисленията ще бъде завършен в 27 елементарни стъпки вместо в 64!
В общия случай при умножаване на две $2^m$-цифрени числа по метода на Карацуба е необходимо да се направят $3^m$ извиквания към таблицата за умножение. Следователно, когато дължината на факторите се удвои, вложеният труд се увеличава само 3 пъти, а не 4 пъти, както е при "училищния" метод. Общата печалба е толкова по-голяма, колкото по-дълги са умножените числа.
По-горе дължината на число беше измерена чрез представянето му в десетична система. При преминаване към двоично представяне дължината на числовия запис се увеличава с около $3,3$ пъти. Поради тази причина в двоичната система, в която работят съвременните компютри, предимствата на метода Карацуба се проявяват, като се започне от по-малки числа, отколкото в десетичната система. Този метод е внедрен в много програми за компютърна алгебра и осигурява големи спестявания на изчислително време.
През 1961 г. методът Карацуба е революционен пробив. След като стана ясно, че училищният метод не е оптимален, много математици се замислиха - възможно ли е да се умножават големи числа дори по-бързо от метода на Карацуба? Оказа се, че е възможно. Един от начините за ускоряване е да се раздели всеки фактор не на две части, а на по-голям (фиксиран или нарастващ с дължината на факторите) брой части.
Към днешна дата сложността на умножаването на многоцифрени числа е почти равна на сложността на събирането. А именно две $n$-цифреничислата могат да се умножават чрез извършване на $f(n) n\log n$ елементарни операции, където $f(n)$ е функция, която нараства толкова бавно с $n$, че за практически цели може да се счита за константа.
Хипотезата, че две $n$-цифрени числа не могат да бъдат умножени по-бързо от $Cn\log n$ стъпки, където $C$ е константа, се счита за правдоподобна, но досега никой не е успял да докаже това. Такива резултати, наречени долни граници (сложност на изчислението), обикновено са много по-трудни от горните граници. За да се получи горна оценка, е достатъчно да се представи конкретен алгоритъм и да се оцени неговата сложност, докато за да се получи долна оценка, е необходимо да можете да прегледате всички възможни начини за изчисляване на желаната стойност.
Читателят има право да попита - ами разделението? Възможно ли е да се разделят по-бързо, отколкото учат в училище? Оказа се, че делението не е много по-сложно от умножението. А именно, всеки метод за умножение на $n$-цифрени числа, който изисква $M(n)$ елементарни операции, може да бъде преобразуван в метод за деление на числа с еднаква дължина с $5 M(n)$ операции.
Изненадващо, изучаването на такъв древен проблем като умножаването на числа все още продължава - последното подобрение е получено през 2014 г.
Кога математиците "ще получат моралното право" повече да не се опитват да подобрят алгоритъма за умножение? Тогава, когато получените горна и долна оценка действително съвпадат, т.е. те ще се различават само с постоянен фактор. Това ще означава, че значително по-нататъшно ускоряване вече не е възможно.
Добавяне за заинтересования читател. Сред основните аритметични операции има прости - събиране и изваждане (това вече беше обсъдено), вече се научихме как бързо да умножаваме. За пълнота даваме схематично описание на споменатото "бързо" разделение.
Необходимо е да се прави разлика между двеситуации:
- деление на едно цяло число на друго за получаване на непълно частно и остатък;
- получаване на приблизителна стойност на отношението на две числа, цели или десетични.
Тук разглеждаме втората ситуация.
Нека започнем, като отбележим, че общата операция за намиране на частното $c=a/b$ може да се сведе до специален случай - намиране на реципрочната стойност на $d=1/b$. След това в резултат на (бързо) умножение се получава желаният отговор: $c=a\times d$.
Намирането на обратното на $b$ означава: решаване на уравнението $by=1$.
Да приемем, че е избрано първоначалното приближение — числото $y_0$, приблизително равно на решението на това уравнение. Ще видим колко точно е това приближение, когато изчислим произведението $b\times y_0$. Трябва да е близо до 1, което може да бъде представено с формулата $$ b\times y_0=1-\varepsilon, $$, където $\varepsilon$ е някакво число с малка абсолютна стойност.
Умножавайки двете страни на това равенство по $1+\varepsilon$, получаваме $$ b\times y_0\times (1+\varepsilon)=1-\smash. $$Това равенство може да се тълкува по следния начин: ако $\varepsilon$$ y_1=y_0\times (1+\varepsilon) $$ е по-добро приближение до $1/b$ от $y_0$, защото $\varepsilon^2
Обърнете внимание, че за да изчислим $y_1$, не е необходимо първо да намерим $\varepsilon$, може да се изчисли ново приближение с помощта на формулата $$ y_=y_0\times(2-b\times y_0). $$ Процесът на подобряване на приближението може да бъде продължен чрез последователно изчисляване на $$ \eqalign< y_2 &=y_1\times(2-b\times y_1),\cr y_3 &=y_2\times(2-b\times y_2)\cr > $$ и т.н. Лесно е да проверите, че $$ b \times y_k=1-\smash>, $$, така че наистина получавате все по-добри и по-добри приближения на $1/b$.
Ето числен пример за такава итерацияизчисления. Нека $$ b=2.8062865 $$ и е избрано първоначалното приближение $y_0=04$. Последователно намиране: $$ \eqalign< y_1 &=040\times(2-28\times040)=03520,\cr y_2 &=03520\times(2-2806\times03520)=0356325376,\cr y_3 &=035632538\times(2-28062865\time s0 35632538)=035634280…\cr> $$ Само три итерации и получихме 8 правилни цифри от числото $1/b$.
Моля, обърнете внимание, че в първата стъпка бяха използвани само 2 значими цифри от $b$ и $y_0$, във втората стъпка бяха използвани само 4 значими цифри от $b$ и $y_1$ и само в третата стъпка изчисленията бяха извършени с осемцифрени числа. Не се изисква голяма прецизност в началните стъпки, дължината на използваните там числа трябва да съответства на точността на получените приближения. В резултат на това сложността на последната стъпка в такъв итеративен процес се оказва по-голяма от сложността на всички предишни стъпки, взети заедно. Така работата по намиране на частното $a/b$ с $n$ знаци се оказва не по-трудна от 5 умножения на $n$-цифрени числа.
По същия начин се извършва бързото деление на цели числа с остатък.
По аналогия с описаното по-горе, читателят вече може независимо да намали решението на уравнението $by^2$=1 до поредица от умножения. Умножаването на полученото решение по $b$ дава, както е лесно за разбиране, $\sqrt$.