Addition-subtraction chain
একটি যোগ-বিয়োগ শৃঙ্খল, বিয়োগ অন্তর্ভুক্ত করার জন্য যোগ শৃঙ্খলের একটি সাধারণীকরণ, একটি ক্রম a0, a1, a2, a3, যা সন্তুষ্ট করে। অর্থাৎ, এর মাধ্যমে কেউ n বাই L সংযোজন এবং/অথবা বিয়োগ গণনা করতে পারে। (মনে রাখবেন যে n ধনাত্মক হওয়ার প্রয়োজন নেই। এই ক্ষেত্রে, ক্রমটিতে a − 1 = 0 অন্তর্ভুক্ত করা যেতে পারে, যাতে n = − 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 (বাইনারি)। অন্যান্য হার্ডওয়্যার গুণকগুলি বুথ এনকোডিংয়ে এন দ্বারা বর্ণিত একটি সংযোজন-বিয়োগ শৃঙ্খল ব্যবহার করে এন দ্বারা গুণ করেঃ এন = 31 = 0 0 1 0 0 0 0 − 1 (বুথ এনকোডিং)। তথ্যসূত্র সংযোজন শৃঙ্খল