Кіріспе
Үлкен сандарды көбейту алгоритмі Toom–Cook, кейде Toom 3 деп аталады, жаңа алгоритмді төмен күрделілігімен енгізген Андрей Тум және оның сипаттамасын жетілдірген Стивен Кук есімдерімен аталған, үлкен бүтін сандарды көбейту алгоритмі. Екі үлкен бүтін сан, a және b берілгенде, Toom–Cook оларды әрқайсысы l ұзындығындағы k кіші бөліктерге бөліп, осы бөліктермен операциялар орындайды. k саны артқан сайын, көбейтудің көптеген кіші операцияларын біріктіруге болады, соның арқасында алгоритмнің жалпы есептеу күрделілігі төмендейді. Көбейтудің қосалқы операцияларын Toom–Cook көбейтуін қайта-қайта қолданып, рекурсивті түрде есептеуге болады, және т.с.с. "Toom 3" және "Toom–Cook" терминдері кейде қате түрде бір-бірінің орнына қолданылса да, Toom 3 – бұл Toom–Cook алгоритмінің k = 3 болғандағы бір ғана жағдайы. Toom 3 тоғыз көбейтуді бесеуге дейін азайтады және Θ(n log(5) / log(3)) ≈ Θ(n1.46) уақыт ішінде жұмыс істейді. Жалпы, Toom k алгоритмі Θ(c(k) ne) уақытында жұмыс істейді, мұндағы 1 = e = log(2k − 1) / log(k), ne – қосалқы көбейтулерге кеткен уақыт, ал c – кіші тұрақтыларға көбейту және қосуға кеткен уақыт. Каратсуба алгоритмі Toom 2-ге баламалы, онда сан екі кішірек санға бөлінеді. Ол төрт көбейтуді үшке дейін азайтады және Θ(n log(3) / log(2)) ≈ Θ(n1.58) уақытында жұмыс істейді. Дәстүрлі ұзын көбейту Toom 1-ге баламалы, оның күрделілігі Θ(n2). e көрсеткішін k-ны арттыру арқылы 1-ге кез келген жақын мәнге орнатуға болатындықтан да, функцияның тұрақты мүшесі өте жылдам өседі. 2005 жылы аралас деңгейдегі Toom–Cook схемаларының өсу қарқыны зерттеу мәселесі ретінде ашық қалды. Дональд Кнут сипаттаған іске асыру уақыт күрделілігіне жетеді. Toom–Cook кішкентай сандармен ұзын көбейтуден баяу болғандықтан, ол әдетте орташа мөлшердегі көбейтулер үшін қолданылады, ал асимптотикалық жағынан жылдам Schönhage–Strassen алгоритмі (күрделілігі Θ(n log n log log n)) қолдануға ыңғайлы болғанда қолданылады. Тум бұл алгоритмді алғаш рет 1963 жылы сипаттады, ал Кук 1966 жылы докторлық диссертациясында жетілдірілген (асимптотикалық түрде баламалы) алгоритмді жариялады.
Toom–Cook, sometimes known as Toom 3, named after Andrei Toom, who introduced the new algorithm with its low complexity, and Stephen Cook, who cleaned the description of it, is a multiplication algorithm for large integers. Given two large integers, a and b, Toom–Cook splits up a and b into k smaller parts each of length l, and performs operations on the parts. As k grows, one may combine many of the multiplication sub operations, thus reducing the overall computational complexity of the algorithm. The multiplication sub operations can then be computed recursively using Toom–Cook multiplication again, and so on. Although the terms "Toom 3" and "Toom–Cook" are sometimes incorrectly used interchangeably, Toom 3 is only a single instance of the Toom–Cook algorithm, where k = 3. Toom 3 reduces nine multiplications to five, and runs in Θ(nlog(5)/log(3)) ≈ Θ(n1.46). In general, Toom k runs in Θ(c(k) ne), where 1=e = log(2k − 1) / log(k), ne is the time spent on sub multiplications, and c is the time spent on additions and multiplication by small constants. The Karatsuba algorithm is equivalent to Toom 2, where the number is split into two smaller ones. It reduces four multiplications to three and so operates at Θ(nlog(3)/log(2)) ≈ Θ(n1.58). Ordinary long multiplication is equivalent to Toom 1, with complexity Θ(n2). Although the exponent e can be set arbitrarily close to 1 by increasing k, the constant term in the function grows very rapidly. The growth rate for mixed level Toom–Cook schemes was still an open research problem in 2005. An implementation described by Donald Knuth achieves the time complexity
Due to its overhead, Toom–Cook is slower than long multiplication with small numbers, and it is therefore typically used for intermediate size multiplications, before the asymptotically faster Schönhage–Strassen algorithm (with complexity Θ(n log n log log n)) becomes practical. Toom first described this algorithm in 1963, and Cook published an improved (asymptotically equivalent) algorithm in his PhD thesis in 1966.
Түрлі k үшін интерполяциялық матрицалар
Мұнда біз km және kn-нің бірнеше әдеттегі кіші мәндері үшін жиі қолданылатын интерполяциялық матрицаларды келтіреміз.
Тоом-1
Том 1 (км = кн = 1) 1 бағалау нүктесін қажет етеді, осы үшін 0 таңдалды. Ол ұзын көбейтуге дейін төмендейді, интерполяциялық матрицасы бірлік матрицасы болып табылады:
Тоом-1,5
Том 1.5 (км = 2, kn = 1) 2 бағалау нүктесін қажет етеді, олар 0 және ∞ деп таңдалды. Оның интерполяциялық матрицасы – бірлік матрица:
Бұл да ұзақ көбейтуге дейін тоқырап кетеді: бір көбейткіштің екі коэффициенті де екінші көбейткіштің жалғыз коэффициентіне көбейтіледі.
Тоом-2
Том 2 (км = 2, kn = 2) үшін 3 бағалау нүктесі қажет, олар 0, 1 және ∞ деп таңдалды. Бұл Каратсуба көбейтуімен бірдей, интерполяциялық матрицасы:
Тоом-2.5
Тоом 2.5 (км = 3, kn = 2) 4 бағалау нүктесін қажет етеді, олар 0, 1, −1 және ∞ деп таңдалды. Оның интерполяциялық матрицасы: