Pairwise summation
সংখ্যাসূচক বিশ্লেষণে, জোড়া-ভিত্তিক যোগফল, যাকে ক্যাসকেড যোগফলও বলা হয়, সসীম-নির্ভুলতা ভাসমান-বিন্দু সংখ্যার একটি ক্রমের যোগফল করার একটি কৌশল যা সরলভাবে ক্রমের যোগফলের তুলনায় সঞ্চিত বৃত্তাকার ত্রুটিকে যথেষ্ট পরিমাণে হ্রাস করে। যদিও কাহান যোগফলের মতো অন্যান্য কৌশল রয়েছে যা সাধারণত আরও ছোট রাউন্ড-অফ ত্রুটি থাকে, তবে জোড় ভিত্তিক যোগফল প্রায় ততটাই ভাল (শুধুমাত্র একটি লগারিদমিক ফ্যাক্টর দ্বারা পৃথক) যদিও গণনামূলক খরচ অনেক কম-এটি প্রয়োগ করা যেতে পারে যাতে প্রায় একই খরচ হয় (এবং গাণিতিক ক্রিয়াকলাপের ঠিক একই সংখ্যা) সরল যোগফলের মতো। বিশেষত, n সংখ্যা xn-এর একটি ক্রমের জোড়াবিশিষ্ট যোগফল ক্রমটিকে পুনরাবৃত্তভাবে দুটি অর্ধে বিভক্ত করে, প্রতিটি অর্ধের যোগফল করে এবং দুটি যোগফল যোগ করে কাজ করেঃ একটি বিভাজন এবং জয় অ্যালগরিদম। এর সবচেয়ে খারাপ-কেস রাউন্ডঅফ ত্রুটিগুলি সর্বাধিক ও (ε লগ এন) হিসাবে অ্যাসিম্পটোটিকভাবে বৃদ্ধি পায়, যেখানে ε হল মেশিনের নির্ভুলতা (একটি নির্দিষ্ট শর্ত সংখ্যা ধরে নেওয়া, যেমন নীচে আলোচনা করা হয়েছে)। তুলনায়, বিন্যাসে যোগফল সংগ্রহ করার সরল কৌশলটিতে (i = 1,., n-এর জন্য একটি সময়ে প্রতিটি xi যোগ করা) বৃত্তাকার ত্রুটি রয়েছে যা O (εn) হিসাবে সবচেয়ে খারাপ হারে বৃদ্ধি পায়। কাহান সংকলনে মোটামুটিভাবে ও (ε)-এর সবচেয়ে খারাপ-কেস ত্রুটি রয়েছে, যা এন-এর থেকে স্বাধীন, তবে এর জন্য বেশ কয়েকগুণ বেশি গাণিতিক ক্রিয়াকলাপের প্রয়োজন হয়। যদি রাউন্ডঅফ ত্রুটিগুলি এলোমেলো হয়, এবং বিশেষত এলোমেলো লক্ষণ থাকে, তবে তারা একটি এলোমেলো হাঁটা তৈরি করে এবং জোড়ার যোগফলের জন্য ত্রুটির বৃদ্ধি গড়ে হ্রাস পায়। অনেক দ্রুত ফুরিয়ার রূপান্তর (এফ. এফ. টি) অ্যালগরিদমে যোগফলের একটি খুব অনুরূপ পুনরাবৃত্তিমূলক কাঠামো পাওয়া যায় এবং সেই এফ. এফ. টিগুলির একই ধীরগতির বৃত্তাকার সঞ্চয়ের জন্য দায়ী। অ্যালগরিদমটি সিউডোকোডে, দৈর্ঘ্যের একটি অ্যারের জন্য জোড়া-ভিত্তিক সমষ্টি অ্যালগরিদমটি লেখা যেতে পারেঃ 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 = 2-এর সাথে মিলে যায়, শেষ পর্যায়টি ছাড়া যা b = N। নির্ভুলতা ধরুন যে একটি n মান xi যোগ করছে, i = 1,., n-এর জন্য। সঠিক যোগফলটি হলঃ (অসীম নির্ভুলতার সাথে গণনা করা হয়েছে)। একটি বেস কেস N = 1-এর জন্য জোড়াবিশিষ্ট যোগফলের সাথে, পরিবর্তে একটি প্রাপ্ত হয়, যেখানে ত্রুটিটি উপরে দ্বারা আবদ্ধ থাকেঃ যেখানে ε হল গাণিতিক প্রয়োগের যন্ত্রের নির্ভুলতা (যেমন। ε ≈ 10−16 স্ট্যান্ডার্ড ডাবল নির্ভুলতা ভাসমান বিন্দুর জন্য)। সাধারণত, সুদের পরিমাণ আপেক্ষিক ত্রুটি, যা তাই উপরে দ্বারা আবদ্ধ থাকেঃ আপেক্ষিক ত্রুটির জন্য অভিব্যক্তিতে, ভগ্নাংশ (с |xi।/|Σxi।) হল যোগফল সমস্যার শর্ত সংখ্যা। মূলত, শর্ত সংখ্যাটি কীভাবে গণনা করা হয় তা নির্বিশেষে ত্রুটির প্রতি সমষ্টি সমস্যার অভ্যন্তরীণ সংবেদনশীলতার প্রতিনিধিত্ব করে। নির্দিষ্ট নির্ভুলতায় একটি নির্দিষ্ট অ্যালগরিদম দ্বারা প্রতিটি (পশ্চাৎমুখী স্থিতিশীল) সমষ্টি পদ্ধতির আপেক্ষিক ত্রুটি আবদ্ধ (অর্থাৎ। যারা নির্বিচারে-নির্ভুলতা গাণিতিক ব্যবহার করে না, অথবা অ্যালগরিদম যাদের মেমরি এবং সময়ের প্রয়োজনীয়তা তথ্যের উপর ভিত্তি করে পরিবর্তিত হয়), এই শর্ত সংখ্যার সাথে আনুপাতিক নয়। একটি অ-শর্তযুক্ত যোগফল সমস্যা হল এমন একটি সমস্যা যেখানে এই অনুপাতটি বড়, এবং এই ক্ষেত্রে জোড়াবিশিষ্ট যোগফলের একটি বড় আপেক্ষিক ত্রুটি থাকতে পারে। উদাহরণস্বরূপ, যদি যোগফল xi শূন্য গড় সহ অসংলগ্ন এলোমেলো সংখ্যা হয়, তবে যোগফলটি একটি এলোমেলো হাঁটা এবং শর্ত সংখ্যাটি এর সাথে আনুপাতিকভাবে বৃদ্ধি পাবে। অন্যদিকে, অ-শূন্য সহ র্যান্ডম ইনপুটগুলির জন্য শর্ত সংখ্যাটি একটি সীমাবদ্ধ ধ্রুবক হিসাবে অ্যাসিম্পটোট বোঝায়। যদি সমস্ত ইনপুট অ-নেতিবাচক হয়, তবে শর্ত সংখ্যাটি হল 1। লক্ষ্য করুন যে কার্যত হরটি কার্যকরভাবে 1, যেহেতু 1 এর চেয়ে অনেক ছোট যতক্ষণ না n 21/ε ক্রমে পরিণত হয়, যা দ্বিগুণ নির্ভুলতায় প্রায় 101015 হয়। তুলনায়, সরল যোগফলের জন্য আবদ্ধ আপেক্ষিক ত্রুটি (কেবল ক্রমানুসারে সংখ্যা যোগ করা, প্রতিটি ধাপে বৃত্তাকার করা) শর্ত সংখ্যা দ্বারা গুণিত হিসাবে বৃদ্ধি পায়। বাস্তবে, এটি অনেক বেশি সম্ভব যে বৃত্তাকার ত্রুটির একটি এলোমেলো চিহ্ন রয়েছে, শূন্য গড় সহ, যাতে তারা একটি এলোমেলো হাঁটা গঠন করে; এই ক্ষেত্রে, সরল যোগফলের একটি মূল গড় বর্গ আপেক্ষিক ত্রুটি রয়েছে যা বৃদ্ধি পায় এবং জোড়াবিশিষ্ট যোগফলের একটি ত্রুটি রয়েছে যা গড় হিসাবে বৃদ্ধি পায়। সফ্টওয়্যার বাস্তবায়ন যুগ্মভাবে যোগফল হল ন্যাম্পাই এবং জুলিয়া টেকনিক্যাল-কম্পিউটিং ভাষার ডিফল্ট যোগফল অ্যালগরিদম, যেখানে উভয় ক্ষেত্রেই এটির সরল যোগফলের সাথে তুলনীয় গতি পাওয়া গেছে (একটি বড় বেস কেস ব্যবহারের জন্য ধন্যবাদ)। অন্যান্য সফ্টওয়্যার বাস্তবায়নের মধ্যে রয়েছে সি #ভাষার জন্য এইচপিসি শার্প লাইব্রেরি এবং ডি-তে স্ট্যান্ডার্ড লাইব্রেরি যোগফল।