দ্রুত বিপরীত বর্গমূল

দ্রুত বিপরীত বর্গমূল, যা কখনো Fast InvSqrt() বা হেক্সাডেসিমাল সংখ্যা পদ্ধতিতে 0x5F3759DF লিখা হয়, এটি এমন একটি অ্যালগরিদম যা 1/√x এর IEEE-৭৫৪ ফ্লোটিং পয়েন্ট বিন্যাসে ৩২-বিট ফ্লোটিং পয়েন্ট নম্বর x এর বর্গমূলের পারস্পরিক (বা গুণগত বিপরীত) মান বের করে। এই পদ্ধতিতে ডিজিটাল সিগন্যাল প্রক্রিয়াকরণে একটি ভেক্টরকে স্বাভাবিক করার জন্য ব্যবহার করা হয়, যেমন, একটি দৈর্ঘ্যের মান ১। উদাহরণস্বরূপ, কম্পিউটার গ্রাফিক্স প্রোগ্রামগুলি আলো এবং ছায়াকরণের ঘটনা এবং প্রতিফলনের কোণ গণনা করার জন্য বিপরীত বর্গমূল ব্যবহার করে। অ্যালগরিদমটি ১৯৯৯ সালে কোয়েক তৃতীয় এরিনার সোর্স কোডে বাস্তবায়ন করার জন্য সুপরিচিত, একটি মূখ্য শুটার ভিডিও গেম যা থ্রিডি গ্রাফিক্সের ব্যাপক ব্যবহার করে। অ্যালগরিদমটি শুধুমাত্র পাবলিক ফোরাম যেমন ইউজেনট ২০০২ বা ২০০৩-এ উপস্থাপন করা শুরু করে। সেই সময়ে, এটি সাধারণত গণনীয় মান মূল্যবান ছিল যা একটি ফ্লোটিং পয়েন্টের পারস্পরিক ক্রমবিন্যাস হিসেবে গণনা করা হত, বিশেষ করে বৃহৎ স্কেলে; দ্রুত বিপরীত বর্গমূল এই ধাপটি সহজেই পরিমাপ করে।
অ্যালগরিদম ইনপুট হিসাবে একটি ৩২ বিট ফ্লোটিং পয়েন্ট নম্বর গ্রহণ করে এবং পরবর্তী ব্যবহারের জন্য একটি আংশিক মান সঞ্চয় করে। তারপর, একটি পূর্ণসংখ্যা হিসাবে ৩২ বিট ফ্লোটিং পয়েন্ট নম্বরকে প্রতিনিধিত্ব করে, এক বিট দ্বারা একটি লজিকাল শিফট সঞ্চালিত হয় এবং ফলাফল থেকে ম্যাজিক নম্বর 0x5F3759DF থেকে বিয়োগ করা হয়। এটি ইনপুটটির বিপরীত বর্গমূলের প্রথম পরিমাপ। একটি ফ্লোটিং পয়েন্ট পয়েন্ট হিসাবে বিটটি নিউটন এর পদ্ধতির একটি পুনরাবৃত্তির সঞ্চালন করে আরো সুনির্দিষ্ট আসন্ন মান বের করা হয়।
অ্যালগরিদমটি মূলত আবিষ্কার করেন জন কারম্যাক, কিন্তু একটি তদন্ত এই তথ্য দেয় যে, কোডটি কম্পিউটার গ্রাফিক্স হার্ডওয়্যার এবং সফ্টওয়্যার উভয় দিক থেকেই গভীর সম্পর্ক খুঁজে পাওয়া যায়। সিলিকন গ্রাফিক্স ও ৩-ডিফএক্স ইন্টারেক্টিভ উভয় মাধ্যমেই পরিবর্তনগুলি সামঞ্জস্য, গ্যারি তরোলো এর এসজিআই নীল নকশার জন্য এটি বাস্তবায়ন করা হয়, যেগুলি সর্বপ্রথম ব্যবহার হিসাবে পরিচিত। ধ্রুবকটি মূলত কীভাবে উৎপন্ন হয়েছিল তা জানা যায় নি, যদিও তদন্তটি সম্ভাব্য পদ্ধতিগুলির উপর কিছুটা আলোকপাত করে।
একটি ফ্লোটিং পয়েন্ট নম্বরের বিপরীত বর্গমূল স্বাভাবিককৃত ভেক্টর দ্বারা গণনা করা হয়। প্রোগ্রামার ঘটনার এবং প্রতিফলন কোণ নির্ধারণ করার জন্য স্বাভাবিক চলক ব্যবহার করতে পারেন। থ্রিডি গ্রাফিক্স প্রোগ্রামগুলিতে প্রতি সেকেন্ডে লক্ষ লক্ষ সঞ্চালন করতে হবে যাতে আলোকে অনুকরণ করা যায়।১৯৯০ এর দশকের প্রথম দিকে যখন কোডটি উন্নত করা হয়েছিল, তখন অধিকাংশ ফ্লোটিং-পয়েন্ট প্রক্রিয়াকরণ শক্তি পূর্ণসংখ্যার প্রক্রিয়াকরণের গতির চেয়ে কম ছিল। এটি ট্রান্সফর্ম এবং আলোকে পরিচালিত বিশেষ হার্ডওয়্যারের আগমনের পূর্বে থ্রিডি গ্রাফিক্স প্রোগ্রামগুলির জন্য বিরক্তিকর ছিল।
ভেক্টর এর দৈর্ঘ্য তার ইউক্লিডীয় আদর্শ গণনা করে নির্ধারিত হয়: ভেক্টর উপাদানগুলির বর্গসমূহের যোগফলের বর্গমূল।যখন ভেক্টর প্রতিটি উপাদানটি সেই দৈর্ঘ্যের দ্বারা বিভক্ত হয়, তখন নতুন ভেক্টর একই দিক নির্দেশ করে একটি ইউনিট ভেক্টর হবে। একটি থ্রিডি গ্রাফিক্স প্রোগ্রামের মধ্যে, সমস্ত ভেক্টর ত্রিমাত্রিক স্থান হয়, তাই formula_1 একটি ভেক্টর হবে যার মান formula_2।
সেই সময়ে, ফ্লোটিং পয়েন্ট বিভাজন গুণের তুলনায় সাধারণত ব্যয়বহুল ছিল; দ্রুত বিপরীত বর্গমূল অ্যালগরিদম বিভাগের ধাপটি বাইপ করে, এটির পারফরম্যান্স সুবিধা প্রদান করে। একটি প্রথম-ব্যক্তি শুটার ভিডিও গেম কোয়েক তৃতীয় এরিনা গ্রাফিক গণনাকে দ্রুত গতিতে দ্রুত বাম পাশের রুট অ্যালগরিদম ব্যবহার করে, কিন্তু অ্যালগোরিদমটি কিছু নির্দিষ্ট হার্ডওয়্যার হেড্চাইন্ড শেডারগুলিতে ক্ষেত্র-প্রোগ্রামযোগ্য গেট অ্যারে (FPGA) ব্যবহার করে প্রয়োগ করা হয়েছে।
নিম্নোক্ত কোডটি হল কোয়েক তৃতীয় এরিনা থেকে দ্রুত বিপরীত বর্গমূলের বাস্তবায়ন, সি প্রসেসরের নির্দেশাবলী, কিন্তু যার মধ্যে সেখানে থাকা মূল মন্তব্যও দেওয়া হলো:
float Q_rsqrt( float number )
// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed
এক সময়, বিপরীত বর্গমূলের গণনা করার সাধারণ পদ্ধতি ছিল 1/√x এর জন্য একটি আনুমানিক মান হিসাব করা, তারপর প্রকৃত পদ্ধতির একটি গ্রহণযোগ্য ত্রুটির পরিসরের মধ্যে এটি না আসা পর্যন্ত অন্য পদ্ধতির মাধ্যমে অনুমানের পুনর্বিবেচনা করা। ১৯৯০ সালের প্রথম দিকে সাধারণ সফ্টওয়্যার পদ্ধতিগুলির একটি লজিক টেবিল থেকে আনুমানিক সূচনা করা হয়। দ্রুত বিপরীত বর্গমূলের মূলটি ছিল ফ্লোটিং-বিন্দুর সংখ্যার কাঠামো ব্যবহার করে সরাসরি একটি আনুমানিক মান হিসাব করা ও টেবিলে প্রদর্শনের চেয়ে দ্রুত প্রমাণ করা। অ্যালগরিদম চতুর্মাত্রিক পদ্ধতিতে অন্য পদ্ধতিতে গণনা করে এবং পারস্পরিক ক্রিয়াশীল ফ্লোটিং পয়েন্ট বিভাগের মান হিসাব করে, যা প্রায় চার গুণ বেশি দ্রুত। অ্যালগরিদম আইইইই ৭৫৪-১৯৮৫ 32-বিট ফ্লোটিং পয়েন্ট স্পেসিফিকেশন নিয়ে পরিকল্পিত ছিল, কিন্তু ক্রিস লোমোমেন্টের তদন্তে দেখা যায় এটি অন্যান্য ফ্লোটিং পয়েন্ট স্পেসিফিকেশনে প্রয়োগ করা যেতে পারে।
দ্রুত বিপরীত বর্গমূল ক্লডজ দ্বারা প্রদত্ত গতিতে সুবিধাটি দীর্ঘদিনের উপাত্ত থেকে এসেছিল যা একটি পূর্ণসংখ্যা হিসাবে ফ্লোটিং পয়েন্ট নম্বরটি ধারণ করে এবং তারপর এটি একটি নির্দিষ্ট ধ্রুবক (0x5F3759DF) থেকে বিয়োগ করে। ধ্রুবক সোর্স কোডটি দেখতে যাতে সহজ উপলব্দ হয়, তাই, কোডে পাওয়া যেমন অন্যান্য ধ্রুবকের মত, এটিকে প্রায়ই একটি জাদুকরী সংখ্যা বলা হয়। এই পূর্ণসংখ্যা বিয়োগ এবং বিট শিফ্টটি একটি লঙ্গনের মধ্যে ফলাফল যা একটি ফ্লোটিং পয়েন্ট সংখ্যা হিসাবে বিবেচনা করা হয় ইনপুট নম্বরের বিপরীত বর্গমূলের জন্য একটি আনুমানিক মান। নিউটন এর পুনরাবৃত্তির পদ্ধতি দ্বারা মানটি কিছুটা সঠিকতা অর্জন করে, এবং কোড শেষ হয়। অ্যালগরিদম নিউটন এর পদ্ধতির জন্য একটি অনন্য প্রথম পরিমাপ ব্যবহার করে যথোপযুক্ত ফলাফল উৎপন্ন করে; তবে ১৯৯৯ সালে মুক্তি পাওয়া x৮৬ প্রসেসরের উপর SSE নির্দেশনা codice_1 ব্যবহার করার চেয়ে এটি খুব ধীর এবং নিখুঁত।
সি স্ট্যান্ডার্ডগুলির পরিপ্রেক্ষিতে, বিটগুলির মাধ্যমে পূর্ণসংখ্যা হিসাবে একটি ফ্লোটিং পয়েন্ট মানকে পুনর্বিবেচনা করা অসম্পূর্ণ আচরণ বলে মনে করা হয়।দ্রুত বিপরীত বর্গমূলকে সাধারণ ভাবে সঠিক ভাবে সম্পন্ন করার জন্য, একটি আরো আদর্শ রূপান্তর পদ্ধতিতে, একটি ইউনিয়ন প্রকারের মাধ্যমে ফ্লোটিং পয়েন্ট মান এবং পূর্ণসংখ্যা টাইপ করা হয়। এটি একটি ইউনিয়ন টাইপ সঙ্গে সি++ এর মানের মধ্যে অনির্দিষ্ট আচরণ বিবেচনা করা হয় যে লক্ষ করা উচিত।
float Q_rsqrt( float number )
একটি উদাহরণ হিসাবে, সংখ্যা গণনা করতে ব্যবহার করা যেতে পারে। অ্যালগরিদম এর প্রথম ধাপ নিচে চিত্রিত করা হলো:
IEEE ৩২-bit ব্যবহার করে প্রদর্শনঃ
এই শেষ বিট প্যাটার্নটিকে একটি ফ্লোটিং পয়েন্ট নম্বর হিসাবে পুনর্বিন্যস্ত করে আনুমানিক সংখ্যা y = ২.৬১৪৮৬ হয়, যার মধ্যে প্রায় ৩.৪% ত্রুটি আছে। নিউটন এর পদ্ধতি একক পুনরাবৃত্তির পরে, চূড়ান্ত ফলাফল y = ২.৫২৫৪৯, যাতে শুধুমাত্র ০.১৭% ত্রুটি হয়।
অ্যালগরিদম নিম্নলিখিত পদক্ষেপগুলি সম্পাদন করে 1/√x এর মান গণনা করে:
যেহেতু এই অ্যালগরিদম একক-স্পষ্টতা ভাসমান পয়েন্ট সংখ্যাগুলির বিট-স্তরের প্রতিনিধিত্বের উপর ব্যাপকভাবে নির্ভর করে, এই উপস্থাপনাটির একটি সংক্ষিপ্ত সারাংশ এখানে প্রদান করা হয়েছে। অশূন্য আসল সংখ্যাটি x একক স্পষ্টতা ভলট হিসাবে এনকোড করার জন্য, প্রথম ধাপ হল xকে একটি স্বাভাবিক বাইনারি সংখ্যা হিসাবে লিখতে হবেঃ
যেখানে এর সূচক একটি পূর্ণসংখ্যা, এর "তাৎপর্যপূর্ণ" বাইনারি উপস্থাপনা , এবং । এটা উল্লেখ করা উচিত যে, যেহেতু তাৎপর্যপূর্ণ পয়েন্টের একক বিট হওয়ার পরেই সর্বদা ১ হয়, তাই এটি সংরক্ষণ করা প্রয়োজন হয় না। এই ফর্ম থেকে, তিনটি স্বাক্ষরবিহীন পূর্ণসংখ্যা গণনা করা হয়:
এই ক্ষেত্রটি তারপর, একটি বামদিক থেকে ডানদিকে 32 বিট মান দ্বারা পূর্ণ হয়।
একটি উদাহরণ হিসাবে, আবার বিবেচনা করে, "x" এর মান নির্ণয় করি,
এবং এইভাবে, তিনটি স্বাক্ষরবিহীন পূর্ণসংখ্যা ক্ষেত্র হল:
এই ক্ষেত্রগুলি নিচের চিত্রের মধ্যে দেখানো হলো:
যদি কোন কম্পিউটার বা ক্যালকুলেটর ছাড়াই 1/√x গণনা করা হয়, তবে লগারিদমের টেবিল এ ক্ষেত্রে উপযোগী হবে, তবে আডেন্টিটি লগ ) −½ log("x")}} দ্বারা মান নির্ণয় সম্ভব, যা প্রতিটি বেসের জন্য বৈধ। দ্রুত বিপরীত বর্গমূল এই পরিচয় উপর ভিত্তি করে, এবং যে একটি ফ্লোট-৩২ একটি পূর্ণসংখ্যা তার লগারিদমের একটি আনুমানিক মান দেয়। এখানে কীভাবে:
যদি x হল একটি ইতিবাচক স্বাভাবিক সংখ্যা:
তারপর আছে,
কিন্তু যেহেতু , ডানদিকে অবস্থিত লগারিদমের মান আনুমানিক হতে পারে,
যেখানে হল একটি নিখুঁত প্যারামিটার যা আদান প্রদানের জন্য ব্যবহৃত হয়। উদাহরণস্বরূপ, উৎপন্ন ব্যবধানের উভয় প্রান্তে সঠিক ফলাফল উৎপন্ন করে, যখন যথাযথ পরিমাপ (ত্রুটিটির ইউনিফর্ম আদর্শের অর্থে সেরা) উৎপন্ন করে।
এইভাবে আনুমানিক মানটি বের করা হয়।
অন্যদিকে, একটি পূর্ণসংখ্যা ফলন হিসাবে x এর বিট প্যাটার্ন ব্যাখ্যা,
এটি তখন দেখায় যে একটি শ্রেণিকৃত এবং স্থানান্তরিত রৈখিক এর পরিমাপকৃত মান, যা ডান পাশের চিত্রে অঙ্কিত। অন্য কথায়, দ্বারা অনুমিত হয়,
পরিচয়ের উপর ভিত্তি করে গণনা,
উপরের লগারিদমের আনুমানিক মান ব্যবহার করে, x এবং y উভয়ই প্রয়োগ করে, উপরের সমীকরণটি হয়:
সুতরাং, এর পরিমাপকৃত মান হলো:
সুতরাং, যা কোডে লেখা আছে,
i = 0x5f3759df - ( i » 1 );
উপরে প্রথম শব্দটি জাদু সংখ্যা,
যার থেকে এটি হতে পারে। দ্বিতীয় শব্দটি , যেখানে এক বিন্দুর ডানদিকে বিট স্থানান্তর করে গণনা করা হয়।
formula_24 কে বিপরীত বর্গমূল ধরে, formula_25। আগের ধাপগুলি দ্বারা প্রাপ্ত পরিমাপ, মূল খোঁজার পদ্ধতির ব্যবহার করে পরিমার্জিত করা যেতে পারে, এটি এমন একটি পদ্ধতি যা একটি ফাংনের শূন্য খুঁজে বের করে। বীজগণিতটি নিউটন এর পদ্ধতি ব্যবহার করে: যদি একটি পরিমাপ, y এর থাকে, তাহলে একটি ভাল আনুমানিক হিসাব formula_26 by taking formula_27 গণনা করা যাবে, যেখানে formula_28 এর ডেরিভেটিভটি formula_29 এর formula_30 হবে। উপরের formula_29, formula_32 যেখানে formula_33 এবং formula_34।
formula_24 কে ফ্লোটিং নম্বর ধরে, codice_2 এর সমতুল মান হলো formula_36। এই ধাপটি পুনরাবৃত্তি করে ফাংশনের আউটপুট (formula_26) ব্যবহার করে পরবর্তী পুনরাবৃত্তির ইনপুট হিসাব করা হয়, অ্যালগরিদমটি formula_24 এর বিপরীত বর্গমূলে রূপান্তরিত করে। কোয়েক তৃতীয় ইঞ্জিনের উদ্দেশ্যে শুধুমাত্র একটি পুনরাবৃত্তির জন্য ব্যবহার করা হয়েছিল। একটি দ্বিতীয় পুনরাবৃত্তির কোডে ছিল, কিন্তু মন্তব্যে যোগ করা হয়েছিল।
উপরে উল্লিখিত হিসাবে, আনুমানিক মান আশ্চর্যজনকভাবে সঠিক হয়। ০.০১ তে শুরু হওয়া ইনপুটগুলির জন্য ডান দিকে গ্রাফটি ফাংশনের ত্রুটি (অর্থাৎ, নিউটন এর পদ্ধতির একটি পুনরাবৃত্তির মাধ্যমে এটির উন্নতির পরে অতিক্রান্ততার ত্রুটি), যেখানে স্ট্যান্ডার্ড লাইব্রেরি ১০.০ মান দেয়, যখন InvSqrt() থেকে মান ৯.৯৮২২২২ হয়, তখন পার্থক্য হয় ০.০১৭৪৭৯, অথবা ০.১৭৫%। পরম ত্রুটিটি কেবল তখনই কেবল বেশি হয়, যখন আপেক্ষিক ত্রুটি পরিমাপের সমস্ত আদেশ জুড়ে একই সীমার মধ্যে থাকে।
কোয়েকন ২০০৫ পর্যন্ত কোয়েক-থ্রির জন্য সোর্স কোড প্রকাশিত হয় নি , কিন্তু ২০০৫ বা ২০০৩ সালের দিকে দ্রুত বিপরীত বর্গমূলের কোড ইউসনেট এবং অন্যান্য ফোরামে প্রকাশিত হয়। প্রচলিত ধারণা ছিল জন কারম্যাক সম্ভবত এই কোডের লেখক, কিন্তু তিনি বিনয়ী প্রকাশ করেন এবং এর লেখক হিসেবে তারজে ম্যাথেসেন এর নাম প্রস্তাব করেন, একটি সুশৃঙ্খল সমাবেশ প্রোগ্রামার হিসেবে যিনি ইতোমধ্যে কোয়েক অপ্টিমাইজেশান সঙ্গে আইডি সফ্টওয়্যার সাহায্য করেন। ম্যাথেসেন ১৯৯০ এর দশকের একটি অনুরূপ বিট কোড লেখেন, কিন্তু মূল লেখকগণ থ্রিডি কম্পিউটার গ্রাফিক্সের ইতিহাসে অনেক আগেই প্রমাণিত হয়েছিল যে গরি তেরোলি এর এসজিআই নীল এর কোড বাস্তবায়নের জন্য, যা হতে পারে এর সম্ভাব্য সর্বপ্রথম ব্যবহার। রেইস সমাফেল্ড উপসংহার টেনে বলেন যে মেটল্যাব এর আবিষ্কারক ক্লিভ মোলারের সঙ্গে পরামর্শ সঙ্গে আরডেন্ট কম্পিউটারে গ্রেগ ওয়ালশ দ্বারা মূল এলগরিদম উদ্ভাবিত হয়েছিল। ক্লিভ মোলার উইলিয়াম কাহন এবং কে.সি.-এর লিখিত কোড থেকে এই কৌশল সম্পর্ক জানতে পারেন।১৯৮৬ সালের দিকে বার্কলে এনএজি জিম ব্লিন আইইইইউ কম্পিউটার গ্রাফিক্স এবং অ্যাপ্লিকেশনের জন্য ১৯৯৭ সালে কলামের বিপরীত বর্গমূ্লের একটি সাধারণ পরিমাপ প্রদর্শন করেন। পল কিনে ১৯৮৬ এর কাছাকাছি সময়ে এফপিএসটি সিরিজ কম্পিউটারের জন্য একটি দ্রুত পদ্ধতি বাস্তবায়ন করেন। সিস্টেমটি ভেক্টর ফ্লোটিং পয়েন্ট হার্ডওয়্যার যা পূর্ণসংখ্যার অপারেশন সমৃদ্ধ ছিল না এবং অন্তর্ভুক্ত প্রাথমিক বিন্দু তৈরি করতে ম্যানিপুলেশন অনুমোদন করার জন্য ফ্লোটিং-পয়েন্ট মানগুলি শুরু হয়েছিল।
জাদুকরী সংখ্যাটি নির্ধারণের সঠিক মান কীভাবে নির্ধারিত হয়েছিল তা সঠিকভাবে জানা যায়নি। ক্রিস লোম্যান্ট একটি পরিসীমা্র উপর জাদু সংখ্যা R নির্বাচন করে আনুমানিক মানের ত্রুটি হ্রাস করেন। তিনি প্রথমে 0x5F37642F, 0x5F3759DF এর কাছাকাছি রৈখিক পরিমাপের ধাপের জন্য সর্বোত্তম ধ্রুবকটি গণনা করেছিলেন, কিন্তু এই নতুন ধ্রুবক নিউটনের পদ্ধতির পুনরাবৃত্তির পরে সামান্য কম সঠিকতা প্রদান করেছিলো। লোম্যান্ট তখন একের পর এক নিউটনের পুনরাবৃত্তির পরে ধ্রুবক অনুকূল অনুসন্ধান করেন এবং 0x5F375A86 পান, যা প্রতিটি পুনরাবৃত্তির পর্যায়ে মূল থেকে আরও সঠিক। আসল ধ্রুবকের সঠিক মূল্যটি ডেরিভেটিভেশন বা ট্রায়াল এবং ত্রুটির মধ্য দিয়ে নির্বাচিত হয়েছিল কি না তা নিয়ে তিনি উপসংহার টেনেছেন। লোম্যান্ট উল্লেখ করেছেন যে ৬৪ বিট আইআইইই-৭৫৭৫ আকারের টাইপ ডবল জাদু সংখ্যা 0x5FE6EC85E7DE30DA, কিন্তু এটি পরে ম্যাথু রবার্টসন দ্বারা সঠিক মান 0x5FE6EB50C7B537A9 দেখানো হয়েছিল।