2025-11-17T19:07:12.711716

Fast Trigonometric Functions using the RLIBM Approach

Park, Nagarakatte
This paper describes our experience developing polynomial approximations for trigonometric functions that produce correctly rounded results for multiple representations and rounding modes using the RLIBM approach. A key challenge with trigonometric functions concerns range reduction with "pi", which reduces a given input in the domain of a 32-bit float to a small domain. Any rounding error in the value of "pi" is amplified during range reduction, which can result in wrong results. We describe our experience implementing fast range reduction techniques that maintain a large number of bits of "pi" both with floating-point and integer computations. The resulting implementations for trigonometric functions are fast and produce correctly rounded results for all inputs for multiple representations up to 32-bits with a single implementation.
academic

RLIBM পদ্ধতি ব্যবহার করে দ্রুত ত্রিকোণমিতিক ফাংশন

মৌলিক তথ্য

  • পেপার আইডি: 2510.13426
  • শিরোনাম: RLIBM পদ্ধতি ব্যবহার করে দ্রুত ত্রিকোণমিতিক ফাংশন
  • লেখক: Sehyeok Park, Santosh Nagarakatte (Rutgers University)
  • শ্রেণীবিভাগ: cs.PL (প্রোগ্রামিং ভাষা)
  • প্রকাশনা সম্মেলন: International Workshop on Verification of Scientific Software (VSS 2025)
  • পেপার লিঙ্ক: https://arxiv.org/abs/2510.13426

সারসংক্ষেপ

এই পেপারটি RLIBM পদ্ধতি ব্যবহার করে ত্রিকোণমিতিক ফাংশন বহুপদী অনুমান বিকাশের অভিজ্ঞতা বর্ণনা করে, যা বিভিন্ন প্রতিনিধিত্ব এবং রাউন্ডিং মোডের জন্য সঠিকভাবে রাউন্ড করা ফলাফল তৈরি করতে পারে। ত্রিকোণমিতিক ফাংশনের মূল চ্যালেঞ্জ হল π জড়িত পরিসীমা হ্রাস, যা 32-বিট ফ্লোটিং পয়েন্ট ডোমেনে ইনপুটকে ছোট ডোমেনে হ্রাস করে। π মানের যেকোনো রাউন্ডিং ত্রুটি পরিসীমা হ্রাস প্রক্রিয়ায় প্রসারিত হয়, যা ভুল ফলাফলের দিকে পরিচালিত করতে পারে। লেখকরা দ্রুত পরিসীমা হ্রাস কৌশল বাস্তবায়নের অভিজ্ঞতা বর্ণনা করেন, যা ফ্লোটিং পয়েন্ট এবং পূর্ণসংখ্যা গণনা উভয়েই π এর বিশাল সংখ্যক বিট বজায় রাখে। চূড়ান্ত ত্রিকোণমিতিক ফাংশন বাস্তবায়ন দ্রুত এবং সমস্ত ইনপুটের জন্য সঠিকভাবে রাউন্ড করা ফলাফল উৎপাদন করে, 32-বিট পর্যন্ত বিভিন্ন প্রতিনিধিত্ব সমর্থন করে এবং শুধুমাত্র একটি একক বাস্তবায়ন প্রয়োজন।

গবেষণা পটভূমি এবং প্রেরণা

মূল সমস্যা

  1. সঠিক রাউন্ডিং এর চ্যালেঞ্জ: বৈজ্ঞানিক গণনা গণিত লাইব্রেরি দ্বারা প্রদত্ত মৌলিক ফাংশন ব্যাপকভাবে ব্যবহার করে, কিন্তু সমস্ত ইনপুটের জন্য সঠিকভাবে রাউন্ড করা ফলাফল উৎপাদন অত্যন্ত কঠিন ("টেবিলমেকারের দ্বিধা"), এবং প্রধান গণিত লাইব্রেরি সমস্ত ইনপুটের জন্য সঠিক ফলাফল উৎপাদন করতে পারে না।
  2. পোর্টেবিলিটি এবং পুনরুৎপাদনযোগ্যতা সমস্যা: সঠিক রাউন্ডিং এর অভাব গণিত লাইব্রেরি অ্যাপ্লিকেশনগুলিকে বিভিন্ন মেশিনে সম্পূর্ণ ভিন্ন ফলাফল উৎপাদন করতে দেয়, যা পোর্টেবিলিটি এবং পুনরুৎপাদনযোগ্যতাকে প্রভাবিত করে।
  3. বিভিন্ন প্রতিনিধিত্ব ফর্ম্যাটের প্রয়োজনীয়তা: কাস্টম ফর্ম্যাট (যেমন bfloat16, tensorfloat32, FP8) বৃদ্ধির সাথে, একটি রেফারেন্স লাইব্রেরির প্রয়োজন যা বিভিন্ন প্রতিনিধিত্ব এবং রাউন্ডিং মোডের জন্য সঠিক ফলাফল প্রদান করতে পারে।

বিদ্যমান পদ্ধতির সীমাবদ্ধতা

  • মিনিম্যাক্স বহুপদী অনুমান: ঐতিহ্যবাহী পদ্ধতি সমস্ত ইনপুটের সর্বাধিক ত্রুটি কমিয়ে আনে এমন বহুপদী অনুমান তৈরি করে, কিন্তু যখন প্রকৃত মূল্যের আউটপুট রাউন্ডিং সীমানার খুব কাছাকাছি থাকে, স্বাধীনতার ডিগ্রি উল্লেখযোগ্যভাবে হ্রাস পায়।
  • কর্মক্ষমতা এবং সঠিকতা ট্রেড-অফ: বিদ্যমান লাইব্রেরি কর্মক্ষমতা (যেমন Payne-Hanek বাস্তবায়ন) বা সঠিকতা (যেমন GCC এর libm) এর ক্ষেত্রে আপস করে।

মূল অবদান

  1. দক্ষ পরিসীমা হ্রাস কৌশল: ফ্লোটিং পয়েন্ট এবং পূর্ণসংখ্যা গণনা একত্রিত করে একটি দক্ষ পরিসীমা হ্রাস অ্যালগরিদম বিকাশ করা হয়েছে, যা সঠিক ফলাফল উৎপাদনের জন্য π এর পর্যাপ্ত বিট বজায় রাখতে পারে।
  2. বহু-প্রতিনিধিত্ব একক বাস্তবায়ন: একটি একক বহুপদী অনুমান বাস্তবায়ন করা হয়েছে, যা 10-বিট থেকে 32-বিট এর বিভিন্ন প্রতিনিধিত্ব এবং সমস্ত মান রাউন্ডিং মোডের জন্য সঠিকভাবে রাউন্ড করা ফলাফল উৎপাদন করতে পারে।
  3. কর্মক্ষমতা অপ্টিমাইজেশন: পূর্ণসংখ্যা-ভিত্তিক পরিসীমা হ্রাস ফ্লোটিং পয়েন্ট কৌশলের তুলনায় 19% কর্মক্ষমতা উন্নতি প্রদান করে, সামগ্রিক প্রধান লাইব্রেরির চেয়ে দ্রুত বা সমতুল্য কর্মক্ষমতা।
  4. সম্পূর্ণ ত্রিকোণমিতিক ফাংশন লাইব্রেরি: sin, cos, tan ফাংশনের জন্য দ্রুত এবং সঠিক বাস্তবায়ন প্রদান করা হয়েছে।

পদ্ধতির বিস্তারিত ব্যাখ্যা

RLIBM পদ্ধতির মূল ধারণা

RLIBM পদ্ধতির মূল অন্তর্দৃষ্টি হল সঠিকভাবে রাউন্ড করা ফলাফল সরাসরি অনুমান করা, ফাংশনের প্রকৃত মূল্যের পরিবর্তে। প্রদত্ত ইনপুটের জন্য সঠিকভাবে রাউন্ড করা ফলাফলের জন্য, একটি প্রকৃত মূল্য ব্যবধান রয়েছে, যার মধ্যে যেকোনো মূল্য সঠিক ফলাফলে রাউন্ড করবে। এটি মিনিম্যাক্স পদ্ধতির চেয়ে বৃহত্তর স্বাধীনতা প্রদান করে (সমস্ত ইনপুটের জন্য 1 ULP)।

বহু-প্রতিনিধিত্ব সমর্থন প্রক্রিয়া

বিভিন্ন প্রতিনিধিত্ব সমর্থন করার জন্য, RLIBM প্রকল্প (n+2)-বিট প্রতিনিধিত্বের বহুপদী অনুমান তৈরি করার প্রস্তাব দেয়, round-to-odd রাউন্ডিং মোড ব্যবহার করে। এই পদ্ধতির সুবিধা হল:

  • round-to-odd ফলাফল লক্ষ্য প্রতিনিধিত্বে সরাসরি রাউন্ড করার জন্য প্রয়োজনীয় সমস্ত তথ্য সংরক্ষণ করে
  • পরবর্তী রাউন্ডিং নিম্ন বিট-প্রস্থ প্রতিনিধিত্বে সঠিক ফলাফল উৎপাদন করতে পারে
  • দ্বিগুণ রাউন্ডিং ত্রুটি এড়ায়

পরিসীমা হ্রাস অ্যালগরিদম

মৌলিক নীতি

ত্রিকোণমিতিক ফাংশনের পরিসীমা হ্রাস ইনপুট x∈-∞,∞ কে হ্রাসকৃত ইনপুট x'∈-π/2^(t+1), π/2^(t+1) এ ম্যাপ করে, যেখানে:

x = x' + kπ/2^t
k = [2^t * x/π]
x' = π/2^t * r, যেখানে r = 2^t*x/π - k

ফ্লোটিং পয়েন্ট বাস্তবায়ন কৌশল

ছোট ইনপুট প্রক্রিয়াকরণ (|x| < 2^30):

  • 80-বিট 256/π ব্যবহার করা হয়, দুটি double মানে সংরক্ষিত
  • মধ্যবর্তী রাউন্ডিং ত্রুটি এড়ানো হয়
  • k এবং ভগ্নাংশ অংশ r সঠিকভাবে গণনা করতে আংশিক পণ্য ব্যবহার করা হয়

বড় ইনপুট প্রক্রিয়াকরণ (2^30 ≤ |x|):

  • সংস্করণ 1: 256/π কে 28-বিট খণ্ডে বিভক্ত করা হয় double অ্যারেতে সংরক্ষিত, প্রতিটি খণ্ড ট্রাংকেশন মোড ব্যবহার করে তৈরি
  • সংস্করণ 2: 53-বিট নির্ভুলতা খণ্ড ব্যবহার করা হয়, fused-multiply-add নির্দেশ ব্যবহার করে রাউন্ডিং ত্রুটি হ্রাস করা হয়

পূর্ণসংখ্যা বাস্তবায়ন কৌশল

ছোট ইনপুট অপ্টিমাইজেশন:

  • 80-বিট 256/π ব্যবহার করা হয়, দুটি 40-বিট পূর্ণসংখ্যা P1 এবং P0 তে বিভক্ত
  • বিট শিফট অপারেশনের মাধ্যমে পূর্ণসংখ্যা k এবং ভগ্নাংশ বিট চিহ্নিত করা হয়
  • ফ্লোটিং পয়েন্ট গণনার নির্ভুলতা হ্রাস এড়ানো হয়

বড় ইনপুট প্রক্রিয়াকরণ:

  • 192-বিট 256/π ব্যবহার করা হয়, তিনটি 64-বিট পূর্ণসংখ্যায় বিভক্ত
  • 128-বিট আংশিক পণ্য গণনা করা হয়
  • বিট শিফট অপারেশনের মাধ্যমে প্রাসঙ্গিক বিট নিষ্কাশন করা হয়

আউটপুট ক্ষতিপূরণ

ত্রিকোণমিতিক পরিচয় ব্যবহার করে আউটপুট ক্ষতিপূরণ:

sin(x) = sin(k'π/2^t)cos(x') + cos(k'π/2^t)sin(x')
cos(x) = cos(k'π/2^t)cos(x') - sin(k'π/2^t)sin(x')

পূর্ব-গণনা করা টেবিল এবং পর্যায়ক্রমিকতা/প্রতিসাম্য অপ্টিমাইজেশনের মাধ্যমে, প্রয়োজনীয় পূর্ব-গণনা করা মান 512 এ হ্রাস করা হয়।

পরীক্ষামূলক সেটআপ

পরীক্ষা পরিবেশ

  • হার্ডওয়্যার: 2.10GHz Intel Xeon(R) Silver 4310 সার্ভার, 256GB RAM
  • অপারেটিং সিস্টেম: Ubuntu 24.04.1 LTS
  • পরিমাপ সরঞ্জাম: কর্মক্ষমতা কাউন্টার

তুলনামূলক লাইব্রেরি

  • GLIBC: float এবং double libm
  • Core-Math: সঠিক রাউন্ডিং লাইব্রেরি
  • RLIBM বাস্তবায়ন: বিভিন্ন পরিসীমা হ্রাস কৌশলের বৈকল্পিক

মূল্যায়ন সূচক

  • সঠিকতা: সম্পূর্ণ গণনার মাধ্যমে সমস্ত ইনপুটের সঠিকতা যাচাই করা হয়
  • কর্মক্ষমতা: অন্যান্য লাইব্রেরির তুলনায় ত্বরণ অনুপাত

পরীক্ষামূলক ফলাফল

সঠিকতা যাচাইকরণ

  • RLIBM ফাংশন: 10-বিট থেকে 32-বিট সমস্ত প্রতিনিধিত্বের সমস্ত ইনপুটের জন্য সঠিকভাবে রাউন্ড করা ফলাফল উৎপাদন করে
  • GLIBC float libm: 32-বিট float ইনপুটের sin, cos, tan এর জন্য হাজার হাজার ত্রুটিপূর্ণ ফলাফল রয়েছে
  • GLIBC double libm: float সংস্করণের চেয়ে আরও নির্ভুল কিন্তু এখনও ত্রুটি রয়েছে
  • Core-Math: শুধুমাত্র 32-বিটের জন্য সঠিক ফলাফল উৎপাদন করে, 10-32 বিট পরিসরে দ্বিগুণ রাউন্ডিং ত্রুটির কারণে ব্যর্থ হয়

কর্মক্ষমতা ফলাফল

পরিসীমা হ্রাস অপ্টিমাইজেশন প্রভাব

মিশ্র পদ্ধতি (ছোট ইনপুটের জন্য ফ্লোটিং পয়েন্ট, বড় ইনপুটের জন্য পূর্ণসংখ্যা) অন্যান্য কৌশলের তুলনায়:

  • প্রাথমিক ফ্লোটিং পয়েন্ট পদ্ধতি (FP V1) এর চেয়ে 19% দ্রুত
  • বিকল্প ফ্লোটিং পয়েন্ট পদ্ধতি (FP V2) এর তুলনায় উল্লেখযোগ্য উন্নতি
  • বিশুদ্ধ পূর্ণসংখ্যা পদ্ধতির চেয়ে 4% দ্রুত

অন্যান্য লাইব্রেরির সাথে তুলনা

  • Core-Math এর চেয়ে গড়ে 10% দ্রুত
  • GLIBC double ফাংশনের চেয়ে গড়ে 137% দ্রুত
  • কর্মক্ষমতা উন্নতি প্রধানত উচ্চ দক্ষ পরিসীমা হ্রাস এবং পূর্ণসংখ্যা গণনার নির্ভুলতা সুবিধার কারণে

প্রযুক্তিগত উদ্ভাবন পয়েন্ট

1. নির্ভুলতা এবং কর্মক্ষমতার ভারসাম্য

  • পূর্ণসংখ্যা গণনা 64-বিট double এর চেয়ে উচ্চতর নির্ভুলতা প্রদান করে (uint64_t এবং uint128_t)
  • হ্রাসকৃত ইনপুট পর্যাপ্ত নির্ভুলতা পেতে প্রয়োজনীয় আংশিক পণ্যের সংখ্যা হ্রাস করে

2. মিশ্র পরিসীমা হ্রাস কৌশল

  • ছোট ইনপুট ফ্লোটিং পয়েন্ট গণনা ব্যবহার করে (যখন 256*x/π এর পূর্ণসংখ্যা অংশ যথেষ্ট ছোট থাকে)
  • বড় ইনপুট পূর্ণসংখ্যা গণনা ব্যবহার করে (উচ্চতর নির্ভুলতা এবং সহজ বিট অপারেশন প্রদান করে)

3. বিট অপারেশন অপ্টিমাইজেশন

  • 256*x/π এ হ্রাসকৃত ইনপুট এবং k এর নিম্ন বিটের সাথে সম্পর্কিত অংশ চিহ্নিত করতে বিট শিফট অপারেশন ব্যবহার করা হয়
  • ফ্লোটিং পয়েন্ট গণনায় রাউন্ডিং সঞ্চয় এড়ানো হয়

সম্পর্কিত কাজ

ঐতিহ্যবাহী পদ্ধতি

  • মিনিম্যাক্স অনুমান: Remez অ্যালগরিদম ইত্যাদি, কিন্তু রাউন্ডিং সীমানার কাছাকাছি স্বাধীনতার ডিগ্রি সীমিত
  • Payne-Hanek অ্যালগরিদম: ক্লাসিক পরিসীমা হ্রাস পদ্ধতি, কিন্তু বাস্তবায়ন দক্ষতা একটি চ্যালেঞ্জ

সঠিক রাউন্ডিং গবেষণা

  • CR-LIBM: প্রাথমিক সঠিক রাউন্ডিং লাইব্রেরি, কিন্তু কর্মক্ষমতা ধীর
  • Core-Math: আধুনিক সঠিক রাউন্ডিং বাস্তবায়ন, কিন্তু শুধুমাত্র একক প্রতিনিধিত্ব সমর্থন করে

RLIBM প্রকল্প উন্নয়ন

  • মৌলিক ফাংশন (e^x, log ইত্যাদি) থেকে ত্রিকোণমিতিক ফাংশনে সম্প্রসারণ
  • বহু-প্রতিনিধিত্ব সমর্থনের উদ্ভাবনী পদ্ধতি

উপসংহার এবং আলোচনা

প্রধান উপসংহার

  1. সম্ভাব্যতা প্রমাণ: ত্রিকোণমিতিক ফাংশনের জন্য দ্রুত এবং সঠিক বাস্তবায়ন তৈরি করা সম্ভব প্রমাণ করে
  2. পরিসীমা হ্রাসের গুরুত্ব: উচ্চ দক্ষ পরিসীমা হ্রাস নিম্ন-ডিগ্রি বহুপদী অনুমানের মতোই গুরুত্বপূর্ণ
  3. পূর্ণসংখ্যা গণনার সুবিধা: পূর্ণসংখ্যা-ভিত্তিক বাস্তবায়ন বড় ইনপুটে ফ্লোটিং পয়েন্ট পদ্ধতির চেয়ে উল্লেখযোগ্যভাবে উন্নত

সীমাবদ্ধতা

  1. জটিলতা: বাস্তবায়ন জটিলতা উচ্চ, নির্ভুল বিট অপারেশন এবং একাধিক কৌশলের প্রয়োজন
  2. মেমরি ওভারহেড: পূর্ব-গণনা করা টেবিল এবং বহু-নির্ভুলতা ধ্রুবক সংরক্ষণের প্রয়োজন
  3. স্কেলেবিলিটি: উচ্চতর নির্ভুলতা প্রতিনিধিত্বে সম্প্রসারণ পুনর্ডিজাইনের প্রয়োজন

ভবিষ্যত দিকনির্দেশনা

  1. GPU প্ল্যাটফর্ম: GPU প্ল্যাটফর্মের সঠিক রাউন্ডিং লাইব্রেরি অন্বেষণ করা
  2. মানকীকরণ: IEEE-754 মান কমিটিতে অংশগ্রহণ করে বাধ্যতামূলক সঠিক রাউন্ডিং প্রচার করা
  3. প্রধান সংহতকরণ: প্রধান গণিত লাইব্রেরি বিকাশকারীদের সাথে এই পদ্ধতি সংহত করার জন্য সহযোগিতা করা

গভীর মূল্যায়ন

সুবিধা

  1. তত্ত্ব এবং অনুশীলনের সমন্বয়: RLIBM তত্ত্ব চ্যালেঞ্জিং ত্রিকোণমিতিক ফাংশনে সফলভাবে প্রয়োগ করা হয়েছে
  2. সম্পূর্ণ প্রকৌশল অপ্টিমাইজেশন: অ্যালগরিদম থেকে বাস্তবায়ন পর্যন্ত সর্বব্যাপী অপ্টিমাইজেশন
  3. কঠোর যাচাইকরণ: সম্পূর্ণ গণনার মাধ্যমে সঠিকতা যাচাই করা হয়েছে
  4. ব্যবহারিক মূল্য: বাস্তব অ্যাপ্লিকেশনে গুরুত্বপূর্ণ সমস্যা সমাধান করে

অপূর্ণতা

  1. বাস্তবায়ন জটিলতা: একাধিক কৌশলের সমন্বয় বাস্তবায়ন এবং রক্ষণাবেক্ষণ জটিলতা বৃদ্ধি করে
  2. পাঠযোগ্যতা: বিশাল বিট অপারেশন কোডের পাঠযোগ্যতা এবং রক্ষণাবেক্ষণযোগ্যতা উন্নত করার অবকাশ রয়েছে
  3. তাত্ত্বিক বিশ্লেষণ: পূর্ণসংখ্যা পদ্ধতি কেন আরও উন্নত তার গভীর তাত্ত্বিক বিশ্লেষণের অভাব

প্রভাব

  1. একাডেমিক অবদান: সংখ্যাসূচক গণনা ক্ষেত্রে নতুন সঠিক রাউন্ডিং বাস্তবায়ন পদ্ধতি প্রদান করে
  2. ব্যবহারিক মূল্য: উচ্চ নির্ভুলতা সংখ্যাসূচক গণনা প্রয়োজন এমন বৈজ্ঞানিক গণনায় সরাসরি প্রয়োগ করা যায়
  3. মান প্রচার: ভবিষ্যত ফ্লোটিং পয়েন্ট মান উন্নয়নকে প্রভাবিত করতে পারে

প্রযোজ্য পরিস্থিতি

  1. বৈজ্ঞানিক গণনা: উচ্চ নির্ভুলতা এবং পুনরুৎপাদনযোগ্যতা প্রয়োজন এমন সংখ্যাসূচক সিমুলেশন
  2. আর্থিক গণনা: নির্ভুল ফলাফল প্রয়োজন এমন আর্থিক মডেলিং
  3. এমবেডেড সিস্টেম: একাধিক ফ্লোটিং পয়েন্ট ফর্ম্যাট সমর্থন প্রয়োজন এমন সিস্টেম
  4. রেফারেন্স বাস্তবায়ন: অন্যান্য লাইব্রেরির সঠিকতার ভিত্তি হিসাবে

সংদর্ভ

এই পেপারটি সংখ্যাসূচক বিশ্লেষণ, ফ্লোটিং পয়েন্ট গণনা এবং সঠিক রাউন্ডিং ক্ষেত্রের গুরুত্বপূর্ণ সাহিত্য উদ্ধৃত করে, যার মধ্যে রয়েছে:

  • Muller এর মৌলিক ফাংশন রেফারেন্স বই
  • MPFR উচ্চ-নির্ভুলতা লাইব্রেরি
  • Payne-Hanek পরিসীমা হ্রাস অ্যালগরিদম
  • IEEE-754 ফ্লোটিং পয়েন্ট মান সম্পর্কিত গবেষণা

এই পেপারটি সংখ্যাসূচক গণনা ক্ষেত্রে গুরুত্বপূর্ণ অবদান রেখেছে, তত্ত্ব পদ্ধতিকে ব্যবহারিক উচ্চ-কর্মক্ষমতা বাস্তবায়নে সফলভাবে রূপান্তরিত করেছে, এবং বৈজ্ঞানিক গণনায় সঠিক রাউন্ডিং সমস্যার জন্য কার্যকর সমাধান প্রদান করেছে।