Кіріспе
Көбейту алгоритмі
Шёнгаге-Страссен алгоритмі – Арнольд Шёнгаге мен Волкер Страссен 1971 жылы жариялаған үлкен бүтін сандар үшін асимптотикалық жылдамдыққа ие көбейту алгоритмі. Ол 2n+1 модульді бүтін сандарға қатысты жылдам Фурье түрлендіруін (FFT) рекурсивті қолдану арқылы жұмыс істейді. Алгоритмді пайдаланып екі n цифрлі санды көбейтудің біт күрделілігі үлкен O белгісімен көрсетіледі. Шёнгаге-Страссен алгоритмі 1971 жылдан 2007 жылға дейін белгілі болған асимптотикалық жағынан ең жылдам көбейту әдісі болды. Бұл Каратсуба және Тум-Кук көбейтуі сияқты бұрынғы әдістерден асимптотикалық тұрғыдан жылдам, және шамамен 10 000 – 100 000 ондық цифрдан астам сандар үшін іс жүзінде олардан жоғары өнімділік көрсетеді. 2007 жылы Мартин Фюрер одан да жылдам асимптотикалық күрделілікке ие алгоритм жариялады. 2019 жылы Дэвид Харви мен Жорис ван дер Ховен көп цифрлы көбейтудің теориялық күрделілігін көрсетті; алайда, олардың алгоритмі тұрақты факторларға ие, бұл оны кез келген нақты практикалық мәселе үшін қолдануды мүмкін емес етеді (галактикалық алгоритмді қараңыз). Шёнгаге-Страссен алгоритмінің қолданылу аясы – өздері үшін жасалған үлкен есептеулер, мысалы, Ұлы Интернет Мерсендік алғашқы сандарды іздеу және π-нің жуықтамасы, сондай-ақ Кронеккер алмастыру арқылы Ленстра эллиптік қисықтарын факторизациялау сияқты практикалық қолданыстар, бұл полиномдық көбейтуді бүтін сан көбейтуге дейін азайтады.
Сипаттама
Бұл бөлімде алгоритмнің оңайлатылған нұсқасы келтірілген, онда екі табиғи санның көбейтіндісін есептеу көрсетілген, модуль – белгілі бір тұрақты сан. Бүтін сандар биттердің блоктарына бөлінеді, сондықтан практикалық іске асыруда параметрлер арасында дұрыс тепе-теңдікті табу маңызды. Қандай жағдайда болса да, бұл алгоритм екі оң бүтін санды көбейтуге мүмкіндік береді, егер таңдалған болса, онда сигналдардағы биттер саны және , мұндағы – екінің дәрежесі. Сигналдар мен сигналдарды әрқайсысы биттен тұратын блоктарға бөліп, нәтижедегі блоктарды массивтер ретінде сақтаймыз (олардың элементтерін қарапайымдық үшін кез келген дәлдіктегі бүтін сандар ретінде қарастырамыз). Енді Фурье түрлендіруі үшін модулді келесідей таңдаймыз. Сондай-ақ , және массивтердің элементтерін (кез келген дәлдіктегі) бүтін сандар модулі ретінде қарастырайық. Ескеріңіз, өйткені , модуль көбейтуден туындаған кез келген ауысуларды қабылдауға жеткілікті үлкен, сондықтан көбейтінді (модуль ) Фурье түрлендіруінің конволюциясын есептеу арқылы шығарылады. Сондай-ақ, , сондықтан – бірліктің примитивті түбірі модуль бойынша.
Let be the number of bits in the signals and , where is a power of two. Divide the signals and into blocks of bits each, storing the resulting blocks as arrays (whose entries we shall consider for simplicity as arbitrary precision integers). We now select a modulus for the Fourier transform, as follows. Let be such that Also put , and regard the elements of the arrays as (arbitrary precision) integers modulo Observe that since , the modulus is large enough to accommodate any carries that can result from multiplying and Thus, the product (modulo ) can be calculated by evaluating the convolution of Also, with , we have , and so is a primitive th root of unity modulo
We now take the discrete Fourier transform of the arrays in the ring , using the root of unity for the Fourier basis, giving the transformed arrays Because is a power of two, this can be achieved in logarithmic time using a fast Fourier transform. Let (pointwise product), and compute the inverse transform of the array , again using the root of unity The array is now the convolution of the arrays Finally, the product is given by evaluating
This basic algorithm can be improved in several ways. Firstly, it is not necessary to store the digits of to arbitrary precision, but rather only up to bits, which gives a more efficient machine representation of the arrays Secondly, it is clear that the multiplications in the forward transforms are simple bit shifts. With some care, it is also possible to compute the inverse transform using only shifts. Taking care, it is thus possible to eliminate any true multiplications from the algorithm except for where the pointwise product is evaluated. It is therefore advantageous to select the parameters so that this pointwise product can be performed efficiently, either because it is a single machine word or using some optimized algorithm for multiplying integers of a (ideally small) number of words. Selecting the parameters is thus an important area for further optimization of the method.
Енді біз массивтердің дискретті Фурье түрлендірмесін сақинада аламыз , Фурье негізі үшін бірліктің түбірін пайдалана отырып, түрлендірілген массивтерді аламыз. – екінің дәрежесі болғандықтан, бұл логарифмдік уақытта жылдам Фурье түрлендірмесін пайдаланып жүзеге асырылуы мүмкін. (нүктелік көбейтінді) деп белгілейміз және массивтің кері түрлендірмесін қайтадан бірліктің түбірін пайдалана отырып есептейміз. Массив енді массивтердің конволюциясы болып табылады. Ақырында, көбейтіндіні бағалау арқылы шығаруға болады.
Let be the number of bits in the signals and , where is a power of two. Divide the signals and into blocks of bits each, storing the resulting blocks as arrays (whose entries we shall consider for simplicity as arbitrary precision integers). We now select a modulus for the Fourier transform, as follows. Let be such that Also put , and regard the elements of the arrays as (arbitrary precision) integers modulo Observe that since , the modulus is large enough to accommodate any carries that can result from multiplying and Thus, the product (modulo ) can be calculated by evaluating the convolution of Also, with , we have , and so is a primitive th root of unity modulo
We now take the discrete Fourier transform of the arrays in the ring , using the root of unity for the Fourier basis, giving the transformed arrays Because is a power of two, this can be achieved in logarithmic time using a fast Fourier transform. Let (pointwise product), and compute the inverse transform of the array , again using the root of unity The array is now the convolution of the arrays Finally, the product is given by evaluating
This basic algorithm can be improved in several ways. Firstly, it is not necessary to store the digits of to arbitrary precision, but rather only up to bits, which gives a more efficient machine representation of the arrays Secondly, it is clear that the multiplications in the forward transforms are simple bit shifts. With some care, it is also possible to compute the inverse transform using only shifts. Taking care, it is thus possible to eliminate any true multiplications from the algorithm except for where the pointwise product is evaluated. It is therefore advantageous to select the parameters so that this pointwise product can be performed efficiently, either because it is a single machine word or using some optimized algorithm for multiplying integers of a (ideally small) number of words. Selecting the parameters is thus an important area for further optimization of the method.
Бұл негізгі алгоритмді бірнеше жолмен жақсартуға болады. Біріншіден, сандардың цифрларын кез келген дәлдікпен сақтаудың қажеті жоқ, бірақ тек битке дейін, бұл массивтерді машинада тиімдірек бейнелеуге мүмкіндік береді. Екіншіден, алға түрлендірудегі көбейтулер қарапайым биттерді жылдырулар екені анық. Сақтықпен, кері түрлендіруді тек жылдыруларды қолдана отырып есептеуге де болады. Сақтық танытса, алгоритмнен нақты көбейтулерді толығымен жоюға болады, тек нүктелік көбейтінді бағаланған кезде ғана. Сондықтан параметрлерді тиімді нүктелік көбейтіндіні орындау үшін таңдау тиімді, өйткені бұл бір машина сөзі немесе (идеалды жағдайда аз) сөздердің бүтін сандарын көбейту үшін кейбір оңтайландырылған алгоритмді қолдану. Параметрлерді таңдау – әдісті одан әрі оңтайландыру үшін маңызды сала болып табылады.
Let be the number of bits in the signals and , where is a power of two. Divide the signals and into blocks of bits each, storing the resulting blocks as arrays (whose entries we shall consider for simplicity as arbitrary precision integers). We now select a modulus for the Fourier transform, as follows. Let be such that Also put , and regard the elements of the arrays as (arbitrary precision) integers modulo Observe that since , the modulus is large enough to accommodate any carries that can result from multiplying and Thus, the product (modulo ) can be calculated by evaluating the convolution of Also, with , we have , and so is a primitive th root of unity modulo
We now take the discrete Fourier transform of the arrays in the ring , using the root of unity for the Fourier basis, giving the transformed arrays Because is a power of two, this can be achieved in logarithmic time using a fast Fourier transform. Let (pointwise product), and compute the inverse transform of the array , again using the root of unity The array is now the convolution of the arrays Finally, the product is given by evaluating
This basic algorithm can be improved in several ways. Firstly, it is not necessary to store the digits of to arbitrary precision, but rather only up to bits, which gives a more efficient machine representation of the arrays Secondly, it is clear that the multiplications in the forward transforms are simple bit shifts. With some care, it is also possible to compute the inverse transform using only shifts. Taking care, it is thus possible to eliminate any true multiplications from the algorithm except for where the pointwise product is evaluated. It is therefore advantageous to select the parameters so that this pointwise product can be performed efficiently, either because it is a single machine word or using some optimized algorithm for multiplying integers of a (ideally small) number of words. Selecting the parameters is thus an important area for further optimization of the method.
Қосымша зерттеу
Қолданылу ерекшеліктері туралы мәліметтерді "Prime Numbers: A Computational Perspective" кітабынан оқуға болады. Бұл нұсқа Шёнгагедің бастапқы әдісінен кейбір жағынан өзгешеленеді, себебі ол дискретті салмақты түрлендіруді негациклді конволюцияларды тиімдірек жүзеге асыру үшін қолданады. Толық ақпарат алу үшін тағы бір дереккөз – Кнуттың "Компьютерлік бағдарламалау өнері" кітабы.
Оңтайландырулар
Бұл бөлім Schönhage–Strassen алгоритмін іске асырғандағы бірнеше маңызды практикалық оңтайландыруларды түсіндіреді.
Басқа көбейту алгоритмін қолдану, ішкі алгоритм
Белгілі бір шектен төмен болса, басқа көбейту алгоритмдерін, мысалы, Toom-Cook көбейтуін қолдану тиімдірек.
2 амалдың квадрат түбірі
Бұл идея – NTT (саны теориялық түрлендіру) тәсілінде мәндерді салмақтағанда, шекті өрістегі реттік бірліктің түбірі ретінде пайдалану. Бұл, теңдеудің шешімі болып табылады. Осы тәсіл бүтін сандарды көбейтуге жұмсалатын уақытты 10%-ға үнемдеуге мүмкіндік береді.