Schönhage–Strassen algorithm
સ્કોનહેજ-સ્ટ્રાસેન અલ્ગોરિધમ એ મોટા પૂર્ણાંકો માટે એસિમ્પ્ટોટિકલી ઝડપી ગુણાકાર અલ્ગોરિધમ છે, જે 1971માં આર્નોલ્ડ સ્કોનહેજ અને વોલ્કર સ્ટ્રાસેન દ્વારા પ્રકાશિત કરવામાં આવ્યું હતું. તે પૂર્ણાંકો મોડ્યુલો 2n + 1 પર ઝડપી ફોરિયર ટ્રાન્સફોર્મ (FFT) ને પુનરાવર્તિત રીતે લાગુ કરીને કામ કરે છે. અલ્ગોરિધમનો ઉપયોગ કરીને બે આંકડાની સંખ્યાઓનો ગુણાકાર કરવા માટે રન-ટાઇમ બીટ જટિલતા મોટા સંકેતલિપીમાં છે. સ્કોનહેજ-સ્ટ્રાસેન અલ્ગોરિધમ 1971 થી 2007 સુધી જાણીતી એસિમ્પ્ટોટિકલી સૌથી ઝડપી ગુણાકાર પદ્ધતિ હતી. તે કારાત્સુબા અને ટૂમ-કૂક ગુણાકાર જેવી જૂની પદ્ધતિઓ કરતાં એસિમ્પ્ટોટિક રીતે ઝડપી છે, અને લગભગ 10,000 થી 100,000 દશાંશ અંકોથી વધુની સંખ્યાઓ માટે વ્યવહારમાં તેમને પાછળ છોડવાનું શરૂ કરે છે. 2007 માં, માર્ટિન ફ્યુરરે ઝડપી એસિમ્પ્ટોટિક જટિલતા સાથે એક અલ્ગોરિધમ પ્રકાશિત કર્યું. 2019 માં, ડેવિડ હાર્વે અને જોરિસ વાન ડેર હોવેને દર્શાવ્યું હતું કે બહુ-અંકના ગુણાકારમાં સૈદ્ધાંતિક જટિલતા હોય છે; જો કે, તેમના અલ્ગોરિધમમાં સતત પરિબળો હોય છે જે તેને કોઈપણ કલ્પનીય વ્યવહારુ સમસ્યા માટે અશક્ય રીતે ધીમું બનાવે છે (ગેલેક્ટિક અલ્ગોરિધમ જુઓ). સ્કોનહેજ-સ્ટ્રાસેન અલ્ગોરિધમનો ઉપયોગ તેમના પોતાના માટે કરવામાં આવેલી મોટી ગણતરીઓ જેમ કે ગ્રેટ ઈન્ટરનેટ મર્સેન પ્રાઇમ સર્ચ અને તેના અંદાજો, તેમજ ક્રોનેકર અવેજી દ્વારા લેન્સ્ટ્રા લંબગોળ વળાંક પરિબળકરણ જેવા વ્યવહારુ ઉપયોગોનો સમાવેશ કરે છે, જે બહુપદી ગુણાકારને પૂર્ણાંક ગુણાકારમાં ઘટાડે છે. વર્ણન આધાર B માં દરેક સંખ્યાને બહુપદી તરીકે લખી શકાય છેઃ વધુમાં, બે સંખ્યાઓના ગુણાકારને બે બહુપદીઓના ગુણાકાર તરીકે વિચારી શકાય છેઃ કારણ કે, માટેઃ, આપણી પાસે કોન્વોલ્યુશન છે. એફએફટી (ફાસ્ટ ફોરિયર ટ્રાન્સફોર્મ) નો ઉપયોગ કરીને, જેનો ઉપયોગ એનટીટીને બદલે મૂળ સંસ્કરણમાં થાય છે, કન્વોલ્યુશન નિયમ સાથે; આપણે મેળવીએ છીએ. એટલે કે;, જ્યાં ફોરિયર સ્પેસમાં અનુરૂપ ગુણાંક છે. આને આ રીતે પણ લખી શકાય છેઃ fft (a * b) = fft (a) ● fft (b). ફોરિયર ટ્રાન્સફોર્મ હેઠળ રેખીયતાને કારણે આપણી પાસે સમાન ગુણાંક છે, અને કારણ કે આ બહુપદીઓમાં ગુણાંક દીઠ માત્ર એક અનન્ય શબ્દનો સમાવેશ થાય છેઃ અને કન્વોલ્યુશન નિયમઃ આપણે એફ. એફ. ટી. દ્વારા આપણી કન્વોલ્યુશન સમસ્યાને ઉત્પાદન સમસ્યામાં ઘટાડી છે. દરેક માટે આઇ. એફ. એફ. ટી. (બહુપદી અંતર્વેશન) શોધવાથી, ઇચ્છિત ગુણાંક મળે છે. એલ્ગોરિધમ સમસ્યાને પેટા સમસ્યાઓમાં વિભાજિત કરવા માટે વિભાજીત કરો અને જીતી લો વ્યૂહરચનાનો ઉપયોગ કરે છે. મોડ એન હેઠળ કન્વોલ્યુશન, જ્યાં અને સ્કોનહેજ-સ્ટ્રાસેન અલ્ગોરિધમમાં. દોઃ અને, n-th રુટ ક્યાં છે તે જુઓઃ આનો અર્થ એ છે કે, કોઈ વ્યક્તિ વજનનો ઉપયોગ કરી શકે છે, અને પછી પછી સાથે ગુણાકાર કરી શકે છે. વજનનો ઉપયોગ કરવાને બદલે; પુનરાવર્તનના પ્રથમ તબક્કામાં (ક્યારે), ગણતરી કરી શકાય છેઃ સામાન્ય એફ. એફ. ટી. માં, જે જટિલ સંખ્યાઓ પર કામ કરે છે, તેનો ઉપયોગ કરી શકાય છેઃ જો કે, એફ. એફ. ટી. નો ઉપયોગ સ્કોનહેજ-સ્ટ્રાસેનમાં એનટીટી (સંખ્યા સૈદ્ધાંતિક પરિવર્તન) તરીકે પણ થઈ શકે છે. આનો અર્થ એ છે કે આપણે તેનો ઉપયોગ કરવો પડશે જે મર્યાદિત ક્ષેત્રમાં સંખ્યાઓ ઉત્પન્ન કરે છે (ઉદાહરણ તરીકે). મર્યાદિત ક્ષેત્ર હેઠળ એકતાનું મૂળ એ એક તત્વ છે જે અથવા. ઉદાહરણ તરીકે, જ્યાં પ્રાઇમ છે, તે આપે છે. તેની અંદર અને અંદર નોંધ લો. આ કેન્ડીએડેટ્સ માટે, તેના મર્યાદિત ક્ષેત્ર હેઠળ, અને તેથી આપણે જે રીતે ઈચ્છીએ તે રીતે કાર્ય કરો. જો કે, જ્યાં સુધી મર્યાદિત ક્ષેત્રની એકતાનું મૂળ હોય ત્યાં સુધી સમાન એફ. એફ. ટી. અલ્ગોરિધમ્સનો ઉપયોગ કરી શકાય છે. એફ. એફ. ટી./એન. ટી. ટી. પરિવર્તન શોધવા માટે, આપણે નીચે મુજબ કરીએ છીએઃ પ્રથમ ઉત્પાદન દરેક માટે યોગદાન આપે છે. બીજું યોગદાન આપે છે, મોડને કારણે. ઇન્વર્સ કરવા માટેઃ અથવા એફએફટી નોર્મલાઇઝ ડેટાનો ઉપયોગ કરે છે કે નહીં તેના આધારે. એક દ્વારા ગુણાકાર કરો, એફએફટી ડેટાને ચોક્કસ શ્રેણીમાં સામાન્ય બનાવવા માટે, જ્યાં મોડ, જ્યાં મોડ્યુલર મલ્ટિપ્લિકેટિવ ઇન્વર્સનો ઉપયોગ કરીને જોવા મળે છે. અમલીકરણની વિગતો શા માટે એન = 2 + 1 મોડ એનમાં સ્કોનહેજ-સ્ટ્રાસેન અલ્ગોરિધમમાં,. કોઈએ આને દ્વિસંગી વૃક્ષ તરીકે વિચારવું જોઈએ, જેમાં મૂલ્ય હોય છે. પરવાનગી આપીને, દરેક વ્યક્તિ માટે બધા શોધી શકાય છેઃ એક વ્યક્તિ તમામ જોડીને M જુદા જુદા જૂથોમાં જૂથબદ્ધ કરી શકે છે. કોન્વોલ્યુશન દ્વારા જોડીઓને જૂથબદ્ધ કરવા માટે ઉપયોગ કરવો, એલ્ગોરિધમ્સમાં એક શાસ્ત્રીય સમસ્યા છે. ઉદાહરણ તરીકેઃ ધારો કે k એ કુલ આવક છે અને તે પુરુષની આવક અને સ્ત્રીની આવક છે; કોન્વોલ્યુશનનો ઉપયોગ કરીને, ઇચ્છિત કુલ આવકના આધારે જૂથમાં જૂથબદ્ધ કરી શકાય છે. આને ધ્યાનમાં રાખીને, આપણને જૂથોમાં જૂથબદ્ધ કરવામાં મદદ કરો, ઊંડાણમાં પેટા કાર્યોના દરેક જૂથ માટે; વૃક્ષમાં નોંધ લો કે, કેટલાક એલ માટે. આ ફર્મેટ નંબર છે. મોડ કરતી વખતે, આપણી પાસે ફર્મેટ રીંગ નામનું કંઈક હોય છે. કારણ કે કેટલીક ફર્મેટ સંખ્યાઓ ફર્મેટ અવિભાજ્ય સંખ્યાઓ છે, કેટલાક કિસ્સાઓમાં ગણતરીઓ ટાળી શકાય છે. ત્યાં અન્ય N છે જેનો ઉપયોગ કરી શકાયો હોત, અલબત્ત, સમાન મુખ્ય સંખ્યાના ફાયદાઓ સાથે. બીટ્સ સાથે દ્વિસંગી સંખ્યામાં મહત્તમ સંખ્યા હોય છે. એક મર્સેન સંખ્યા છે, જે કેટલાક કિસ્સાઓમાં મર્સેન અવિભાજ્ય છે. તે ફર્મેટ નંબર સામે એક કુદરતી ઉમેદવાર છે અન્ય એન ની શોધમાં વિવિધ સામે ઘણી મોડ ગણતરીઓ કરવી, જ્યારે પૂર્ણાંક ઉત્પાદનને ઉકેલવાની વાત આવે ત્યારે તે મદદરૂપ થઈ શકે છે. ચાઇનીઝ શેષ પ્રમેયનો ઉપયોગ કરીને, નાના વિવિધ પ્રકારોમાં વિભાજિત થયા પછી, કોઈ વ્યક્તિ ગુણાકારનો જવાબ શોધી શકે છે ફર્મેટ સંખ્યાઓ અને મર્સેન સંખ્યાઓ માત્ર બે પ્રકારની સંખ્યાઓ છે, જેને સામાન્યીકૃત ફર્મેટ મર્સેન સંખ્યા (જી. એસ. એમ.) કહેવાય છે; સૂત્ર સાથેઃ આ સૂત્રમાં; એક ફર્મેટ સંખ્યા છે, અને તે એક મર્સેન સંખ્યા છે. આ સૂત્રનો ઉપયોગ સમીકરણોના સમૂહો પેદા કરવા માટે થઈ શકે છે, જેનો ઉપયોગ સી. આર. ટી. (ચાઇનીઝ રિમેન્ડર થીયરમ) માં થઈ શકે છેઃ, જ્યાં એવી સંખ્યા છે કે જ્યાં અસ્તિત્વમાં છે, એમ ધારીને; વધુમાં, જ્યાં એક તત્વ છે જે તત્વોને ચક્રીય રીતે ઉત્પન્ન કરે છે. જો, ક્યાં, પછી. ચોક્કસ N માટે K કેવી રીતે પસંદ કરવું તે નીચેનું સૂત્ર કાર્યક્ષમતાની ગણતરી કરીને આપેલ બીટ કદને યોગ્ય (બિટ્સને વિભાજિત કરવા માટે જૂથોની સંખ્યા) શોધવામાં મદદ કરે છેઃ સૌથી બાહ્ય સ્તરે બીટ કદ (જેમાં વપરાય છે) છે. બિટ્સના જૂથો આપે છે, જ્યાં. તેના દ્વારા અને તેના દ્વારા સૌથી નાનું શોધી શકાય છે, જેમ કે જો કોઈ વ્યક્તિ 50 ટકાથી ઉપરની કાર્યક્ષમતા ધારણ કરે છે, અને બાકીના સૂત્રની તુલનામાં તે ખૂબ જ નાનું હોય; તો તે મેળવે છે આનો અર્થઃ જ્યારે કંઈક ખૂબ જ અસરકારક હોય છે; તે સ્યુડોકોડ દ્વારા ઉપર બંધાયેલ હોય અથવા એસિમ્પ્ટોટિકલી દ્વારા ઉપર બંધાયેલ હોય ત્યારે નીચેના અંકગણિત, પ્રમાણભૂત મોડ્યુલર સ્કોનહેજ-સ્ટ્રાસેન ગુણાકાર અલ્ગોરિધમ (કેટલાક ઓપ્ટિમાઇઝેશન સાથે), ટી3એમયુએલ = ટૂમ-કૂક ગુણાકાર એસ. એમ. યુ. એલ. = સ્કોનહેજ-સ્ટ્રાસેન ગુણાકાર મૂલ્યાંકન = એફ. એફ. ટી./આઇ. એફ. એફ. ટી. દ્વારા ઝાંખીમાં જોવા મળે છે. આ પ્રકાર સ્કોનહેજની મૂળ પદ્ધતિથી કંઈક અંશે અલગ છે કારણ કે તે નકારાત્મક ચક્રીય કોન્વોલ્યુશનને વધુ અસરકારક રીતે કરવા માટે સ્વતંત્ર ભારિત પરિવર્તનનો ઉપયોગ કરે છે. વિગતવાર માહિતી માટેનો બીજો સ્રોત ક્નુથની ધ આર્ટ ઓફ કમ્પ્યુટર પ્રોગ્રામિંગ છે. ઓપ્ટિમાઇઝેશન આ વિભાગ સ્કોનહેજ-સ્ટ્રાસેનનો અમલ કરતી વખતે સંખ્યાબંધ મહત્વપૂર્ણ વ્યવહારુ ઓપ્ટિમાઇઝેશન સમજાવે છે. અલ્ગોરિધમની અંદર અન્ય ગુણાકાર અલ્ગોરિધમનો ઉપયોગ ચોક્કસ કટઓફ બિંદુની નીચે, અન્ય ગુણાકાર અલ્ગોરિધમનો ઉપયોગ કરવો વધુ કાર્યક્ષમ છે, જેમ કે ટૂમ-કૂક ગુણાકાર. 2 યુક્તિનું વર્ગમૂળ એન. ટી. ટી. (સંખ્યા સૈદ્ધાંતિક પરિવર્તન) માં મૂલ્યોને ભારિત કરતી વખતે મર્યાદિત ક્ષેત્રમાં ક્રમની એકતાના મૂળ તરીકે ઉપયોગ કરવાનો વિચાર છે (તે સમીકરણનો ઉકેલ છે). તે પૂર્ણાંક ગુણાકાર સમયમાં 10 ટકાની બચત કરે છે તેવું દર્શાવવામાં આવ્યું છે. ગ્રાનલુન્ડની યુક્તિ દોડીને; કોઈ ગણતરી કરી શકે છે અને. ગુણાકાર સંદર્ભોના ચોક્કસ મૂલ્યો શોધવા માટે સી. આર. ટી. (ચાઇનીઝ રિમેઇન્ડર પ્રમેય) સાથે સંયોજનમાં કોમ્પ્યુટર અંકગણિત અલ્ગોરિધમ્સ ગુણાકાર