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

দ্রুত বিপরীত বর্গমূল, যা কখনো Fast InvSqrt() বা হেক্সাডেসিমাল সংখ্যা পদ্ধতিতে 0x5F3759DF লিখা হয়, এটি এমন একটি অ্যালগরিদম যা 1/√x এর IEEE-৭৫৪ ফ্লোটিং পয়েন্ট বিন্যাসে ৩২-বিট ফ্লোটিং পয়েন্ট নম্বর x এর বর্গমূলের পারস্পরিক (বা গুণগত বিপরীত) মান বের করে। এই পদ্ধতিতে ডিজিটাল সিগন্যাল প্রক্রিয়াকরণে একটি ভেক্টরকে স্বাভাবিক করার জন্য ব্যবহার করা হয়, যেমন, একটি দৈর্ঘ্যের মান ১। উদাহরণস্বরূপ, কম্পিউটার গ্রাফিক্স প্রোগ্রামগুলি আলো এবং ছায়াকরণের ঘটনা এবং প্রতিফলনের কোণ গণনা করার জন্য বিপরীত বর্গমূল ব্যবহার করে। অ্যালগরিদমটি ১৯৯৯ সালে কোয়েক তৃতীয় এরিনার সোর্স কোডে বাস্তবায়ন করার জন্য সুপরিচিত, একটি মূখ্য শুটার ভিডিও গেম যা থ্রিডি গ্রাফিক্সের ব্যাপক ব্যবহার করে। অ্যালগরিদমটি শুধুমাত্র পাবলিক ফোরাম যেমন ইউজেনট ২০০২ বা ২০০৩-এ উপস্থাপন করা শুরু করে।^[১]^{[note ১]} সেই সময়ে, এটি সাধারণত গণনীয় মান মূল্যবান ছিল যা একটি ফ্লোটিং পয়েন্টের পারস্পরিক ক্রমবিন্যাস হিসেবে গণনা করা হত, বিশেষ করে বৃহৎ স্কেলে; দ্রুত বিপরীত বর্গমূল এই ধাপটি সহজেই পরিমাপ করে।

অ্যালগরিদম ইনপুট হিসাবে একটি ৩২ বিট ফ্লোটিং পয়েন্ট নম্বর গ্রহণ করে এবং পরবর্তী ব্যবহারের জন্য একটি আংশিক মান সঞ্চয় করে। তারপর, একটি পূর্ণসংখ্যা হিসাবে ৩২ বিট ফ্লোটিং পয়েন্ট নম্বরকে প্রতিনিধিত্ব করে, এক বিট দ্বারা একটি লজিকাল শিফট সঞ্চালিত হয় এবং ফলাফল থেকে ম্যাজিক নম্বর 0x5F3759DF থেকে বিয়োগ করা হয়। এটি ইনপুটটির বিপরীত বর্গমূলের প্রথম পরিমাপ। একটি ফ্লোটিং পয়েন্ট পয়েন্ট হিসাবে বিটটি নিউটন এর পদ্ধতির একটি পুনরাবৃত্তির সঞ্চালন করে আরো সুনির্দিষ্ট আসন্ন মান বের করা হয়।

অ্যালগরিদমটি মূলত আবিষ্কার করেন জন কারম্যাক, কিন্তু একটি তদন্ত এই তথ্য দেয় যে, কোডটি কম্পিউটার গ্রাফিক্স হার্ডওয়্যার এবং সফ্টওয়্যার উভয় দিক থেকেই গভীর সম্পর্ক খুঁজে পাওয়া যায়। সিলিকন গ্রাফিক্স ও ৩-ডিফএক্স ইন্টারেক্টিভ উভয় মাধ্যমেই পরিবর্তনগুলি সামঞ্জস্য, গ্যারি তরোলো এর এসজিআই নীল নকশার জন্য এটি বাস্তবায়ন করা হয়, যেগুলি সর্বপ্রথম ব্যবহার হিসাবে পরিচিত। ধ্রুবকটি মূলত কীভাবে উৎপন্ন হয়েছিল তা জানা যায় নি, যদিও তদন্তটি সম্ভাব্য পদ্ধতিগুলির উপর কিছুটা আলোকপাত করে।

প্রেরণা

একটি ফ্লোটিং পয়েন্ট নম্বরের বিপরীত বর্গমূল স্বাভাবিককৃত ভেক্টর দ্বারা গণনা করা হয়।^[৩] প্রোগ্রামার ঘটনার এবং প্রতিফলন কোণ নির্ধারণ করার জন্য স্বাভাবিক চলক ব্যবহার করতে পারেন। থ্রিডি গ্রাফিক্স প্রোগ্রামগুলিতে প্রতি সেকেন্ডে লক্ষ লক্ষ সঞ্চালন করতে হবে যাতে আলোকে অনুকরণ করা যায়।১৯৯০ এর দশকের প্রথম দিকে যখন কোডটি উন্নত করা হয়েছিল, তখন অধিকাংশ ফ্লোটিং-পয়েন্ট প্রক্রিয়াকরণ শক্তি পূর্ণসংখ্যার প্রক্রিয়াকরণের গতির চেয়ে কম ছিল।^[১] এটি ট্রান্সফর্ম এবং আলোকে পরিচালিত বিশেষ হার্ডওয়্যারের আগমনের পূর্বে থ্রিডি গ্রাফিক্স প্রোগ্রামগুলির জন্য বিরক্তিকর ছিল।

ভেক্টর এর দৈর্ঘ্য তার ইউক্লিডীয় আদর্শ গণনা করে নির্ধারিত হয়: ভেক্টর উপাদানগুলির বর্গসমূহের যোগফলের বর্গমূল।যখন ভেক্টর প্রতিটি উপাদানটি সেই দৈর্ঘ্যের দ্বারা বিভক্ত হয়, তখন নতুন ভেক্টর একই দিক নির্দেশ করে একটি ইউনিট ভেক্টর হবে। একটি থ্রিডি গ্রাফিক্স প্রোগ্রামের মধ্যে, সমস্ত ভেক্টর ত্রিমাত্রিক স্থান হয়, তাই ${\boldsymbol {v}}$ একটি ভেক্টর হবে যার মান $(v_{1},v_{2},v_{3})$ ।

\|{\boldsymbol {v}}\|={\sqrt {v_{1}^{2}+v_{2}^{2}+v_{3}^{2}}}

এটি ভেক্টর ইউক্লিডীয় আদর্শ.

{\boldsymbol {\hat {v}}}={\boldsymbol {v}}/\|{\boldsymbol {v}}\|

সাধারণ (ইউনিট) ভেক্টর হয়.

\|{\boldsymbol {v}}\|^{2}

বুঝায় যে

v_{1}^{2}+v_{2}^{2}+v_{3}^{2}

.

{\boldsymbol {\hat {v}}}={\boldsymbol {v}}/{\sqrt {\|{\boldsymbol {v}}\|^{2}}}

, যা দূরত্ব উপাদানগুলির বিপরীত বর্গমূলের ইউনিট ভেক্টর সম্পর্কিত। বিপরীত বর্গমূলটি গণনা করতে ব্যবহার করা যেতে পারে

{\boldsymbol {\hat {v}}}

কারণ এই সমীকরণের সমতুল্য হয়

{\boldsymbol {v}}\,{\frac {1}{\sqrt {\|{\boldsymbol {v}}\|^{2}}}}

, যখন

{\frac {1}{\sqrt {\|{\boldsymbol {v}}\|^{2}}}}

এর বিপরীত বর্গমূল হল

\|{\boldsymbol {v}}\|^{2}

.

সেই সময়ে, ফ্লোটিং পয়েন্ট বিভাজন গুণের তুলনায় সাধারণত ব্যয়বহুল ছিল; দ্রুত বিপরীত বর্গমূল অ্যালগরিদম বিভাগের ধাপটি বাইপ করে, এটির পারফরম্যান্স সুবিধা প্রদান করে। একটি প্রথম-ব্যক্তি শুটার ভিডিও গেম কোয়েক তৃতীয় এরিনা গ্রাফিক গণনাকে দ্রুত গতিতে দ্রুত বাম পাশের রুট অ্যালগরিদম ব্যবহার করে, কিন্তু অ্যালগোরিদমটি কিছু নির্দিষ্ট হার্ডওয়্যার হেড্চাইন্ড শেডারগুলিতে ক্ষেত্র-প্রোগ্রামযোগ্য গেট অ্যারে (FPGA) ব্যবহার করে প্রয়োগ করা হয়েছে। ^[৪]

কোডের সংক্ষিপ্ত বিবরণ

নিম্নোক্ত কোডটি হল কোয়েক তৃতীয় এরিনা থেকে দ্রুত বিপরীত বর্গমূলের বাস্তবায়ন, সি প্রসেসরের নির্দেশাবলী, কিন্তু যার মধ্যে সেখানে থাকা মূল মন্তব্যও দেওয়া হলো:^[৫]

float Q_rsqrt( float number )
{
	long i;
	float x2, y;
	const float threehalfs = 1.5F;

	x2 = number * 0.5F;
	y  = number;
	i  = * ( long * ) &y;                       // evil floating point bit level hacking
	i  = 0x5f3759df - ( i >> 1 );               // what the fuck? 
	y  = * ( float * ) &i;
	y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//	y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

	return y;
}

এক সময়, বিপরীত বর্গমূলের গণনা করার সাধারণ পদ্ধতি ছিল 1/√x এর জন্য একটি আনুমানিক মান হিসাব করা, তারপর প্রকৃত পদ্ধতির একটি গ্রহণযোগ্য ত্রুটির পরিসরের মধ্যে এটি না আসা পর্যন্ত অন্য পদ্ধতির মাধ্যমে অনুমানের পুনর্বিবেচনা করা। ১৯৯০ সালের প্রথম দিকে সাধারণ সফ্টওয়্যার পদ্ধতিগুলির একটি লজিক টেবিল থেকে আনুমানিক সূচনা করা হয়।^[৬] দ্রুত বিপরীত বর্গমূলের মূলটি ছিল ফ্লোটিং-বিন্দুর সংখ্যার কাঠামো ব্যবহার করে সরাসরি একটি আনুমানিক মান হিসাব করা ও টেবিলে প্রদর্শনের চেয়ে দ্রুত প্রমাণ করা। অ্যালগরিদম চতুর্মাত্রিক পদ্ধতিতে অন্য পদ্ধতিতে গণনা করে এবং পারস্পরিক ক্রিয়াশীল ফ্লোটিং পয়েন্ট বিভাগের মান হিসাব করে, যা প্রায় চার গুণ বেশি দ্রুত।^[৭] অ্যালগরিদম আইইইই ৭৫৪-১৯৮৫ 32-বিট ফ্লোটিং পয়েন্ট স্পেসিফিকেশন নিয়ে পরিকল্পিত ছিল, কিন্তু ক্রিস লোমোমেন্টের তদন্তে দেখা যায় এটি অন্যান্য ফ্লোটিং পয়েন্ট স্পেসিফিকেশনে প্রয়োগ করা যেতে পারে।^[৮]

দ্রুত বিপরীত বর্গমূল ক্লডজ দ্বারা প্রদত্ত গতিতে সুবিধাটি দীর্ঘদিনের^{[note ২]} উপাত্ত থেকে এসেছিল যা একটি পূর্ণসংখ্যা হিসাবে ফ্লোটিং পয়েন্ট নম্বরটি ধারণ করে এবং তারপর এটি একটি নির্দিষ্ট ধ্রুবক (0x5F3759DF) থেকে বিয়োগ করে। ধ্রুবক সোর্স কোডটি দেখতে যাতে সহজ উপলব্দ হয়, তাই, কোডে পাওয়া যেমন অন্যান্য ধ্রুবকের মত, এটিকে প্রায়ই একটি জাদুকরী সংখ্যা বলা হয়।^[১]^[৯]^[১০]^[১১] এই পূর্ণসংখ্যা বিয়োগ এবং বিট শিফ্টটি একটি লঙ্গনের মধ্যে ফলাফল যা একটি ফ্লোটিং পয়েন্ট সংখ্যা হিসাবে বিবেচনা করা হয় ইনপুট নম্বরের বিপরীত বর্গমূলের জন্য একটি আনুমানিক মান। নিউটন এর পুনরাবৃত্তির পদ্ধতি দ্বারা মানটি কিছুটা সঠিকতা অর্জন করে, এবং কোড শেষ হয়। অ্যালগরিদম নিউটন এর পদ্ধতির জন্য একটি অনন্য প্রথম পরিমাপ ব্যবহার করে যথোপযুক্ত ফলাফল উৎপন্ন করে; তবে ১৯৯৯ সালে মুক্তি পাওয়া x৮৬ প্রসেসরের উপর SSE নির্দেশনা rsqrtss ব্যবহার করার চেয়ে এটি খুব ধীর এবং নিখুঁত।^[১২]^[১৩]

সি স্ট্যান্ডার্ডগুলির পরিপ্রেক্ষিতে, বিটগুলির মাধ্যমে পূর্ণসংখ্যা হিসাবে একটি ফ্লোটিং পয়েন্ট মানকে পুনর্বিবেচনা করা অসম্পূর্ণ আচরণ বলে মনে করা হয়।দ্রুত বিপরীত বর্গমূলকে সাধারণ ভাবে সঠিক ভাবে সম্পন্ন করার জন্য, একটি আরো আদর্শ রূপান্তর পদ্ধতিতে, একটি ইউনিয়ন প্রকারের মাধ্যমে ফ্লোটিং পয়েন্ট মান এবং পূর্ণসংখ্যা টাইপ করা হয়। এটি একটি ইউনিয়ন টাইপ সঙ্গে সি++ এর মানের মধ্যে অনির্দিষ্ট আচরণ বিবেচনা করা হয় যে লক্ষ করা উচিত।

float Q_rsqrt( float number )
{
	union {
		float f;
		long i;
	} conv;
	
	float x2;
	const float threehalfs = 1.5F;

	x2 = number * 0.5F;
	conv.f  = number;
	conv.i  = 0x5f3759df - ( conv.i >> 1 );	// what the fuck? 
	conv.f  = conv.f * ( threehalfs - ( x2 * conv.f * conv.f ) );
	return conv.f;
}

কাজের একটি উদাহরণ

একটি উদাহরণ হিসাবে, $x = 0.15625$ সংখ্যা $1\sqrt x \approx 2.52982$ গণনা করতে ব্যবহার করা যেতে পারে। অ্যালগরিদম এর প্রথম ধাপ নিচে চিত্রিত করা হলো:

0011_1110_0010_0000_0000_0000_0000_0000  উভয় x এবং i এর বিট প্যাটার্ন
0001_1111_0001_0000_0000_0000_0000_0000  ডানের একটি পদ সরিয়েঃ (i >> 1)
0101_1111_0011_0111_0101_1001_1101_1111  জাদুকরী সংখ্যাটি হলো 0x5F3759DF
0100_0000_0010_0111_0101_1001_1101_1111  উত্তরটি হলো 0x5F3759DF - (i >> 1)

IEEE ৩২-bit ব্যবহার করে প্রদর্শনঃ

0_01111100_01000000000000000000000  1.25 * 2^-3
0_00111110_00100000000000000000000  1.125 * 2^-65
0_10111110_01101110101100111011111  1.432430... * 2^+63
0_10000000_01001110101100111011111  1.307430... * 2^+1

এই শেষ বিট প্যাটার্নটিকে একটি ফ্লোটিং পয়েন্ট নম্বর হিসাবে পুনর্বিন্যস্ত করে আনুমানিক সংখ্যা y = ২.৬১৪৮৬ হয়, যার মধ্যে প্রায় ৩.৪% ত্রুটি আছে। নিউটন এর পদ্ধতি একক পুনরাবৃত্তির পরে, চূড়ান্ত ফলাফল y = ২.৫২৫৪৯, যাতে শুধুমাত্র ০.১৭% ত্রুটি হয়।

অ্যালগরিদম

অ্যালগরিদম নিম্নলিখিত পদক্ষেপগুলি সম্পাদন করে 1/√x এর মান গণনা করে:

x কে একটি পূর্ণসংখ্যা ধরে $log 2 (x)$ এর একটি আনুমানিক গণনা করা হয়
একটি আনুমানিক হিসাব করার জন্য, $log 2 (1/\sqrt x)$ এর মান পরিমাপ করা হয়
ভিত্তি-২ ধরে মানটিকে বিস্তৃতি করে ফ্লোটিং মান বের করা হয়
নিউটন এর পদ্ধতির একক পুনরাবৃত্তির মাধ্যমে মান পরিমাপ করা হয়

ফ্লোটিং পয়েন্ট উপস্থাপনা

যেহেতু এই অ্যালগরিদম একক-স্পষ্টতা ভাসমান পয়েন্ট সংখ্যাগুলির বিট-স্তরের প্রতিনিধিত্বের উপর ব্যাপকভাবে নির্ভর করে, এই উপস্থাপনাটির একটি সংক্ষিপ্ত সারাংশ এখানে প্রদান করা হয়েছে। অশূন্য আসল সংখ্যাটি x একক স্পষ্টতা ভলট হিসাবে এনকোড করার জন্য, প্রথম ধাপ হল xকে একটি স্বাভাবিক বাইনারি সংখ্যা হিসাবে লিখতে হবেঃ^[১৪]

{\begin{aligned}x&=\pm 1.b_{1}b_{2}b_{3}\ldots \times 2^{e_{x}}\\&=\pm 2^{e_{x}}(1+m_{x})\end{aligned}}

যেখানে $e x$ এর সূচক একটি পূর্ণসংখ্যা, $(1 + m x)$ এর "তাৎপর্যপূর্ণ" বাইনারি উপস্থাপনা $m x \in [0, 1)$ , এবং $1.b 1 b 2 b 3 ...$ । এটা উল্লেখ করা উচিত যে, যেহেতু তাৎপর্যপূর্ণ পয়েন্টের একক বিট হওয়ার পরেই সর্বদা ১ হয়, তাই এটি সংরক্ষণ করা প্রয়োজন হয় না। এই ফর্ম থেকে, তিনটি স্বাক্ষরবিহীন পূর্ণসংখ্যা গণনা করা হয়:^[১৫]

$S x$ , এটি হলো এমন "সাইন বিট", যেখানে যদি $x > 0$ হয় তবে এর মান ০, এবং মান ১ হয় যদি $x < 0$ হয় (1 bit)
$E x = e x + B$ হলো "পরিবর্তিত এক্সপোনেন্ট", যেখানে $B = 127$ হলো "এক্সপোনেন্ট বায়াস"^{[note ৩]} (8 bits)
$M x = m x \times L$ , যেখানে $L = 2 23$ ^{[note ৪]} (23 bits)

এই ক্ষেত্রটি তারপর, একটি বামদিক থেকে ডানদিকে 32 বিট মান দ্বারা পূর্ণ হয়।^[১৬]

একটি উদাহরণ হিসাবে, আবার $x = 0.15625 = 0.00101 2$ বিবেচনা করে, x এর মান নির্ণয় করি,

x=+2^{-3}(1+0.25)

এবং এইভাবে, তিনটি স্বাক্ষরবিহীন পূর্ণসংখ্যা ক্ষেত্র হল:

$S = 0$
$E = -3 + 127 = 124 = 01111100 2$
$M = 0.25 \times 2 23 = 2097152 = 01000000000000000000000 2$

এই ক্ষেত্রগুলি নিচের চিত্রের মধ্যে দেখানো হলো:

আনুমানিক লগারিদম হিসাবে একটি পূর্ণসংখ্যার মান আলাদা করা

যদি কোন কম্পিউটার বা ক্যালকুলেটর ছাড়াই 1/√x গণনা করা হয়, তবে লগারিদমের টেবিল এ ক্ষেত্রে উপযোগী হবে, তবে আডেন্টিটি লগ $log b (1/\sqrt x$ ) = −½ log_b(x)}} দ্বারা মান নির্ণয় সম্ভব, যা প্রতিটি বেসের জন্য বৈধ। দ্রুত বিপরীত বর্গমূল এই পরিচয় উপর ভিত্তি করে, এবং যে একটি ফ্লোট-৩২ একটি পূর্ণসংখ্যা তার লগারিদমের একটি আনুমানিক মান দেয়। এখানে কীভাবে:

যদি x হল একটি ইতিবাচক স্বাভাবিক সংখ্যা:

x=2^{e_{x}}(1+m_{x})

তারপর আছে,

\log _{2}(x)=e_{x}+\log _{2}(1+m_{x})

কিন্তু যেহেতু $m x \in [0, 1)$ , ডানদিকে অবস্থিত লগারিদমের মান আনুমানিক হতে পারে,^[১৭]

\log _{2}(1+m_{x})\approx m_{x}+\sigma

যেখানে $σ$ হল একটি নিখুঁত প্যারামিটার যা আদান প্রদানের জন্য ব্যবহৃত হয়। উদাহরণস্বরূপ, $σ = 0$ উৎপন্ন ব্যবধানের উভয় প্রান্তে সঠিক ফলাফল উৎপন্ন করে, যখন $σ \approx 0.0430357$ যথাযথ পরিমাপ (ত্রুটিটির ইউনিফর্ম আদর্শের অর্থে সেরা) উৎপন্ন করে।

এইভাবে আনুমানিক মানটি বের করা হয়।

\log _{2}(x)\approx e_{x}+m_{x}+\sigma .

অন্যদিকে, একটি পূর্ণসংখ্যা ফলন হিসাবে x এর বিট প্যাটার্ন ব্যাখ্যা,^{[note ৫]}

{\begin{aligned}I_{x}&=E_{x}L+M_{x}\\&=L(e_{x}+B+m_{x})\\&=L(e_{x}+m_{x}+\sigma +B-\sigma )\\&\approx L\log _{2}(x)+L(B-\sigma ).\end{aligned}}

এটি তখন দেখায় যে $I x$ একটি শ্রেণিকৃত এবং স্থানান্তরিত রৈখিক $log 2 (x)$ এর পরিমাপকৃত মান, যা ডান পাশের চিত্রে অঙ্কিত। অন্য কথায়, $log 2 (x)$ দ্বারা অনুমিত হয়,

\log _{2}(x)\approx {\frac {I_{x}}{L}}-(B-\sigma ).

ফলাফলের প্রথম পরিমাপ

পরিচয়ের উপর ভিত্তি করে $y = 1/\sqrt x$ গণনা,

\log _{2}(y)=-{\frac {1}{2}}\log _{2}(x)

উপরের লগারিদমের আনুমানিক মান ব্যবহার করে, x এবং y উভয়ই প্রয়োগ করে, উপরের সমীকরণটি হয়:

{\frac {I_{y}}{L}}-(B-\sigma )\approx -{\frac {1}{2}}{\biggl (}{\frac {I_{x}}{L}}-(B-\sigma ){\biggr )}

সুতরাং, $I y$ এর পরিমাপকৃত মান হলো:

I_{y}\approx {\frac {3}{2}}L(B-\sigma )-{\frac {1}{2}}I_{x}

সুতরাং, যা কোডে লেখা আছে,

i  = 0x5f3759df - ( i >> 1 );

উপরে প্রথম শব্দটি জাদু সংখ্যা,

{\frac {3}{2}}L(B-\sigma )={\text{0x5F3759DF}}

যার থেকে এটি $σ \approx 0.0450466$ হতে পারে। দ্বিতীয় শব্দটি $½ I x$ , যেখানে $I x$ এক বিন্দুর ডানদিকে বিট স্থানান্তর করে গণনা করা হয়।^[১৮]

নিউটন এর পদ্ধতি

$y$ কে বিপরীত বর্গমূল ধরে, $f(y)={\frac {1}{y^{2}}}-x=0$ । আগের ধাপগুলি দ্বারা প্রাপ্ত পরিমাপ, মূল খোঁজার পদ্ধতির ব্যবহার করে পরিমার্জিত করা যেতে পারে, এটি এমন একটি পদ্ধতি যা একটি ফাংনের শূন্য খুঁজে বের করে। বীজগণিতটি নিউটন এর পদ্ধতি ব্যবহার করে: যদি একটি পরিমাপ, y এর $y n$ থাকে, তাহলে একটি ভাল আনুমানিক হিসাব $y_{n+1}$ by taking $y_{n}-{\frac {f(y_{n})}{f'(y_{n})}}$ গণনা করা যাবে, যেখানে $f'(y_{n})$ এর ডেরিভেটিভটি $f(y)$ এর $y_{n}$ হবে।^[১৯] উপরের $f(y)$ , $y_{n+1}={\frac {y_{n}(3-xy_{n}^{2})}{2}}$ যেখানে $f(y)={\frac {1}{y^{2}}}-x$ এবং $f'(y)={\frac {-2}{y^{3}}}$ ।

$y$ কে ফ্লোটিং নম্বর ধরে, y = y*(threehalfs - x2*y*y); এর সমতুল মান হলো $\,y_{n+1}=y_{n}\left(1.5-{\frac {x}{2}}y_{n}^{2}\right)={\frac {y_{n}(3-xy_{n}^{2})}{2}}$ । এই ধাপটি পুনরাবৃত্তি করে ফাংশনের আউটপুট ( $y_{n+1}$ ) ব্যবহার করে পরবর্তী পুনরাবৃত্তির ইনপুট হিসাব করা হয়, অ্যালগরিদমটি $y$ এর বিপরীত বর্গমূলে রূপান্তরিত করে।^[২০] কোয়েক তৃতীয় ইঞ্জিনের উদ্দেশ্যে শুধুমাত্র একটি পুনরাবৃত্তির জন্য ব্যবহার করা হয়েছিল। একটি দ্বিতীয় পুনরাবৃত্তির কোডে ছিল, কিন্তু মন্তব্যে যোগ করা হয়েছিল।^[১১]

যথার্থতা

একটি গ্রাফ দ্রুত বিপরীত বর্গমূল এবং বিপরীত বর্গমূলের মানের মধ্যে পার্থক্য দেখায় যা (*libstdc*) দ্বারা সরবরাহ করা হয়^{[তথ্যসূত্র প্রয়োজন]} (নোটঃ লগস্কেল উভয় অক্ষেই)

উপরে উল্লিখিত হিসাবে, আনুমানিক মান আশ্চর্যজনকভাবে সঠিক হয়। ০.০১ তে শুরু হওয়া ইনপুটগুলির জন্য ডান দিকে গ্রাফটি ফাংশনের ত্রুটি (অর্থাৎ, নিউটন এর পদ্ধতির একটি পুনরাবৃত্তির মাধ্যমে এটির উন্নতির পরে অতিক্রান্ততার ত্রুটি), যেখানে স্ট্যান্ডার্ড লাইব্রেরি ১০.০ মান দেয়, যখন InvSqrt() থেকে মান ৯.৯৮২২২২ হয়, তখন পার্থক্য হয় ০.০১৭৪৭৯, অথবা ০.১৭৫%। পরম ত্রুটিটি কেবল তখনই কেবল বেশি হয়, যখন আপেক্ষিক ত্রুটি পরিমাপের সমস্ত আদেশ জুড়ে একই সীমার মধ্যে থাকে।

ইতিহাস এবং তদন্ত

কোয়েকন ২০০৫ পর্যন্ত কোয়েক-থ্রির জন্য সোর্স কোড প্রকাশিত হয় নি , কিন্তু ২০০৫ বা ২০০৩ সালের দিকে দ্রুত বিপরীত বর্গমূলের কোড ইউসনেট এবং অন্যান্য ফোরামে প্রকাশিত হয়। ^[১] প্রচলিত ধারণা ছিল জন কারম্যাক সম্ভবত এই কোডের লেখক, কিন্তু তিনি বিনয়ী প্রকাশ করেন এবং এর লেখক হিসেবে তারজে ম্যাথেসেন এর নাম প্রস্তাব করেন, একটি সুশৃঙ্খল সমাবেশ প্রোগ্রামার হিসেবে যিনি ইতোমধ্যে কোয়েক অপ্টিমাইজেশান সঙ্গে আইডি সফ্টওয়্যার সাহায্য করেন। ম্যাথেসেন ১৯৯০ এর দশকের একটি অনুরূপ বিট কোড লেখেন, কিন্তু মূল লেখকগণ থ্রিডি কম্পিউটার গ্রাফিক্সের ইতিহাসে অনেক আগেই প্রমাণিত হয়েছিল যে গরি তেরোলি এর এসজিআই নীল এর কোড বাস্তবায়নের জন্য, যা হতে পারে এর সম্ভাব্য সর্বপ্রথম ব্যবহার। রেইস সমাফেল্ড উপসংহার টেনে বলেন যে মেটল্যাব এর আবিষ্কারক ক্লিভ মোলারের সঙ্গে পরামর্শ সঙ্গে আরডেন্ট কম্পিউটারে গ্রেগ ওয়ালশ দ্বারা মূল এলগরিদম উদ্ভাবিত হয়েছিল।^[২১] ক্লিভ মোলার উইলিয়াম কাহন এবং কে.সি.-এর লিখিত কোড থেকে এই কৌশল সম্পর্ক জানতে পারেন।১৯৮৬^[২২] সালের দিকে বার্কলে এনএজি ^[২৩]^[২৪] জিম ব্লিন আইইইইউ কম্পিউটার গ্রাফিক্স এবং অ্যাপ্লিকেশনের জন্য ১৯৯৭ সালে কলামের বিপরীত বর্গমূ্লের একটি সাধারণ পরিমাপ প্রদর্শন করেন।^[২৫] পল কিনে ১৯৮৬ এর কাছাকাছি সময়ে এফপিএসটি সিরিজ কম্পিউটারের জন্য একটি দ্রুত পদ্ধতি বাস্তবায়ন করেন। সিস্টেমটি ভেক্টর ফ্লোটিং পয়েন্ট হার্ডওয়্যার যা পূর্ণসংখ্যার অপারেশন সমৃদ্ধ ছিল না এবং অন্তর্ভুক্ত প্রাথমিক বিন্দু তৈরি করতে ম্যানিপুলেশন অনুমোদন করার জন্য ফ্লোটিং-পয়েন্ট মানগুলি শুরু হয়েছিল।

জাদুকরী সংখ্যাটি নির্ধারণের সঠিক মান কীভাবে নির্ধারিত হয়েছিল তা সঠিকভাবে জানা যায়নি। ক্রিস লোম্যান্ট একটি পরিসীমা্র উপর জাদু সংখ্যা R নির্বাচন করে আনুমানিক মানের ত্রুটি হ্রাস করেন। তিনি প্রথমে 0x5F37642F, 0x5F3759DF এর কাছাকাছি রৈখিক পরিমাপের ধাপের জন্য সর্বোত্তম ধ্রুবকটি গণনা করেছিলেন, কিন্তু এই নতুন ধ্রুবক নিউটনের পদ্ধতির পুনরাবৃত্তির পরে সামান্য কম সঠিকতা প্রদান করেছিলো।^[২৬] লোম্যান্ট তখন একের পর এক নিউটনের পুনরাবৃত্তির পরে ধ্রুবক অনুকূল অনুসন্ধান করেন এবং 0x5F375A86 পান, যা প্রতিটি পুনরাবৃত্তির পর্যায়ে মূল থেকে আরও সঠিক।^[২৬] আসল ধ্রুবকের সঠিক মূল্যটি ডেরিভেটিভেশন বা ট্রায়াল এবং ত্রুটির মধ্য দিয়ে নির্বাচিত হয়েছিল কি না তা নিয়ে তিনি উপসংহার টেনেছেন।^[২৭] লোম্যান্ট উল্লেখ করেছেন যে ৬৪ বিট আইআইইই-৭৫৭৫ আকারের টাইপ ডবল জাদু সংখ্যা 0x5FE6EC85E7DE30DA, কিন্তু এটি পরে ম্যাথু রবার্টসন দ্বারা সঠিক মান 0x5FE6EB50C7B537A9 দেখানো হয়েছিল।^[২৮]

আরোও দেখুন

বর্গ মূল গণনার পদ্ধতি

টীকা

↑ There was a discussion on the Chinese developer forum CSDN back in 2000.^[২]
↑ long ধরনের ব্যবহার আধুনিক সিস্টেমের উপর এই কোডের পোর্টেবিলিটিকে হ্রাস করে। কোডটি সঠিকভাবে চালানোর জন্য, sizeof(long) ৪ বাইটের হতে হবে, অন্যথায় নেটিভ আউটপুটগুলির ফলাফল ভিন্ন হতে পারে। অনেক আধুনিক ৬৪-বিট সিস্টেমের অধীনে, sizeof(long) ৮ বাইটের হতে পারে।
↑ $E x$ একটি স্বাভাবিক সংখ্যা হিসাবে প্রতিনিধিত্ব করা $x$ এর জন্য $[1, 254]$ পরিসীমা হতে হবে।
↑ একমাত্র প্রকৃত সংখ্যা যা ঠিক তাৎক্ষণিকভাবে উপস্থাপন করা যেতে পারে, যার জন্য $M x$ একটি পূর্ণসংখ্যা। অন্যান্য সংখ্যার শুধুমাত্র নিকটতম ঠিক প্রতিনিধিত্বশীল সংখ্যা তাদের মান দ্বারা প্রায় প্রতিনিধিত্ব করা যাবে।
↑ $S x = 0$ যখন $x > 0$ .

তথ্যসূত্র

↑ ^ক ^খ ^গ ^ঘ Sommefeldt, Rys (২০০৬-১১-২৯)। "Origin of Quake3's Fast InvSqrt()"। Beyond3D। সংগ্রহের তারিখ ২০০৯-০২-১২।
↑ "Discussion on CSDN"। ২০১৫-০৭-০২ তারিখে মূল থেকে আর্কাইভ করা।
↑ Blinn 2003, পৃ. 130।
↑ Middendorf 2007, পৃ. 155–164।
↑ "quake3-1.32b/code/game/q_math.c"। Quake III Arena। id Software। সংগ্রহের তারিখ ২০১৭-০১-২১।
↑ Eberly 2001, পৃ. 504।
↑ Lomont 2003, পৃ. 1।
↑ Lomont 2003।
↑ Lomont 2003, পৃ. 3।
↑ McEniry 2007, পৃ. 2, 16।
↑ ^ক ^খ Eberly 2001, পৃ. 2।
↑ Ruskin, Elan (২০০৯-১০-১৬)। "Timing square root"। Some Assembly Required। ২০১৫-০৫-১৮ তারিখে মূল থেকে আর্কাইভ করা। সংগ্রহের তারিখ ২০১৫-০৫-০৭।
↑ Fog, Agner। "Lists of instruction latencies, throughputs and micro-operation breakdowns for Intel, AMD and VIA CPUs" (পিডিএফ)। সংগ্রহের তারিখ ২০১৭-০৯-০৮।
↑ Goldberg 1991, পৃ. 7।
↑ Goldberg 1991, পৃ. 15–20।
↑ Goldberg 1991, পৃ. 16।
↑ McEniry 2007, পৃ. 3।
↑ Hennessey ও Patterson 1998, পৃ. 305।
↑ Hardy 1908, পৃ. 323।
↑ McEniry 2007, পৃ. 6।
↑ Sommefeldt, Rys (২০০৬-১২-১৯)। "Origin of Quake3's Fast InvSqrt() - Part Two"। Beyond3D। সংগ্রহের তারিখ ২০০৮-০৪-১৯।
↑ Moler, Cleve। "Symplectic Spacewar"। MATLAB Central - Cleve's Corner। MATLAB। সংগ্রহের তারিখ ২০১৪-০৭-২১।
↑ Blinn 1997, পৃ. 80–84।
↑ "sqrt implementation in fdlibm"।
↑ Fazzari, Rod; Miles, Doug; Carlile, Brad; Groshong, Judson (১৯৮৮)। "A New Generation of Hardware and Software for the FPS T Series"। Proceedings of the 1988 Array Conference: 75–89।
↑ ^ক ^খ Lomont 2003, পৃ. 10।
↑ Lomont 2003, পৃ. 10–11।
↑ Matthew Robertson (২০১২-০৪-২৪)। "A Brief History of InvSqrt" (পিডিএফ)। UNBSJ। ২০১৬-০৩-২৯ তারিখে মূল (পিডিএফ) থেকে আর্কাইভ করা। সংগ্রহের তারিখ ২০১৮-০২-১১।

গ্রন্থপঞ্জি

Blinn, Jim (জুলাই ১৯৯৭)। "Floating Point Tricks"। Computer Graphics & Applications, IEEE। 17 (4): 80। ডিওআই:10.1109/38.595279।
Blinn, Jim (২০০৩)। Jim Blinn's Corner: Notation, notation notation। Morgan Kaufmann। আইএসবিএন 1-55860-860-5।
Eberly, David (২০০১)। 3D Game Engine Design। Morgan Kaufmann। আইএসবিএন 978-1-55860-593-0।
Goldberg, David (১৯৯১)। "What every computer scientist should know about floating-point arithmetic"। ACM Computing Surveys। 23 (1): 5–48। ডিওআই:10.1145/103162.103163।
Hardy, Godfrey (১৯০৮)। A Course of Pure Mathematics। Cambridge, UK: Cambridge University Press। আইএসবিএন 0-521-72055-9।
Hennessey, John; Patterson, David A. (১৯৯৮)। Computer Organization and Design (2nd সংস্করণ)। San Francisco, CA: Morgan Kaufmann Publishers। আইএসবিএন 978-1-55860-491-9।
Lomont, Chris (ফেব্রুয়ারি ২০০৩)। "Fast Inverse Square Root" (পিডিএফ)। সংগ্রহের তারিখ ২০০৯-০২-১৩।
McEniry, Charles (আগস্ট ২০০৭)। "The Mathematics Behind the Fast Inverse Square Root Function Code" (পিডিএফ)। ২০১৫-০৫-১১ তারিখে মূল (পিডিএফ) থেকে আর্কাইভ করা।
Middendorf, Lars; Mühlbauer, Felix; Umlauf, George; Bodba, Christophe (জুন ১, ২০০৭)। "Embedded Vertex Shader in FPGA"। Rettberg, Achin। Embedded System Design: Topics, Techniques and Trends। IFIP TC10 Working Conference:International Embedded Systems Symposium (IESS)। et al.। Irvine, California: Springer। আইএসবিএন 978-0-387-72257-3।
Striegel, Jason (২০০৮-১২-০৪)। "Quake's fast inverse square root"। Hackszine। O'Reilly Media। ২০০৯-০২-১৫ তারিখে মূল থেকে আর্কাইভ করা। সংগ্রহের তারিখ ২০১৩-০১-০৭।
IEEE Computer Society (১৯৮৫), 754-1985 - IEEE Standard for Binary Floating-Point Arithmetic, Institute of Electrical and Electronics Engineers

বহিঃসংযোগ

Kushner, David (আগস্ট ২০০২)। "The wizardry of Id"। IEEE Spectrum। 39 (8): 42–47। ডিওআই:10.1109/MSPEC.2002.1021943।
A Brief History of InvSqrt ওয়েব্যাক মেশিনে আর্কাইভকৃত ২৯ মার্চ ২০১৬ তারিখে by Matthew Robertson
0x5f3759df, further investigations into accuracy and generalizability of the algorithm by Christian Plesner Hansen
Origin of Quake3's Fast InvSqrt()
Quake III Arena source code

[3] There was a discussion on the Chinese developer forum CSDN back in 2000.^[২]

[10] long ধরনের ব্যবহার আধুনিক সিস্টেমের উপর এই কোডের পোর্টেবিলিটিকে হ্রাস করে। কোডটি সঠিকভাবে চালানোর জন্য, sizeof(long) ৪ বাইটের হতে হবে, অন্যথায় নেটিভ আউটপুটগুলির ফলাফল ভিন্ন হতে পারে। অনেক আধুনিক ৬৪-বিট সিস্টেমের অধীনে, sizeof(long) ৮ বাইটের হতে পারে।

[18] $E x$ একটি স্বাভাবিক সংখ্যা হিসাবে প্রতিনিধিত্ব করা $x$ এর জন্য $[1, 254]$ পরিসীমা হতে হবে।

[19] একমাত্র প্রকৃত সংখ্যা যা ঠিক তাৎক্ষণিকভাবে উপস্থাপন করা যেতে পারে, যার জন্য $M x$ একটি পূর্ণসংখ্যা। অন্যান্য সংখ্যার শুধুমাত্র নিকটতম ঠিক প্রতিনিধিত্বশীল সংখ্যা তাদের মান দ্বারা প্রায় প্রতিনিধিত্ব করা যাবে।

[22] $S x = 0$ যখন $x > 0$ .

[Beyond3D-1] ক ^খ ^গ ^ঘ Sommefeldt, Rys (২০০৬-১১-২৯)। "Origin of Quake3's Fast InvSqrt()"। Beyond3D। সংগ্রহের তারিখ ২০০৯-০২-১২।

[csdn-2] "Discussion on CSDN"। ২০১৫-০৭-০২ তারিখে মূল থেকে আর্কাইভ করা।

[FOOTNOTEBlinn2003130-4] Blinn 2003, পৃ. 130।

[FOOTNOTEMiddendorf2007155–164-5] Middendorf 2007, পৃ. 155–164।

[quakesrc-6] "quake3-1.32b/code/game/q_math.c"। Quake III Arena। id Software। সংগ্রহের তারিখ ২০১৭-০১-২১।

[FOOTNOTEEberly2001504-7] Eberly 2001, পৃ. 504।

[FOOTNOTELomont20031-8] Lomont 2003, পৃ. 1।

[FOOTNOTELomont2003-9] Lomont 2003।

[FOOTNOTELomont20033-11] Lomont 2003, পৃ. 3।

[FOOTNOTEMcEniry20072,_16-12] McEniry 2007, পৃ. 2, 16।

[FOOTNOTEEberly20012-13] ক ^খ Eberly 2001, পৃ. 2।

[ruskin-14] Ruskin, Elan (২০০৯-১০-১৬)। "Timing square root"। Some Assembly Required। ২০১৫-০৫-১৮ তারিখে মূল থেকে আর্কাইভ করা। সংগ্রহের তারিখ ২০১৫-০৫-০৭।

[agner-15] Fog, Agner। "Lists of instruction latencies, throughputs and micro-operation breakdowns for Intel, AMD and VIA CPUs" (পিডিএফ)। সংগ্রহের তারিখ ২০১৭-০৯-০৮।

[FOOTNOTEGoldberg19917-16] Goldberg 1991, পৃ. 7।

[FOOTNOTEGoldberg199115–20-17] Goldberg 1991, পৃ. 15–20।

[FOOTNOTEGoldberg199116-20] Goldberg 1991, পৃ. 16।

[FOOTNOTEMcEniry20073-21] McEniry 2007, পৃ. 3।

[FOOTNOTEHennesseyPatterson1998305-23] Hennessey ও Patterson 1998, পৃ. 305।

[FOOTNOTEHardy1908323-24] Hardy 1908, পৃ. 323।

[FOOTNOTEMcEniry20076-25] McEniry 2007, পৃ. 6।

[Beyond3Dp2-26] Sommefeldt, Rys (২০০৬-১২-১৯)। "Origin of Quake3's Fast InvSqrt() - Part Two"। Beyond3D। সংগ্রহের তারিখ ২০০৮-০৪-১৯।

[MolerResp-27] Moler, Cleve। "Symplectic Spacewar"। MATLAB Central - Cleve's Corner। MATLAB। সংগ্রহের তারিখ ২০১৪-০৭-২১।

[FOOTNOTEBlinn199780–84-28] Blinn 1997, পৃ. 80–84।

[fdlibm-29] "sqrt implementation in fdlibm"।

[30] Fazzari, Rod; Miles, Doug; Carlile, Brad; Groshong, Judson (১৯৮৮)। "A New Generation of Hardware and Software for the FPS T Series"। Proceedings of the 1988 Array Conference: 75–89।

[FOOTNOTELomont200310-31] ক ^খ Lomont 2003, পৃ. 10।

[FOOTNOTELomont200310–11-32] Lomont 2003, পৃ. 10–11।

[robertson-33] Matthew Robertson (২০১২-০৪-২৪)। "A Brief History of InvSqrt" (পিডিএফ)। UNBSJ। ২০১৬-০৩-২৯ তারিখে মূল (পিডিএফ) থেকে আর্কাইভ করা। সংগ্রহের তারিখ ২০১৮-০২-১১।

[১]

[note ১]

[৩]

[৪]

[৫]

[৬]

[৭]

[৮]

[note ২]

[৯]

[১০]

[১১]

[১২]

[১৩]

[১৪]

[১৫]

[note ৩]

[note ৪]

[১৬]

[১৭]

[note ৫]

[১৮]

[১৯]

[২০]

[২১]

[২২]

[২৩]

[২৪]

[২৫]

[২৬]

[২৭]

[২৮]

[২]