Addition-subtraction chain
સરવાળો-બાદબાકી સાંકળ, બાદબાકીનો સમાવેશ કરવા માટે સરવાળો સાંકળોનું સામાન્યીકરણ, એ ક્રમ a0, a1, a2, a3 છે. જે સંતોષ આપે છે. લંબાઈ L ની n માટે સરવાળો-બાદબાકી સાંકળ એ સરવાળો-બાદબાકી સાંકળ છે. એટલે કે, કોઈ વ્યક્તિ એન દ્વારા એલ ઉમેરાઓ અને/અથવા બાદબાકીની ગણતરી કરી શકે છે. (નોંધ કરો કે n હકારાત્મક હોવું જરૂરી નથી. આ કિસ્સામાં, અનુક્રમમાં a − 1 = 0 નો પણ સમાવેશ કરી શકાય છે, જેથી n = − 1 લંબાઈ 1 ની સાંકળ દ્વારા મેળવી શકાય. વ્યાખ્યા મુજબ, દરેક ઉમેરા સાંકળ પણ એક ઉમેરા-બાદબાકી સાંકળ છે, પરંતુ તેનાથી ઊલટું નહીં. તેથી, n માટે ટૂંકી સરવાળો-બાદબાકી સાંકળની લંબાઈ ઉપર n માટે ટૂંકી સરવાળો સાંકળની લંબાઈ દ્વારા બંધાયેલી હોય છે. સામાન્ય રીતે, જો કે, ન્યૂનતમ સરવાળો-બાદબાકી સાંકળનું નિર્ધારણ (જેમ કે લઘુત્તમ સરવાળો સાંકળ નક્કી કરવાની સમસ્યા) એક મુશ્કેલ સમસ્યા છે જેના માટે હાલમાં કોઈ કાર્યક્ષમ અલ્ગોરિધમ્સ જાણીતા નથી. શ્રેષ્ઠ ઉમેરા ક્રમ શોધવાની સંબંધિત સમસ્યા એન. પી.-પૂર્ણ (ડાઉની એટ અલ., 1981) છે, પરંતુ તે ચોક્કસપણે જાણીતું નથી કે શ્રેષ્ઠ ઉમેરા અથવા ઉમેરા-બાદબાકીની સાંકળો શોધવી એ એન. પી.-હાર્ડ છે કે કેમ. ઉદાહરણ તરીકે, એક ઉમેરા-બાદબાકીની સાંકળ છેઃ,,, છે. જો કે, n = 3 માટે આ લઘુતમ ઉમેરા-બાદબાકીની સાંકળ નથી, કારણ કે આપણે તેના બદલે પસંદ કરી શક્યા હોત. સૌથી નાનો n કે જેના માટે સરવાળો-બાદબાકી સાંકળ ન્યૂનતમ સરવાળો સાંકળ કરતાં ટૂંકી હોય છે તે n = 31 છે, જેની ગણતરી માત્ર 6 ઉમેરાઓમાં કરી શકાય છે (ન્યૂનતમ સરવાળો સાંકળ માટે 7 ને બદલે): સરવાળો સાંકળની જેમ, સરવાળો-બાદબાકી સાંકળનો ઉપયોગ સરવાળો સાંકળ ઘાતાંક માટે થઈ શકે છેઃ n માટે લંબાઈ L ની સરવાળો-બાદબાકી સાંકળને જોતાં, શક્તિની ગણતરી x L વખતથી ગુણાકાર અથવા ભાગાકાર કરીને કરી શકાય છે, જ્યાં બાદબાકી વિભાગોને અનુરૂપ હોય છે. આ એવી સમસ્યાઓમાં સંભવિત રીતે કાર્યક્ષમ છે જ્યાં વિભાજન એક સસ્તી કામગીરી છે, ખાસ કરીને લંબગોળ વળાંક પર ઘાતાંક માટે જ્યાં વિભાજન માત્ર સંકેત પરિવર્તનને અનુરૂપ છે (મોરેન અને ઓલિવોસ દ્વારા પ્રસ્તાવિત, 1990). કેટલાક હાર્ડવેર ગુણકો દ્વિસંગીમાં n દ્વારા વર્ણવેલ વધારાની સાંકળનો ઉપયોગ કરીને n દ્વારા ગુણાકાર કરે છેઃ n = 31 = 0 0 0 1 1 1 (દ્વિસંગી). અન્ય હાર્ડવેર ગુણકો બૂથ એન્કોડિંગમાં n દ્વારા વર્ણવેલ સરવાળો-બાદબાકી સાંકળનો ઉપયોગ કરીને n દ્વારા ગુણાકાર કરે છેઃ n = 31 = 0 0 1 0 0 0 0 − 1 (બૂથ એન્કોડિંગ). સંદર્ભો ઉમેરો સાંકળો