Gosper's algorithm
গণিতে, বিল গস্পারের কারণে গস্পারের অ্যালগরিদম হল হাইপারজিওমেট্রিক পদগুলির সমষ্টি খুঁজে বের করার একটি পদ্ধতি যা নিজেই হাইপারজিওমেট্রিক পদ। অর্থাৎঃ ধরুন একজনের একটি (1) +. + a (n) = S (n) −S (0) আছে, যেখানে S (n) একটি হাইপারজিওমেট্রিক শব্দ (অর্থাৎ, S (n + 1)/S (n) হল n-এর একটি মূলদ ফাংশন); তাহলে অবশ্যই a (n) নিজেই একটি হাইপারজিওমেট্রিক শব্দ, এবং a (n)-এর সূত্র দেওয়া থাকলে গস্পারের অ্যালগরিদম S (n)-এর জন্য তা খুঁজে পায়। প্রথম ধাপঃ একটি বহুপদী p খুঁজে বের করুন যাতে b (n) = a (n)/p (n) লিখে, b (n)/b (n − 1) অনুপাতের q (n)/r (n) ফর্ম থাকে যেখানে q এবং r বহুপদী এবং কোন q (n)-এর r (n + j) সহ একটি অ-তুচ্ছ গুণক থাকে না, যা j = 0,1,2,। (সিরিজটি বদ্ধ আকারে যোগযোগ্য হোক বা না হোক, এটি সর্বদা সম্ভব।) ধাপ 2: একটি বহুপদী খুঁজে বের করুন যাতে S (n) = q (n + 1)/p (n) f (n) a (n) হয়। যদি সিরিজটি বদ্ধ আকারে যোগযোগ্য হয় তবে স্পষ্টতই এই বৈশিষ্ট্যের সাথে একটি যুক্তিসঙ্গত ফাংশন f বিদ্যমান; আসলে এটি অবশ্যই সর্বদা একটি বহুপদী হতে হবে এবং এর মাত্রার উপরের সীমা পাওয়া যাবে। f নির্ধারণ করা (অথবা এমন কোন f নেই তা খুঁজে বের করা) তখন রৈখিক সমীকরণের একটি পদ্ধতি সমাধান করার বিষয়। উইলফ-জেইলবার্গার জোড়ার সাথে সম্পর্ক গস্পারের অ্যালগরিদম উইলফ-জেইলবার্গার জোড়া আবিষ্কার করতে ব্যবহার করা যেতে পারে, যেখানে তারা বিদ্যমান। ধরুন যে F (n + 1, k) − F (n, k) = G (n, k + 1) − G (n, k) যেখানে F পরিচিত কিন্তু G নয়। তারপর গস্পারের অ্যালগরিদমে a (k): = F (n + 1, k) − F (n, k) যোগ করুন। (এটিকে k এর একটি ফাংশন হিসাবে বিবেচনা করুন যার সহগগুলি সংখ্যার পরিবর্তে n এর ফাংশন হতে পারে; অ্যালগরিদমের সবকিছু এই সেটিংয়ে কাজ করে। যদি এটি সফলভাবে S (k) কে S (k) − S (k − 1) = a (k) সহ খুঁজে পায়, তাহলে আমাদের কাজ শেষ হবেঃ এটি প্রয়োজনীয় G। যদি তা না হয়, তবে এমন কোনও G নেই। ডেফিনিট বনাম অনির্দিষ্ট যোগফল গস্পারের অ্যালগরিদম (যেখানে সম্ভব) হাইপারজিওমেট্রিক পদগুলির অনির্দিষ্ট যোগফলের জন্য একটি হাইপারজিওমেট্রিক বদ্ধ রূপ খুঁজে পায়। এটি ঘটতে পারে যে এমন কোনও বদ্ধ রূপ নেই, তবে সমস্ত n-এর উপর যোগফল বা n-এর মানগুলির কোনও নির্দিষ্ট সেটের একটি বদ্ধ রূপ রয়েছে। এই প্রশ্নটি তখনই অর্থপূর্ণ হয় যখন সহগগুলি নিজেই অন্য কোনও চলকের ফাংশন হয়। সুতরাং, ধরুন a (n, k) হল n এবং k উভয়ের মধ্যে একটি হাইপারজিওমেট্রিক পদঃ অর্থাৎ, a (n, k)/a (n−1, k) এবং a (n, k)/a (n, k−1) হল n এবং k-এর মূলদ ফাংশন। বিল গস্পার 1970-এর দশকে সেল এবং এম. আই. টি-তে ম্যাক্সিমা কম্পিউটার বীজগণিত পদ্ধতিতে কাজ করার সময় এই অ্যালগরিদমটি আবিষ্কার করেছিলেন। তথ্যসূত্র কম্পিউটার বীজগণিত হাইপারজিওমেট্রিক ফাংশন