Pairwise summation
આંકડાકીય વિશ્લેષણમાં, જોડી મુજબનો સરવાળો, જેને કાસ્કેડ સરવાળો પણ કહેવાય છે, તે મર્યાદિત-ચોકસાઇ ફ્લોટિંગ-પોઇન્ટ સંખ્યાઓના ક્રમનો સરવાળો કરવાની એક તકનીક છે જે અનુક્રમમાં સરવાળાને નિષ્કપટ રીતે એકઠા કરવાની સરખામણીમાં સંચિત રાઉન્ડ-ઓફ ભૂલને નોંધપાત્ર રીતે ઘટાડે છે. જો કે કાહન સરવાળો જેવી અન્ય તકનીકો છે જેમાં સામાન્ય રીતે નાની રાઉન્ડ-ઓફ ભૂલો હોય છે, જોડી મુજબનો સરવાળો લગભગ એટલો જ સારો છે (માત્ર લઘુગણક પરિબળ દ્વારા અલગ પડે છે) જ્યારે ગણતરીની કિંમત ઘણી ઓછી હોય છે-તેનો અમલ કરી શકાય છે જેથી લગભગ સમાન ખર્ચ (અને અંકગણિત કામગીરીની બરાબર સમાન સંખ્યા) નિષ્કપટ સરવાળો હોય. ખાસ કરીને, n સંખ્યાઓ xn ના ક્રમનો જોડી મુજબનો સરવાળો ક્રમને પુનરાવર્તિત રીતે બે ભાગમાં વિભાજીત કરીને, દરેક અડધા ભાગનો સરવાળો કરીને અને બે સરવાળો ઉમેરીને કામ કરે છેઃ એક વિભાજન અને વિજય અલ્ગોરિધમ. તેની સૌથી ખરાબ સ્થિતિ રાઉન્ડઓફ ભૂલો મહત્તમ O (ε લોગ n) તરીકે એસિમ્પ્ટોટિક રીતે વધે છે, જ્યાં ε એ મશીનની ચોકસાઇ છે (નીચે ચર્ચા કર્યા મુજબ નિશ્ચિત સ્થિતિ સંખ્યા ધારીને). તેની સરખામણીમાં, અનુક્રમમાં સરવાળો એકઠા કરવાની નિષ્કપટ તકનીક (i = 1,., n માટે એક સમયે દરેક xi ને ઉમેરવું) માં રાઉન્ડઓફ ભૂલો છે જે O (εn) તરીકે સૌથી ખરાબ રીતે વધે છે. કાહન સરવાળામાં લગભગ O (ε) ની સૌથી ખરાબ ભૂલ હોય છે, જે n થી સ્વતંત્ર હોય છે, પરંતુ તેમાં ઘણી વખત વધુ અંકગણિત કામગીરીની જરૂર પડે છે. જો રાઉન્ડઓફ ભૂલો રેન્ડમ હોય, અને ખાસ કરીને રેન્ડમ સંકેતો હોય, તો તે રેન્ડમ વોક બનાવે છે અને ભૂલ વૃદ્ધિ જોડી મુજબના સરવાળા માટે સરેરાશ સુધી ઘટાડવામાં આવે છે. સરવાળાનું ખૂબ જ સમાન પુનરાવર્તિત માળખું ઘણા ઝડપી ફોરિયર ટ્રાન્સફોર્મ (એફ. એફ. ટી.) અલ્ગોરિધમ્સમાં જોવા મળે છે, અને તે તે એફ. એફ. ટી. ના સમાન ધીમા રાઉન્ડઓફ સંચય માટે જવાબદાર છે. અલ્ગોરિધમ સ્યુડોકોડમાં, લંબાઈ ≤0 ના એરે માટે જોડી મુજબના સરવાળા અલ્ગોરિધમને લખી શકાય છેઃ s = જોડી મુજબ (x [1. n]) જો n ≤ N બેઝ કેસઃ પૂરતી નાની એરે માટે નિષ્કપટ સરવાળો s = 0 માટે i = 1 થી n s = s + x [i] અન્યથા વિભાજીત કરો અને જીતી લોઃ એરેના બે અર્ધભાગોનો પુનરાવર્તિત સરવાળો m = ફ્લોર (n/2) s = જોડી મુજબ (x [1. m]) + જોડી મુજબ (x [m + 1. n]) અંત જો કેટલાક પૂરતા પ્રમાણમાં નાના માટે, આ અલ્ગોરિધમ બેઝ કેસ તરીકે નિષ્કપટ લૂપ-આધારિત સરવાળા પર સ્વિચ કરે છે, જેની ભૂલ બાઉન્ડ O (Nε) છે. સમગ્ર રકમમાં સૌથી ખરાબ-કેસ ભૂલ હોય છે જે આપેલ શરત સંખ્યા માટે (નીચે જુઓ) મોટા n માટે O (ε log n) તરીકે એસિમ્પ્ટોટિક રીતે વધે છે. આ પ્રકારના અલ્ગોરિધમમાં (સામાન્ય રીતે વિભાજન અને વિજય અલ્ગોરિધમ્સ માટે), પુનરાવર્તનના ઓવરહેડને ઋણમુક્ત કરવા માટે મોટા બેઝ કેસનો ઉપયોગ કરવો ઇચ્છનીય છે. જો એન = 1 હોય, તો દરેક ઇનપુટ માટે આશરે એક પુનરાવર્તિત સબરૂટિન કૉલ હોય છે, પરંતુ વધુ સામાન્ય રીતે દરેક એન/2 ઇનપુટ્સ માટે (આશરે) એક પુનરાવર્તિત કૉલ હોય છે જો પુનરાવર્તન બરાબર એન = એન પર અટકે છે. એન ને પૂરતા પ્રમાણમાં મોટું બનાવીને, પુનરાવર્તનના ઓવરહેડને નગણ્ય બનાવી શકાય છે (ચોક્કસપણે પુનરાવર્તિત સારાંશ માટે મોટા બેઝ કેસની આ તકનીક ઉચ્ચ-પ્રદર્શન એફએફટી અમલીકરણ દ્વારા કાર્યરત છે). N ને ધ્યાનમાં લીધા વિના, બરાબર n − 1 ઉમેરાઓ કુલ મળીને કરવામાં આવે છે, જે નિષ્કપટ સરવાળા માટે સમાન છે, તેથી જો પુનરાવર્તન ઓવરહેડને નગણ્ય બનાવવામાં આવે તો જોડી મુજબના સરવાળા અનિવાર્યપણે નિષ્કપટ સરવાળા માટે સમાન ગણતરી ખર્ચ ધરાવે છે. આ વિચાર પરની વિવિધતા એ છે કે દરેક પુનરાવર્તિત તબક્કે સરવાળાને b બ્લોકમાં વિભાજિત કરવી, દરેક બ્લોકનો પુનરાવર્તિત સરવાળો કરવો, અને પછી પરિણામોનો સરવાળો કરવો, જેને તેના પ્રસ્તાવકો દ્વારા "સુપરબ્લોક" અલ્ગોરિધમ તરીકે ઓળખવામાં આવ્યું હતું. ઉપરોક્ત જોડી મુજબનું અલ્ગોરિધમ છેલ્લા તબક્કા સિવાય દરેક તબક્કા માટે b = 2 ને અનુરૂપ છે જે b = N છે. ચોકસાઈ ધારો કે એક n મૂલ્યો xi નો સરવાળો છે, i = 1,., n માટે. ચોક્કસ સરવાળો છેઃ (અનંત ચોકસાઇ સાથે ગણવામાં આવે છે). બેઝ કેસ N = 1 માટે જોડી મુજબના સરવાળા સાથે, તેના બદલે એક પ્રાપ્ત થાય છે, જ્યાં ભૂલ ઉપર આ રીતે બંધાયેલ છેઃ જ્યાં ε એ ઉપયોગમાં લેવાતા અંકગણિતની મશીનની ચોકસાઇ છે (દા. ત. પ્રમાણભૂત ડબલ ચોકસાઇ ફ્લોટિંગ પોઇન્ટ માટે ε ≈ 10−16). સામાન્ય રીતે, વ્યાજની માત્રા એ સાપેક્ષ ભૂલ હોય છે, જે તેથી ઉપર આ રીતે બંધાયેલી હોય છેઃ સાપેક્ષ ભૂલ માટે બંધાયેલ અભિવ્યક્તિમાં, અપૂર્ણાંક ( નિષ્પન્ન |xi |/|Σxi |) એ સારાંશ સમસ્યાની શરત સંખ્યા છે. અનિવાર્યપણે, શરત સંખ્યા ભૂલો માટે સારાંશ સમસ્યાની આંતરિક સંવેદનશીલતાને રજૂ કરે છે, પછી ભલે તેની ગણતરી કેવી રીતે કરવામાં આવે. નિશ્ચિત ચોકસાઇમાં નિશ્ચિત અલ્ગોરિધમ દ્વારા દરેક (પછાત સ્થિર) સરવાળા પદ્ધતિની સંબંધિત ભૂલ બંધાયેલ છે (એટલે કે. જે લોકો મનસ્વી-ચોકસાઇવાળા અંકગણિતનો ઉપયોગ કરે છે, કે એલ્ગોરિધમ્સ કે જેમની મેમરી અને સમયની જરૂરિયાતો ડેટાના આધારે બદલાય છે), તે આ શરત સંખ્યાના પ્રમાણસર નથી. બિન-શરતી સરવાળાની સમસ્યા એ છે કે જેમાં આ ગુણોત્તર મોટો હોય અને આ કિસ્સામાં જોડી મુજબના સરવાળામાં પણ મોટી સાપેક્ષ ભૂલ હોઈ શકે છે. ઉદાહરણ તરીકે, જો xi સરવાળા શૂન્ય સરેરાશ સાથે અસંબંધિત રેન્ડમ સંખ્યાઓ હોય, તો સરવાળો એક રેન્ડમ વોક છે અને શરત સંખ્યા તેના પ્રમાણસર વધશે. બીજી બાજુ, બિન-શૂન્ય સાથે રેન્ડમ ઇનપુટ્સ માટે અર્થ એ છે કે મર્યાદિત અચળાંકની સ્થિતિ સંખ્યા એસિમ્પ્ટોટ્સ તરીકે છે. જો તમામ ઇનપુટ્સ બિન-નકારાત્મક હોય, તો શરત નંબર 1 છે. નોંધ લો કે વ્યવહારમાં છેદ અસરકારક રીતે 1 છે, કારણ કે જ્યાં સુધી n એ 21/ε ક્રમનો ન બને ત્યાં સુધી તે 1 કરતા ઘણો નાનો હોય છે, જે બમણી ચોકસાઇમાં આશરે 101015 છે. તેની સરખામણીમાં, નિષ્કપટ સરવાળા માટે બંધાયેલી સાપેક્ષ ભૂલ (ફક્ત અનુક્રમમાં સંખ્યાઓ ઉમેરવી, દરેક તબક્કે ગોળાકાર કરવી) સ્થિતિ સંખ્યા દ્વારા ગુણાકાર તરીકે વધે છે. વ્યવહારમાં, તે વધુ સંભવ છે કે ગોળાકાર ભૂલો શૂન્ય સરેરાશ સાથે રેન્ડમ સંકેત ધરાવે છે, જેથી તેઓ રેન્ડમ વોક બનાવે છે; આ કિસ્સામાં, નિષ્કપટ સરવાળામાં મૂળ સરેરાશ ચોરસ સંબંધિત ભૂલ હોય છે જે વધે છે અને જોડી મુજબના સરવાળામાં એક ભૂલ હોય છે જે સરેરાશ વધે છે. સોફ્ટવેર અમલીકરણ જોડી મુજબનો સરવાળો એ ન્યુમ્પી અને જુલિયા ટેકનિકલ-કમ્પ્યુટિંગ ભાષામાં મૂળભૂત સરવાળો અલ્ગોરિધમ છે, જ્યાં બંને કિસ્સાઓમાં તે નિષ્કપટ સરવાળો (મોટા બેઝ કેસના ઉપયોગને કારણે) સાથે તુલનાત્મક ઝડપ ધરાવતો હોવાનું જણાયું હતું. અન્ય સોફ્ટવેર અમલીકરણમાં સી #ભાષા માટે એચ. પી. સી. શાર્પ લાઈબ્રેરી અને ડી. સંદર્ભોમાં પ્રમાણભૂત લાઈબ્રેરી સારાંશનો સમાવેશ થાય છે.