Բաժանիր և տիրիր (ալգորիթմ)

«Բաժանիր և տիրիր» (անգլ.՝ Divide and conquer), համակարգչային գիտության մեջ ալգորիթմների նախագծման պարադիգմ: «Բաժանիր և տիրիր» ալգորիթմը ռեկուրսիվորեն բաժանում է խնդիրը երկու կամ ավելի ենթախնդիրների, որոնք ունեն նույն կամ առնչվող տեսակը, մինչև դրանք բավականին պարզ դառնան ուղղակիորեն լուծվելու համար: Ենթախնդիրների լուծումները համակցվում են՝ նախնական խնդրի լուծումը տալու համար:

«Բաժանիր և տիրիր» մեթոդը բազմաթիվ խնդիրների արդյունավետ ալգորիթմների հիմքն է, ինչպիսիք են տեսակավորումը (օրինակ՝ Արագ տեսակավորում, Միաձուլման տեսակավորում), մեծ թվերի բազմապատկումը (օրինակ՝ Կարացուբայի ալգորիթմ), կետին ամենամոտ զույգի որոնումը, սինթակտիկ վերլուծությունը (օրինակ՝ վերևից ներքև վերլուծիչներ), և Ֆուրիեի դիսկրետ փոխակերպման հաշվարկը (Ֆուրիեի արագ փոխակերպում, (անգլ.՝ Fast Fourier transform (FFT))^[1]:

«Բաժանիր և տիրիր» տեխնիկայի արդյունավետ ալգորիթմների նախագծումը կարող է բարդ լինել։ Ինչպես մաթեմատիկական ինդուկցիայում, այստեղ ևս հաճախ անհրաժեշտ է ընդհանրացնել խնդիրը, որպեսզի այն ենթարկվի ռեկուրսիվ լուծման։ «Բաժանիր և տիրիր» ալգորիթմի ճշտությունը սովորաբար ապացուցվում է մաթեմատիկական ինդուկցիայով, իսկ դրա հաշվարկային ծախսը հաճախ որոշվում է ռեկուրենտ հավասարումների լուծման միջոցով:

Բաժանիր և տիրիր

«Բաժանիր և տիրիր» մոտեցումը հաճախ օգտագործվում է խնդրի օպտիմալ լուծում գտնելու համար: Հիմնական գաղափարն այն է, որ տրված խնդիրը բաժանվի երկու կամ ավելի նման, բայց պարզեցված ենթախնդիրների, այնուհետև դրանք հերթով լուծելով և վերջնական լուծումները միավորելով՝ ստացվի սկզբնական խնդրի լուծումը։ Բավականին պարզ խնդիրները լուծվում են անմիջապես։ Օրինակ, եթե անհրաժեշտ է տեսակավորել n բնական թվերի ցանկը, այն բաժանում են n/2 թվերի երկու ցանկի, յուրաքանչյուրն առանձին տեսակավորում, իսկ հետո համապատասխանաբար միավորում արդյունքները՝ ստանալով սկզբնական ցանկի տեսակավորված տարբերակը (տես նկարը): Այս մոտեցումը հայտնի է որպես Միաձուլման տեսակավորման ալգորիթմ:

«Բաժանիր և տիրիր» անվանումը երբեմն կիրառվում է այն ալգորիթմների համար, որոնք յուրաքանչյուր խնդիր նվազեցնում և հասցնում են միայն մեկ ենթախնդրի, ինչպես օրինակ՝ տեսակավորված ցուցակում գրառում գտնելու երկուական որոնման ալգորիթմը (կամ Թվային մեթոդներում դրա անալոգը)^[2]: Վերջիններս կարող են լինել ավելի արդյունավետ, քան հիմնական «բաժանիր և տիրիր» ալգորիթմները, մասնավորապես, եթե դրանք օգտագործում են պոչի ռեկուրսիա և կարող են վերածվել պարզ ցիկլերի: Այս լայն սահմանման համաձայն, սակայն, յուրաքանչյուր ալգորիթմ, որն օգտագործում է ռեկուրսիա կամ ցիկլեր, կարող է դիտվել որպես «բաժանիր և տիրիր» ալգորիթմ։ Հետևաբար, որոշ հեղինակներ կարծում են, որ «բաժանիր և տիրիր» անունը պետք է օգտագործվի միայն այն դեպքում, երբ յուրաքանչյուր խնդիր կարող է առաջացնել երկու կամ ավելի ենթախնդիրներ^[3]։ Փոխարենը մեկ ենթախնդիր դասի համար առաջարկվել է «նվազեցրու և տիրիր» անվանումը^[4]։ «Բաժանիր և տիրիր» ալգորիթմների կարևոր կիրառություններից մեկը օպտիմալացման մեջ է, որտեղ, եթե որոնման տարածքը յուրաքանչյուր քայլում կրճատվում է («հատում») հաստատուն գործոնով, ապա ընդհանուր ալգորիթմն ունենում է նույն ասիմպտոտիկ բարդությունը, ինչ հատման քայլը, ընդ որում հաստատունը կախված է հատման գործակցից (երկրաչափական շարքի գումար)։ Այս ամենը հայտնի է «Հատում և որոնում» անվանմամբ:

Վաղ պատմական օրինակներ

Այս ալգորիթմների վաղ օրինակները հիմնականում «Նվազեցրու և տիրիր» տեսակի են. սկզբնական խնդիրը հաջորդաբար բաժանվում է «միայնակ» ենթախնդիրների և կարող է լուծվել կրկնվելով։

Երկուական որոնումը («նվազեցրու և տիրիր» տեսակի ալգորիթմ), որտեղ ենթախնդիրները մոտավորապես սկզբնական չափի կեսին են հավասար, երկար պատմություն ունի։ Չնայած ալգորիթմի հստակ նկարագրությունը համակարգիչների վրա հայտնվեց 1946 թվականի Ջոն Մաուչլիի հոդվածում, տեսակավորված ցուցակ օգտագործելու գաղափարը իրերի որոնումը հեշտացնելու համար հասնում է մինչև Բաբելոն՝ մեր թվարկությունից առաջ 200 թվական^[5]։ Մեկ այլ «Նվազեցրու և տիրիր» տեսակի մինչքրիստոնեական շրջանի հին ալգորիթմ է էվկլիդեսի ալգորիթմը, որը թույլ է տալիս հաշվարկել երկու թվերի ամենամեծ ընդհանուր բաժանարարը՝ թվերը նվազեցնելով ավելի ու ավելի փոքր համարժեք ենթախնդիրների։։

Բազմաթիվ ենթախնդիրներով «Բաժանիր և տիրիր» ալգորիթմի վաղ օրինակ է Գաուսի 1805 թվականի նկարագրությունը, որն այժմ կոչվում է «Քուլի-Թուկի Ֆուրիեի արագ փոխակերպման (FFT)» ալգորիթմ^[6], թեև նա քանակապես չի վերլուծել դրա գործողությունների և FFT-ները լայն տարածում չեն գտել մինչև որ դրանք ավելի քան մեկ դար անց նորից հայտնաբերվել են:

Երկու ենթախնդիրներից բաղկացած «Բաժանիր և տիրիր» տեսակի հին ալգորիթմը, որը հատուկ մշակվել է համակարգիչների համար և պատշաճ կերպով վերլուծվել է, միաձուլման տեսակավորումն է՝ հայտնաբերված Ջոն ֆոն Նեյմանի կողմից 1945 թվականին^[7]։

Մեկ այլ նշանավոր օրինակ է 1960 թվականին Անատոլի Կարացուբայի կողմից հորինված ալգորիթմը^[8], որը կարող է բազմապատկել երկու n քանակի նիշեր ունեցող թվեր $O(n^{\log _{2}3})$ բարդության գործողություններում։ Այս ալգորիթմը հերքեց Անդրեյ Կոլմոգորովի 1956 թվականի ենթադրությունը, որ այդ առաջադրանքի համար $\Omega (n^{2})$ բարդության գործողություններ կպահանջվեն։

Որպես «Բաժանիր և տիրիր» ալգորիթմի մեկ այլ օրինակ, որն ի սկզբանե չի ներառել համակարգիչներ, Դոնալդ Կնուտը ներկայացրել է այն մեթոդը, որը սովորաբար օգտագործվում է փոստային բաժանմունքների աշխատանքը կազմակերպելու համար. նամակները տեսակավորվում են առանձին պայուսակների մեջ՝ ըստ տարբեր աշխարհագրական տարածքների, այս պայուսակներից յուրաքանչյուրն ինքնին տեսակավորվում է տարբեր խմբաքանակներում՝ ըստ փոքր տարածաշրջանների և այլն, մինչև դրանք առաքվում են^[5]: Սա կապված է կարգային տեսակավորման հետ, որը նկարագրվել է դեռևս 1929 թվականին՝ դակիչ քարտերի տեսակավորման մեքենաների համար^[5]։

Առավելություններ

Բարդ խնդիրների լուծում

«Բաժանիր և տիրիր» մեթոդը հզոր գործիք է մտավոր բարդ խնդիրների լուծման համար. այն պահանջում է ընդամենը խնդիրը ենթախնդիրների բաժանելու, պարզ դեպքերը լուծելու և ենթախնդիրները սկզբնական խնդրին միավորելու մեխանիզմ։ Նմանապես, «Նվազեցրու և տիրիր» մեթոդը պահանջում է միայն խնդիրը նվազեցնել մեկ փոքր խնդրի, օրինակ՝ դասական Հանոյի աշտարակ գլուխկոտրուկը, որը աշտարակի $n$ բարձրությունից տեղափոխումը նվազեցնում է $n-1$ բարձրությունից տեղափոխման։

Ալգորիթմի արդյունավետություն

«Բաժանիր և տիրիր» մեթոդը հաճախ օգնում է արդյունավետ ալգորիթմների հայտնաբերման մեջ։ Օրինակ՝ այն կարևոր էր Կարացուբայի արագ բազմապատկման մեթոդի, արագ տեսակավորման և միաձուլման տեսակավորման ալգորիթմների, Շտրասենիմատրիցների բազմապատկման և Ֆուրիեի արագ վերափոխումների համար։

Այս բոլոր օրինակներում «բաժանիր և տիրիր» մոտեցումը հանգեցրել է լուծման ասիմպտոտիկ արժեքի բարելավման։

«Բաժանիր և տիրիր» ալգորիթմները ի սկզբանե հարմարեցվել են բազմամշակիչ մեքենաներում աշխատելու համար, հա��կապես համօգտագործվող հիշողություն ունեցող համակարգերում, որտեղ կարիք չկա, որ մշակիչների միջև տվյալների հաղորդակցությունը նախապես պլանավորվի, քանի որ տարբեր ենթախնդիրների լուծումները կարող են իրականացվել տարբեր պրոցեսորների վրա:

Հիշողության հասանելիություն

«Բաժանիր և տիրիր» ալգորիթմները, բնականաբար, հակված են արդյունավետորեն օգտագործելու հիշողության քեշերը: Պատճառը կայանում է նրանում, որ երբ ենթախնդիրը բավական փոքր է դառնում, այն և դրա բոլոր ենթախնդիրները, ըստ էության, կարող են լուծվել քեշի մեջ՝ առանց ավելի դանդաղ հիմնական հիշողությանը մուտք գործելու։ Ալգորիթմը, որը նախագծված է այս կերպ քեշն օգտագործելու համար, կոչվում է «քեշից անկախ» (անգլ.՝ cache-oblivious) ալգորիթմ, քանի որ այն չի պարունակում քեշի չափը որպես հստակ պարամետր^[9]։ Ավելին, «Բաժանիր և տիրիր» ալգորիթմները կարող են նախագծվել կարևոր ալգորիթմների համար (օրինակ՝ տեսակավորում, FFT-ներ և մատրիցնների բազմապատկում)՝ որպես օպտիմալ, քեշից անկախ ալգորիթմներ, որոնք քեշն օգտագործում են ասիմպտոտիկ իմաստով հնարավորինս արդյունավետ կերպով՝ անկախ քեշի չափից։ Ի հակադրություն, քեշի շահագործման ավանդական մոտեցումը արգելափակում է այն, ինչպես օրինակ՝ ցիկլային ներդիրների օպտիմիզացման դեպքում, որտեղ խնդիրը հստակ բաժանվում է համապատասխան չափերի հատվածների։ Սա նույնպես կարող է քեշն օպտիմալ կերպով օգտագործել, սակայն միայն այն դեպքում, երբ ալգորիթմը հարմարեցված է կոնկրետ սարքի քեշի չափերի համար։

Նույն առավելությունն առկա է հիերարխիկ պահպանման այլ համակարգերի նկատմամբ, ինչպիսիք են NUMA-ն կամ վիրտուալ հիշողությունը։ իԲացի այդ, քեշի մի քանի մակարդակներում, երբ ենթախնդիրը բավականաչափ փոքր է, այն կարող է լուծվել հիերարխիայի տվյալ մակարդակում՝ առանց մուտք գործել ավելի բարձր (ավելի դանդաղ) մակարդակներ:

Մոտարկման հսկողություն

Հաշվարկներում, որտեղ օգտագործվում է մոտարկման թվաբանություն, (օրինակ՝ կոտորակային թվերի հետ աշխատելիս) «բաժանիր և տիրիր» ալգորիթմը կարող է տալ ավելի ճշգրիտ արդյունքներ, քան մակերեսորեն համարժեք կրկնողական մեթոդը։ Օրինակ՝ N թվերը կարելի է գումարել կամ պարզ ցիկլի միջոցով, որտեղ յուրաքանչյուր թիվ ավելացվում է միակ փոփոխականի մեջ, կամ «բաժանիր և տիրիր» տեսակի ալգորիթմով, որը կոչվում է զույգային գումարում։ Վերջինս տվյալների հավաքածուն բաժանում է երկու մասի, ռեկուրսիվ կերպով հաշվարկում է յուրաքանչյուր մասի գումարը, ապա գումարում այդ երկու գումարները։ Թեև երկրորդ մեթոդը կատարում է նույն քանակությամբ գումարումներ, որքան առաջինը, և ունի ռեկուրսիվ կանչերի լրացուցիչ ծախսեր, այն սովորաբար ավելի ճշգրիտ է։^[10]

Իրականացման խնդիրներ

Ռեկուրսիա

«Բաժանիր և տիրիր» ալգորիթմները բնականորեն իրականացվում են որպես ռեկուրսիվ ընթացակարգեր։ Այդ դեպքում, մասնակի ենթախնդիրները, որոնք տանում են դեպի տվյալ պահին լուծվող խնդիրը, ավտոմատ կերպով պահվում են ընթացակարգի կանչի բլոկում։ Ռեկուրսիվ ֆունկցիան այն ֆունկցիան է, որն իր սահմանման մեջ կանչում է ինքն իրեն։

Պարզ բլոկ

«Բաժանիր և տիրիր» ալգորիթմները կարող են նաև իրականացվել ոչ ռեկուրսիվ ծրագրով, որը մասնակի ենթախնդիրները պահում է որոշակի հստակ տվյալների կառուցվածքում, ինչպիսիք են բլոկը (անգլ.՝ stack), հերթը (անգլ.՝ queue) կամ առաջնահերթության հերթը (անգլ.՝ priority queue)։ Այս մոտեցումը ավելի շատ ազատություն է տալիս հաջորդ լուծվող ենթախնդրի ընտրության մեջ, ինչը կարևոր հատկություն է որոշ կիրառություններում: Այս մոտեցումը նաև ստանդարտ լուծում է այն ծրագրավորման լեզուներում, որոնք չեն աջակցում ռեկուրսիվ ընթացակարգերին։

Բլոկի չափ

«Բաժանիր և տիրիր» ալգորիթմների ռեկուրսիվ իրականացումներում անհրաժեշտ է ապահովել, որ ռեկուրսիայի բլոկի (անգլ.՝ stack) համար բավարար հիշողություն հատկացված լինի, հակառակ դեպքում ծրագրի կատարումը կարող է ձախողվել՝ բլոկի գերլցման պատճառով։ Ժամանակի առումով արդյունավետ «բաժանիր և տիրիր» ալգորիթմները հաճախ ունեն հարաբերականորեն ավելի փոքր ռեկուրսիայի խորություն։ Օրինակ՝ արագ տեսակավորման ալգորիթմը կարելի է այնպես իրականացնել, որ երբեք չպահանջի ավելի քան $\log _{2}n$ քանակի ներդրված ռեկուրսիվ կանչեր՝ $n$ տարրեր տեսակավորելու համար։

Բլոկի գերլցումից բարդ է խուսափել ռեկուրսիվ ընթացակարգեր օգտագործելիս, քանի որ շատ կոմպիլյատորներ ենթադրում են, որ ռեկուրսիայի բլոկը հիշողության հարակցական տարածք է, և որոշները դրա համար հատկացնում են ֆիքսված քանակի տարածք։ Կոմպիլյատորները կարող են նաև բլոկում պահպանել ավելի շատ տեղեկություն, քան խստորեն անհրաժեշտ է, օրինակ՝ վերադարձի հասցեն, անփոփոխ պարամետրերը և ընթացակարգի ներքին փոփոխականները։ Այսպիսով, բլոկի գերլցման ռիսկը կարելի է նվազեցնել՝ նվազագույնի հասցնելով ռեկուրսիվ ընթացակարգի պարամետրերը և ներքին փոփոխականները, կամ օգտագործելով պարզ բլոկ կառուցվածք (անգլ.՝ explicit stack structure)։

Լավագույն դեպքերի ընտրություն

Ցանկացած ռեկուրսիվ ալգորիթմում կա զգալի ազատություն՝ հիմքում ընկած դեպքերի ընտրության հարցում։ Դրանք այն փոքր ենթախնդիրներն են, որոնք լուծվում են անմիջականորեն՝ ռեկուրսիան ավարտելու համար։

Ընտրելով ամենափոքր կամ ամենապարզ հիմքում ընկած դեպքերը՝ ծրագրերը դառնում են ավելի էլեգանտ և, որպես կանոն, ավելի պարզ, քանի որ քիչ դեպքեր են հաշվի առնվում և դրանք համեմատաբար հեշտ են լուծվում։ Օրինակ՝ Ֆուրիեի արագ վերափոխման (FFT) ալգորիթմը կարող է դադարեցնել ռեկուրսիան, երբ մուտքը ընդամենը մեկ նմուշ է, իսկ արագ տեսակավորման ալգորիթմը՝ երբ մուտքը դատարկ ցուցակ է։ Երկու դեպքում էլ կա ընդամենը հիմքում ընկած մեկ դեպք, որը չի պահանջում որևէ մշակում։

Մյուս կողմից, արդյունավետությունը հաճախ բարելավվում է, եթե ռեկուրսիան դադարեցվում է հիմքում ընկած հարաբերականորեն մեծ դեպքերի վրա, որոնք լուծվում են ոչ ռեկուրսիվ կերպով՝ ստեղծելով հիբրիդային ալգորիթմ։ Այս ռազմավարությունը խուսափում է քիչ կամ ընդհանրապես աշխատանք չկատարող ռեկուրսիվ կանչերի ավելորդ ծախսերից և կարող է թույլ տալ օգտագործել մասնագիտացված ոչ ռեկուրսիվ ալգորիթմներ, որոնք այդ նշված դեպքերի համար ավելի արդյունավետ են, քան հստակ ռեկուրսիան։ Հիբրիդային ռեկուրսիվ ալգորիթմի համար ընդհանուր ընթացակարգը բազային դեպքի կարճ միացումով իրականացումն է (անգլ.՝ short-circuiting the base case)։ Այս դեպքում, նախքան ֆունկցիայի կանչը ստուգվում է, թե արդյոք հաջորդ քայլը կհանգեցնի բազային դեպքի՝ դրանով իսկ խուսափելով ավելորդ ֆունկցիայի կանչից։ Օրինակ, «ծառում»՝ «երեխա» հանգույցի վրա ռեկուրսիա օգտագործելու և հետո ստուգելու փոխարեն, թե արդյոք այն դատարկ է, կարելի է նախապես ստուգել դատարկ լինելը՝ ռեկուրսիա օգտագործելուց առաջ։ Այսպիսով, որոշ բինար ծառերի ալգորիթմներում հնարավոր է խուսափել ֆունկցիայի կանչերի կեսից։ Կարևոր է նշել, որ այս նկատառումներն անկախ են այն բանից, երբ ռեկուրսիան իրականացվում է կոմպիլյատորի կամ հստակ բլոկի միջոցով։

Օրինակ, շատ գրադարանային իրականացումներ արագ տեսակավորման ալգորիթմի փոխարեն կօգտագործեն պարզ ցիկլերի վրա հիմնված ներդրմամբ տեսակավորմանման ալգորիթմ, երբ տեսակավորվող տարրերի թիվը բավական փոքր է։ Կարևոր է նշել, որ եթե դատարկ ցուցակը լինի միակ հիմքում ընկած դեպքը, ապա ցուցակը $n$ տարրերով տեսակավորելու համար անհրաժեշտ կլիներ առավելագույնը $n$ արագ տեսակավորման կանչեր, որոնք բացի տարրը անմիջապես վերադարձնելուց ոչինչ չէին անի։

Որպես այլընտրանք, կարելի է օգտագործել է բազային մեծ դեպքեր, որոնցում դեռևս կիրառվում են «բաժանիր և տիրիր» ալգորիթմներ, բայց իրականացվում են նախապես ֆիքսված չափերի համար, որտեղ ալգորիթմը կարող է ամբողջությամբ բացվել կոդի մեջ՝ առանց ռեկուրսիայի, ցիկլերի կամ պայմանականների օգտագործման։ Օրինակ՝ այս մոտեցումը օգտագործվում է որոշ արդյունավետ FFT իրականացումների մեջ^[11]։ Հիմնային կոդերի ստեղծման մեթոդները կարող են օգտագործվել մեծ թվով առանձին բազային դեպքեր ստեղծելու համար, որոնք ցանկալի են այս ռազմավարությունն արդյունավետ իրականացնելու պարագայում^[11]։

Այս գաղափարի ընդհանրացված տարբերակը հայտնի է որպես ռեկուրսիայի «բացում» կամ «կոպտացում»։ Ժամանակի ընթացքում տարբեր մեթոդներ են առաջարկվել հիմքում ընկած դեպքերի մեծացման ընթացակարգը ավտոմատացնելու համար^[12]։

Դինամիկ ծրագրավորում՝ համընկնող ենթախնդիրների համար

Որոշ խնդիրների դեպքում, ճյուղավորված ռեկուրսիան կարող է բազմաթիվ անգամներ գնահատել նույն ենթախնդիրը։ Այսպիսի դեպքերում անհրաժեշտ է հայտնաբերել և պահպանել համընկնող ենթախնդիրների լուծումները, որը հայտնի է մեմորիզացիա անվամբ։ Երբ այս մոտեցումը կիրառվում է ամբողջությամբ, այն հանգեցնում է ներքևից վերև «բաժանիր և տիրիր» ալգորիթմների, ինչպիսին է դինամիկ ծրագրավորումը։

Տես նաև

Մաթեմատիկական ինդուկցիա

Ծանոթագրություններ

↑ Blahut, Richard (14 May 2014). Fast Algorithms for Signal Processing. Cambridge University Press. էջեր 139–143. ISBN 978-0-511-77637-3.
↑ Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (31 July 2009). Introduction to Algorithms. MIT Press. ISBN 978-0-262-53305-8.
↑ Brassard, G., and Bratley, P. Fundamental of Algorithmics, Prentice-Hall, 1996.
↑ Anany V. Levitin, Introduction to the Design and Analysis of Algorithms (Addison Wesley, 2002).
↑ ^5,0 ^5,1 ^5,2 Donald E. Knuth, The Art of Computer Programming: Volume 3, Sorting and Searching, second edition (Addison-Wesley, 1998).
↑ Heideman, M. T., D. H. Johnson, and C. S. Burrus, "Gauss and the history of the fast Fourier transform", IEEE ASSP Magazine, 1, (4), 14–21 (1984).
↑ Knuth, Donald (1998). The Art of Computer Programming: Volume 3 Sorting and Searching. էջ 159. ISBN 0-201-89685-0.
↑ Karatsuba, Anatolii A.; Yuri P. Ofman (1962). «Умножение многозначных чисел на автоматах». Doklady Akademii Nauk SSSR. 146: 293–294. Translated in Karatsuba, A.; Ofman, Yu. (1963). «Multiplication of Multidigit Numbers on Automata». Soviet Physics Doklady. 7: 595–596. Bibcode:1963SPhD....7..595K.
↑ M. Frigo; C. E. Leiserson; H. Prokop (1999). «Cache-oblivious algorithms». 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039). էջեր 285–297. doi:10.1109/SFFCS.1999.814600. ISBN 0-7695-0409-4. S2CID 62758836.
↑ Nicholas J. Higham, "The accuracy of floating-point summation", SIAM J. Scientific Computing 14 (4), 783–799 (1993).
↑ ^11,0 ^11,1 Frigo, M.; Johnson, S. G. (February 2005). «The design and implementation of FFTW3» (PDF). Proceedings of the IEEE. 93 (2): 216–231. CiteSeerX 10.1.1.66.3097. doi:10.1109/JPROC.2004.840301. S2CID 6644892.
↑ Radu Rugina and Martin Rinard, "Recursion unrolling for divide and conquer programs" in Languages and Compilers for Parallel Computing, chapter 3, pp. 34–48. Lecture Notes in Computer Science vol. 2017 (Berlin: Springer, 2001).

[1] Blahut, Richard (14 May 2014). Fast Algorithms for Signal Processing. Cambridge University Press. էջեր 139–143. ISBN 978-0-511-77637-3.

[CormenLeiserson2009-2] Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (31 July 2009). Introduction to Algorithms. MIT Press. ISBN 978-0-262-53305-8.

[3] Brassard, G., and Bratley, P. Fundamental of Algorithmics, Prentice-Hall, 1996.

[4] Anany V. Levitin, Introduction to the Design and Analysis of Algorithms (Addison Wesley, 2002).

[Knuth3-5] 5,0 ^5,1 ^5,2 Donald E. Knuth, The Art of Computer Programming: Volume 3, Sorting and Searching, second edition (Addison-Wesley, 1998).

[Heideman84-6] Heideman, M. T., D. H. Johnson, and C. S. Burrus, "Gauss and the history of the fast Fourier transform", IEEE ASSP Magazine, 1, (4), 14–21 (1984).

[7] Knuth, Donald (1998). The Art of Computer Programming: Volume 3 Sorting and Searching. էջ 159. ISBN 0-201-89685-0.

[8] Karatsuba, Anatolii A.; Yuri P. Ofman (1962). «Умножение многозначных чисел на автоматах». Doklady Akademii Nauk SSSR. 146: 293–294. Translated in Karatsuba, A.; Ofman, Yu. (1963). «Multiplication of Multidigit Numbers on Automata». Soviet Physics Doklady. 7: 595–596. Bibcode:1963SPhD....7..595K.

[cahob-9] M. Frigo; C. E. Leiserson; H. Prokop (1999). «Cache-oblivious algorithms». 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039). էջեր 285–297. doi:10.1109/SFFCS.1999.814600. ISBN 0-7695-0409-4. S2CID 62758836.

[10] Nicholas J. Higham, "The accuracy of floating-point summation", SIAM J. Scientific Computing 14 (4), 783–799 (1993).

[fftw-11] 11,0 ^11,1 Frigo, M.; Johnson, S. G. (February 2005). «The design and implementation of FFTW3» (PDF). Proceedings of the IEEE. 93 (2): 216–231. CiteSeerX 10.1.1.66.3097. doi:10.1109/JPROC.2004.840301. S2CID 6644892.

[12] Radu Rugina and Martin Rinard, "Recursion unrolling for divide and conquer programs" in Languages and Compilers for Parallel Computing, chapter 3, pp. 34–48. Lecture Notes in Computer Science vol. 2017 (Berlin: Springer, 2001).

[1]