В.Б. Алексеев - Введение в теорию сложности алгоритмов (1158872), страница 3
Текст из файла (страница 3)
. ··=2 2 22n!2n−12n−1 (2n − 2)!· (1 · 3 · 5 · . . . · (2n − 3)) ==n!n!(2 · 4 · 6 · · · · · (2n − 2))2n−1 (2n − 2)!1 n−1= C2n−2.n−1n!2 (n − 1)! nÒåîðåìà äîêàçàíà.Çàìå÷àíèå. Äëÿ ïîëíîé ñòðîãîñòè â äîêàçàòåëüñòâå íóæíî îáñóäèòü ñóùåñòâîâàíèå ôóíêöèè f (x), çàäàííîé ðàâåíñòâîì (2.1). Ìîæíîïîêàçàòü, ÷òî ðÿä ñïðàâà ñõîäèòñÿ, íàïðèìåð, ïðè 0 6 x 6 41 .Ðàñêðûâàÿ ôàêòîðèàëû ïî ôîðìóëå Ñòèðëèíãà, ëåãêî ïîëó÷èòü,mm÷òî C2m∼ √4πm , òî åñòü an ðàñòåò ýêñïîíåíöèàëüíî ñ ðîñòîì n.
Ñëåäîâàòåëüíî ïåðåáîðíûé àëãîðèòì èìååò ýêñïîíåíöèàëüíóþ ñëîæíîñòü.Òåîðåìà 2.2. Äëÿ íàõîæäåíèÿ îïòèìàëüíîãî ïîðÿäêà óìíîæåíèÿnìàòðèö ñóùåñòâóåò àëãîðèòì (òèïà äèíàìè÷åñêîãî ïðîãðàì-11ìèðîâàíèÿ) ñ ÷èñëîì îïåðàöèé (àðèôìåòè÷åñêèõ è ñðàâíåíèé ÷èñåë)O(n3 ).Ïóñòü íà âõîä ïîñòóïàåò íàáîð ÷èñåë(m0 , m1 , . . . , mn ). Ââåäåì òàêèå ïîäçàäà÷è Bij : íàéòè îïòèìàëüíûéïîðÿäîê âû÷èñëåíèé è íàèìåíüøåå ÷èñëî kij óìíîæåíèé ýëåìåíòîâ äëÿïðîèçâåäåíèÿ Ai × Ai+1 × . . . × Aj , (1 6 i 6 j 6 n). Î÷åâèäíî, kii = 0äëÿ âñåõ i, è îáùåå ÷èñëî ïîäçàäà÷ Bij åñòü O(n2 ).Äîêàçàòåëüñòâî.Óòâåðæäåíèå.
Åñëè1 6 i < j 6 n,òîkij = min{ki,s + ks+1,j + mi−1 ms mj },(2.2)s òàêèì, ÷òî i 6 s 6 j − 1.Äîêàçàòåëüñòâî. Åñëè ïîñëåäíÿÿ îïåðàöèÿ óìíîæåíèÿ äåëèò ïðîèçâåäåíèå Ai · Ai+1 · . . . · Aj íà 2 ïðîèçâåäåíèÿ (Ai · . . . · As ) · (As+1 · . . . · Aj ),òî äëÿ ïîëó÷åíèÿ ìèíèìàëüíîãî ÷èñëà îïåðàöèé íàäî èñïîëüçîâàòü ìèíèìàëüíîå ÷èñëî îïåðàöèé â îáåèõ ñêîáêàõ, òî åñòü âñåãî ki,s + ks+1,jîïåðàöèé. Ïîñëå âû÷èñëåíèÿ ýòèõ ïðîèçâåäåíèé íàäî åùå ïåðåìíîæèòü 2ìàòðèöû ðàçìåðîâ mi−1 ×ms è ms ×mj .
Ïîëó÷àåì îáùåå ÷èñëî îïåðàöèé,ñòîÿùåå â (2.2) â ôèãóðíûõ ñêîáêàõ. Òåïåðü îñòàåòñÿ çàìåòèòü, ÷òî äëÿìèíèìèçàöèè îáùåãî ÷èñëà óìíîæåíèé äîñòàòî÷íî ïåðåáîðîì âûáðàòüîïòèìàëüíîå ìåñòî äëÿ ïîñëåäíåé îïåðàöèè. Óòâåðæäåíèå äîêàçàíî.Áóäåì ðåøàòü ïîäçàäà÷è Bij ÿðóñàìè, îòíîñÿ ê ÿðóñó t âñå ïîäçàäà÷è ñ j − i = t.
Ðàññìîòðèì ïîñëåäîâàòåëüíî t = 0, 1, 2, . . . , n − 1.Ïðè t = 0 ïîëó÷èì ïîäçàäà÷è Bii , äëÿ êîòîðûõ kii = 0 è ñêîáêè âîîáùåíå íàäî ðàññòàâëÿòü. Ïðè ðåøåíèè î÷åðåäíîé çàäà÷è Bij ñ j − i = tâîñïîëüçóåìñÿ óòâåðæäåíèåì. Ïðè ýòîì ëåãêî âèäåòü, ÷òî ñïðàâà â (2.2)áóäóò èñïîëüçîâàòüñÿ ðåçóëüòàòû ïîäçàäà÷ ÿðóñîâ t1 < t, êîòîðûå óæåðåøåíû.
Òîãäà äëÿ âû÷èñëåíèÿ kij ïî ôîðìóëå (2.2) äîñòàòî÷íî ñäåëàòü2(j − i) óìíîæåíèé, 2(j − i) ñëîæåíèé è j − i − 1 ñðàâíåíèé. Îáùåå÷èñëî îïåðàöèé äëÿ âû÷èñëåíèÿ îäíîãî kij íå ïðåâîñõîäèò O(n), à äëÿâû÷èñëåíèÿ âñåõ kij íå ïðåâîñõîäèò O(n3 ) (ïîñêîëüêó îáùåå ÷èñëîïîäçàäà÷ Bij åñòü O(n2 )). Ïðè âû÷èñëåíèè kij óêàçàííûì ñïîñîáîì ìûíàõîäèì è òî s, äëÿ êîòîðîãî äîñòèãàåòñÿ ìèíèìóì â (2.2). Åñëè ìûäëÿ âñåõ (i, j) áóäåì ôèêñèðîâàòü ýòî s, òî ñìîæåì áûñòðî îïòèìàëüíîðàññòàâèòü ñêîáêè â çàäà÷å B1n (â èñõîäíîé çàäà÷å), ðàçáèâàÿ êàæäîåïðîèçâåäåíèå ïîñëåäîâàòåëüíî îïòèìàëüíûì îáðàçîì íà 2 ïðîèçâåäåíèÿ.Òåîðåìà äîêàçàíà.ãäå ìèíèìóì áåðåòñÿ ïî âñåì12Çàäà÷à î êðàò÷àéøèõ ïóòÿõÏóñòü G ïîëíûé îðèåíòèðîâàííûé ãðàô ñ n âåðøèíàìèv1 , v2 , .
. . , vn . Ïóñòü êàæäîé äóãå (vi , vj ) ñîïîñòàâëåíî äåéñòâèòåëüíîå÷èñëî dij > 0, ëèáî dij = +∞. ×èñëî dij òðàêòóåòñÿ êàê ðàññòîÿíèå èç viâ vj íàïðÿìóþ. Äëèíà îðèåíòèðîâàííîãî ïóòè èç vi â vj îïðåäåëÿåòñÿêàê ñóììà äëèí âñåõ äóã ýòîãî ïóòè (îíà ðàâíà +∞, åñëè õîòÿ áû îäíîñëàãàåìîå ðàâíî +∞). Êðàò÷àéøåå ðàññòîÿíèå d¯ij èç vi â vj îïðåäåëèìêàê ìèíèìóì äëèí ïî âñåì îðèåíòèðîâàííûì ïóòÿì èç vi â vj .
Ñîîòâåòñòâóþùèé ïóòü áóäåì íàçûâàòü êðàò÷àéøèì. Ðàññìîòðèì ñëåäóþùóþçàäà÷ó î êðàò÷àéøèõ ïóòÿõ.Âõîä: ìàòðèöà D = kdij k ïîðÿäêà n (ñ÷èòàåì, ÷òî dii = 0 äëÿ âñåõi).Òðåáóåòñÿ: ïîñòðîèòü ìàòðèöó D̄ = kd¯ij k êðàò÷àéøèõ ðàññòîÿíèé.Îòìåòèì, ÷òî àíàëîãè÷íóþ çàäà÷ó äëÿ íåïîëíîãî ãðàôà ìîæíîñâåñòè ê çàäà÷å î ïîëíîì ãðàôå, ïîëîæèâ dij = +∞ äëÿ íåñóùåñòâóþùèõäóã. Åñëè dij = dji äëÿ âñåõ i, j , òî ãðàô G ìîæíî ñ÷èòàòü íåîðèåíòèðîâàííûì.Àëãîðèòì äëÿ óêàçàííîé çàäà÷è, îñíîâàííûé íà ïåðåáîðå âñåõâîçìîæíûõ ïóòåé, èìååò íå ìåíåå, ÷åì ýêñïîíåíöèàëüíóþ ñëîæíîñòü,ïîñêîëüêó èç vi â vj ñóùåñòâóåò íå ìåíåå (n−2)! ïóòåé áåç ïîâòîðÿþùèõñÿâåðøèí.Òåîðåìà 2.3. Ñóùåñòâóåò àëãîðèòì äëÿ çàäà÷è î êðàò÷àéøèõD ìàòðèöó D̄, ñ ÷èñëîì îïåðàöèé (àðèô3ìåòè÷åñêèõ è ñðàâíåíèé ÷èñåë) O(n ), ãäå n ÷èñëî âåðøèí â ãðàôå.Äîêàçàòåëüñòâî.
Ââåäåì ñëåäóþùèå ïîäçàäà÷è: äëÿ êàæäîé ïàðû(k)i, j è íàòóðàëüíîãî k > 0 âû÷èñëèòü dij ìèíèìàëüíóþ äëèíó ñðåäèâñåõ îðèåíòèðîâàííûõ ïóòåé èç vi â vj , ïðîõîäÿùèõ, êðîìå vi è vj , òîëüêîïî âåðøèíàì v1 , v2 , . . . , vk (âîçìîæíî òîëüêî ïî ÷àñòè èëè íàïðÿìóþ èçvi â vj ). Åñëè k = 0, òî ðàçðåøàåòñÿ òîëüêî ïåðåõîä èç vi â vj íàïðÿìóþ.(k)Ïóñòü D(k) = kdij k. Òîãäà D(0) = D è D(n) = D̄. Áóäåì ïîñëåäîâàòåëüíîâû÷èñëÿòü D(1) , D(2) , .
. . , D(n) .Óòâåðæäåíèå. Äëÿ ëþáûõ i, j è k > 0ïóòÿõ, ñòðîÿùèé ïî ìàòðèöå(k)(k−1)dij = min(dij(k−1), dik(k−1)+ dkj).Âñå ïóòè èç vi â vj , èñïîëüçóþùèå òîëüêî âåðøèíûv1 , v2 , . . . , vk , ðàñïàäàþòñÿ íà 2 ìíîæåñòâà A è B íå ïðîõîäÿùèõ ÷åðåç(k−1)vk è ïðîõîäÿùèõ ÷åðåç vk . Ìèíèìàëüíàÿ äëèíà ïóòåé â A ðàâíà dijïî îïðåäåëåíèþ. Êàæäûé ïóòü èç B ðàçáèâàåòñÿ íà 2 ÷àñòè: ïóòü B1 èçvi â vk ïî âåðøèíàì v1 , v2 , . . . , vk−1 è ïóòü B2 èç vk â vj ïî âåðøèíàìÄîêàçàòåëüñòâî.13(k−1)v1 , v2 , . . .
, vk−1 . Ìèíèìàëüíàÿ äëèíà ïóòè â B1 ðàâíà dik , à â B2 (k)(k−1)(k−1)(k−1)(k−1)+ dkj , ïîëó÷àåì dij . Óòâåðæäåíèåè dikdkj . Ñðàâíèâàÿ dijäîêàçàíî.(k)Çàìå÷àíèå. Âû÷èñëÿÿ dij îïèñàííûì ñïîñîáîì, ìû, â ÷àñòíîñòè,óçíàåì, èñïîëüçîâàòü vk èëè íåò.Òàêèì îáðàçîì, äëÿ âû÷èñëåíèÿ D(k) ïî D(k−1) äîñòàòî÷íî n2 ñëîæåíèé è n2 ñðàâíåíèé ÷èñåë, à äëÿ âû÷èñëåíèÿ D(1) , D(2) , . . . , D(n) = D̄ïî çàäàííîé ìàòðèöå D = D(0) äîñòàòî÷íî n3 ñëîæåíèé è n3 ñðàâíåíèé.Òåîðåìà äîêàçàíà.Ïðè ýòîì, ó÷èòûâàÿ çàìå÷àíèå, ìîæíî áûñòðî óñòàíîâèòü è ñàìèêðàò÷àéøèå ïóòè.2.2. Ìåòîä ðàçäåëÿé è âëàñòâóé.
Òåîðåìà îðåêóððåíòíîì íåðàâåíñòâåÄðóãîé ðåêóððåíòíûé ìåòîä ïîñòðîåíèÿ áûñòðûõ àëãîðèòìîâ ýòî ìåòîä, êîòîðûé íàçûâàþò ðàçäåëÿé è âëàñòâóé.  íåì òàêæå ðåøåíèå çàäà÷è ñâîäèòñÿ ê ðåøåíèþ ïîäçàäà÷, íî, â îòëè÷èå îò ìåòîäàäèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ, ðàçìåðíîñòü ïîäçàäà÷ îòëè÷àåòñÿ îòðàçìåðíîñòè çàäà÷è íå íà êîíñòàíòó, à â êîíñòàíòó ðàç è ïîäçàäà÷èðåøàþòñÿ íåçàâèñèìî äðóã îò äðóãà. Äëÿ ïîëó÷åíèÿ îöåíîê ñëîæíîñòèòàêèõ àëãîðèòìîâ èñïîëüçóåòñÿ ñëåäóþùàÿ òåîðåìà.Òåîðåìà 2.4 (î ðåêóððåíòíîì íåðàâåíñòâå).
Ïóñòü L(n) ôóíê-n. Ïóñòü c íàòóðàëüíîå ÷èñëî, c > 2, èa, b, α - äåéñòâèòåëüíûå êîíñòàíòû, ïðè÷åì a > 0, è ïóñòü äëÿ âñåõn = ck , ãäå k ëþáîå íàòóðàëüíîå ÷èñëî (k = 1, 2, 3, . . .), âûïîëíÿåòñÿöèÿ íàòóðàëüíîãî ïàðàìåòðàíåðàâåíñòâînL(n) 6 aL( ) + bnα .c(2.3)Ïóñòü ïðè ýòîì L(n) ìîíîòîííî íå óáûâàåò íà êàæäîì îòðåçêå[ck + 1, ck+1 ]. Òîãäà ïðè ñòðåìëåíèè n ê áåñêîíå÷íîñòè äëÿ âñåõ nâûïîëíÿåòñÿαO(n ),L(n) = O(nlogc a ),O(nα log n),åñëèα > logc a,åñëèα < logc a,α = logc a.åñëè îöåíêàõ âèäà O(g(n) logk n), ãäå k êîíñòàíòà, âîñíîâàíèè ëîãàðèôìà ïðåäïîëàãàåòñÿ ëþáîå ïîñòîÿííîå ÷èñëî. Ïðè ýòîìïåðåõîä îò îäíîãî îñíîâàíèÿ ê äðóãîìó èçìåíÿåò òîëüêî êîíñòàíòó â O.Çàìå÷àíèå.14Ïóñòü n = ck , ãäå k = 1, 2, 3, .
. .. Òîãäà, ïðèìåíÿÿíåñêîëüêî ðàç (2.3), ïîëó÷àåìÄîêàçàòåëüñòâî. n αnnα) + bnα =L(n) 6 aL( ) + bn 6 a(aL( 2 ) + bcccα= bn + abα6 bn + baαcαα= bn + bnα6 . . . 6 bn + bnαα n αc2+a L2n + a (aLacαacαα+ bnc3 a 2cαnckc2n+ . . . + bnÏóñòü d = max(b, L(1)). Òàê êàênα+b36 n α+a Lc2n a k−1cα)=c3k6+a Lnck.= 1, òî a k−1 a a 2L(n) 6 dn 1 + α + α + . .
. + α+ dak =cccα a 2 a k a.= dnα 1 + α + α + · · · + αcccÐàññìîòðèì 3 ñëó÷àÿ:a< 1 =⇒ L(n) 6 dnα const = O(nα );αca2) logc a > α =⇒ α > 1 =⇒c α 2 α k ! a kαccc=⇒ L(n) 6 dnα α++ ··· +=⇒1+caaa|{z}1)logc a < α =⇒6constlogc a=⇒ L(n) 6 dak const = O(alogc n ) = O(n) (òàê êàê alogc n = nlogc a );3) logc a = α =⇒ a = cα =⇒ L(n) 6 dnα (k + 1) = dnα (1 + logc n) == O(nα log n).Ïóñòü òåïåðü n ëþáîå.
Òîãäà ñóùåñòâóåò òàêîå íàòóðàëüíîå k ,÷òî c < n 6 ck+1 . Ðàññìîòðèì 3 ñëó÷àÿ, ó÷èòûâàÿ, ÷òî ïî óñëîâèþ L(n) íåóáûâàþùàÿ ôóíêöèÿ íà êàæäîì îòðåçêå [ck + 1, ck+1 ] (p íèæå k15íåêîòîðàÿ êîíñòàíòà):αα1) α > logc a =⇒ L(n) 6 L(ck+1 ) 6 p(ck+1 ) = pcα (ck ) 6 pcα nα == O(nα );logc a2) α < logc a =⇒ L(n) 6 L(ck+1 ) 6 p(ck+1 )logc a= pclogc a (ck )66 panlogc a = O(nlogc a );α3) α = logc a =⇒ L(n) 6 L(ck+1 ) 6 pc(k+1)α logc (ck+1 ) 6 pcα (ck ) 2k 66 pcα 2nα logc n = O(nα ) log n.Òåîðåìà äîêàçàíà.2.3. Àëãîðèòì Êàðàöóáû äëÿ óìíîæåíèÿ ÷èñåëÅñëè òðåáóåòñÿ ñëîæèòü äâà n-ðàçðÿäíûõ ÷èñëà, òî ìîæíî ïðîèçâåñòè ñëîæåíèå â ñòîëáèê.
Ïðè ýòîì â êàæäîì ðàçðÿäå íàì íóæíî âçàâèñèìîñòè îò çíà÷åíèé äàííîãî ðàçðÿäà â ñëàãàåìûõ è îò âåëè÷èíûïåðåíîñà èç ïðåäûäóùåãî ðàçðÿäà âû÷èñëèòü ðàçðÿä ñóììû è âåëè÷èíóïåðåíîñà â ñëåäóþùèé ðàçðÿä. Äëÿ îäíîãî ðàçðÿäà ýòî òðåáóåò êîíñòàíòíîãî ÷èñëà îïåðàöèé, à â öåëîì äëÿ ñëîæåíèÿ äâóõ n-ðàçðÿäíûõ÷èñåë O(n) îïåðàöèé íàä ðàçðÿäàìè. Àíàëîãè÷íóþ îöåíêó O(n) ìîæíîïîëó÷èòü è äëÿ ñëîæíîñòè âû÷èòàíèÿ â ñòîëáèê. Òîëüêî çäåñü âìåñòîïåðåíîñà â ñëåäóþùèé ðàçðÿä ôîðìèðóåòñÿ çàïðîñ èç ñëåäóþùåãî ðàçðÿäà.Åñëè äâà n-ðàçðÿäíûõ ÷èñëà óìíîæàòü â ñòîëáèê, òî âñå ðàçðÿäûïåðâîãî ÷èñëà ñíà÷àëà íàäî óìíîæàòü íà ïåðâûé ðàçðÿä âòîðîãî ÷èñëà,çàòåì íà ñëåäóþùèé ðàçðÿä è ò.
ä. Òàêèì îáðàçîì ÷èñëî îïåðàöèé íàäðàçðÿäàìè áóäåò íå ìåíåå n2 . Áîëåå áûñòðûé (ïî ïîðÿäêó) àëãîðèòìïðåäëîæèë À. À. Êàðàöóáà [8], è èìåííî ýòîò àëãîðèòì ñ÷èòàåòñÿ ïåðâûìàëãîðèòìîì òèïà ðàçäåëÿé è âëàñòâóé.Äëÿ ïðîñòîòû ìû íå áóäåì ðàññìàòðèâàòü àäðåñàöèþ, à áóäåì âêà÷åñòâå àëãîðèòìîâ ðàññìàòðèâàòü ñõåìû èç ôóíêöèîíàëüíûõ ýëåìåíòîâ â áàçèñå èç âñåõ äâóõìåñòíûõ áóëåâñêèõ îïåðàöèé è ïîä ñëîæíîñòüþàëãîðèòìà ïîíèìàòü ÷èñëî ýëåìåíòîâ â ñõåìå.  ýòîì ñëó÷àå ãîâîðÿò îáèòîâîé ñëîæíîñòè àëãîðèòìà.Òåîðåìà 2.5 (Êàðàöóáà À.
À.). Äëÿ óìíîæåíèÿ äâóõ äâîè÷-n-ðàçðÿäíûõ ÷èñåë ñóùåñòâóåò àëãîðèòì ñ áèòîâîé ñëîæíîñòüþlog2 3O(n).íûõÏîêàæåì ñíà÷àëà, ÷òî àëãîðèòì (ñõåìó) äëÿóìíîæåíèÿ (n + 1)-ðàçðÿäíûõ äâîè÷íûõ ÷èñåë ìîæíî ïîëó÷èòü, èñïîëüçóÿ àëãîðèòì (ñõåìó) äëÿ óìíîæåíèÿ n-ðàçðÿäíûõ äâîè÷íûõ ÷èñåë è äîïîëíèòåëüíî O(n) áèòîâûõ îïåðàöèé.
Äåéñòâèòåëüíî, ïóñòüÄîêàçàòåëüñòâî.16òðåáóåòñÿ ïåðåìíîæèòü äâà (n + 1)-ðàçðÿäíûõ äâîè÷íûõ ÷èñëà X1 =(x0 , x1 , . . . , xn )2 è Y1 = (y0 , y1 , . . . , yn )2 . Îáîçíà÷èì (x1 , x2 , . . . , xn )2 = Xè (y1 , y2 , . . . , yn )2 = Y . Ïðè ýòîì X1 = x0 2n + X , Y1 = y0 2n + Y èX1 Y1 = x0 y0 22n + (x0 Y + y0 X)2n + XY.Ïîýòîìó äëÿ âû÷èñëåíèÿ X1 Y1 äîñòàòî÷íî èñïîëüçîâàòü óìíîæèòåëüMn äëÿ âû÷èñëåíèÿ XY , 2n ýëåìåíòîâ äëÿ âû÷èñëåíèÿ x0 Y è y0 X ,1 ýëåìåíò äëÿ âû÷èñëåíèÿ x0 y0 è 3 ñóììàòîðà ïîðÿäêà (òî åñòü äëÿ÷èñëà ðàçðÿäîâ) íå áîëåå 2n + 2, òàê êàê X1 Y1 < 22n+2 .
Îòìåòèì,÷òî ÷èñëà x0 y0 è x0 Y + y0 X íàäî ïîäàâàòü íà ñóììàòîðû ñî ñäâèãîì,îäíîâðåìåííî ïîäàâàÿ íà ìëàäøèå ðàçðÿäû 0. Ïðè ýòîì 0 ìîæíî ïðåäâàðèòåëüíî ïîëó÷èòü ïîäñõåìîé ñ 2 ýëåìåíòàìè, ðåàëèçóþùåé x0 x̄0 = 0.Òàê êàê ñëîæíîñòü êàæäîãî ñóììàòîðà ìîæíî ñäåëàòü íå áîëåå O(n), òîñëîæíîñòü ïîëó÷åííîé ñõåìû áóäåò íå áîëüøå ÷åì L(Mn ) + O(n). Ïóñòüòåïåðü íóæíî ïåðåìíîæèòü äâà 2n-ðàçðÿäíûõ ÷èñëà X è Y . Ðàçîáüåìèõ íà ÷àñòè, ñîäåðæàùèå ïî n ðàçðÿäîâ. Òîãäà ïîëó÷èì X = X1 2n + X2 ,Y = Y1 2n + Y2 . ÎòñþäàXY = X1 Y1 22n + (X1 Y2 + X2 Y1 )2n + X2 Y2 == X1 Y1 22n + [(X1 + X2 )(Y1 + Y2 ) − X1 Y1 − X2 Y2 ]2n + X2 Y2 .Òàê êàê X1 Y2 + X2 Y1 > 0, òî ïðè âû÷èòàíèè â êâàäðàòíîé ñêîáêå íåâîçíèêàåò îòðèöàòåëüíûõ ÷èñåë. Òàêèì îáðàçîì, óìíîæåíèå XY äâóõ2n-ðàçðÿäíûõ ÷èñåë ñâîäèòñÿ ê äâóì óìíîæåíèÿì n-ðàçðÿäíûõ ÷èñåëX1 Y1 è X2 Y2 , óìíîæåíèþ n + 1-ðàçðÿäíûõ ÷èñåë (X1 + X2 )(Y1 + Y2 ) èíåñêîëüêèì ñëîæåíèÿì è âû÷èòàíèÿì ÷èñåë ñ ÷èñëîì ðàçðÿäîâ íå áîëåå4n (òàê êàê XY < 24n ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
