دوال مثلثية سريعة باستخدام طريقة RLIBM

المعلومات الأساسية

• معرّف الورقة: 2510.13426
• العنوان: دوال مثلثية سريعة باستخدام طريقة RLIBM
• المؤلفون: Sehyeok Park, Santosh Nagarakatte (جامعة روتجرز)
• التصنيف: cs.PL (لغات البرمجة)
• المؤتمر: ورشة العمل الدولية للتحقق من البرامج العلمية (VSS 2025)
• رابط الورقة: https://arxiv.org/abs/2510.13426

الملخص

تصف هذه الورقة التجربة في تطوير تقريبات متعددة الحدود للدوال المثلثية باستخدام طريقة RLIBM، والتي تنتج نتائج مقربة بشكل صحيح لتمثيلات وأنماط تقريب متعددة. يكمن التحدي الرئيسي للدوال المثلثية في تقليل النطاق الذي يتضمن π، والذي يقلل المدخلات من مجال الأعداد العشرية 32 بت إلى مجال صغير. أي خطأ تقريب في قيمة π يتم تضخيمه أثناء عملية تقليل النطاق، مما قد يؤدي إلى نتائج خاطئة. يصف المؤلفون تجربتهم في تنفيذ تقنيات تقليل نطاق سريعة تحافظ على عدد كبير من أرقام π في كل من الحسابات العشرية والصحيحة. يوفر التنفيذ النهائي للدوال المثلثية سرعة وتقريباً صحيحاً لجميع المدخلات، مع دعم تمثيلات متعددة تصل إلى 32 بت، وذلك باستخدام تنفيذ واحد فقط.

السياق البحثي والدافع

المشاكل الأساسية

1. تحدي التقريب الصحيح: تستخدم الحسابات العلمية على نطاق واسع الدوال الأساسية المقدمة من مكتبات رياضية، لكن إنتاج نتائج مقربة بشكل صحيح لجميع المدخلات أمر بالغ الصعوبة ("معضلة جدول الأرقام")، وتفشل مكتبات الرياضيات السائدة في إنتاج نتائج صحيحة لجميع المدخلات.
2. مشاكل قابلية النقل والتكرار: يؤدي الافتقار إلى التقريب الصحيح في مكتبات الرياضيات إلى إنتاج التطبيقات نتائج مختلفة تماماً على أجهزة مختلفة، مما يؤثر على قابلية النقل والتكرار.
3. الحاجة إلى تمثيلات متعددة: مع زيادة التنسيقات المخصصة (مثل bfloat16 و tensorfloat32 و FP8)، هناك حاجة إلى مكتبة مرجعية توفر نتائج صحيحة لتمثيلات وأنماط تقريب متعددة.

قيود الطرق الموجودة

• تقريب متعدد الحدود Minimax: تنتج الطرق التقليدية تقريبات متعددة الحدود تقلل الحد الأقصى للخطأ لجميع المدخلات، لكن عندما تكون القيمة الحقيقية للمخرجات قريبة جداً من حدود التقريب، تنخفض درجات الحرية بشكل كبير.
• المقايضة بين الأداء والصحة: تقوم المكتبات الموجودة بالمقايضة بين الأداء (مثل تنفيذ Payne-Hanek) أو الصحة (مثل libm في GCC).

المساهمات الأساسية

1. تقنيات تقليل نطاق فعالة: تطوير خوارزمية تقليل نطاق فعالة تجمع بين العمليات الحسابية العشرية والصحيحة، مع الحفاظ على عدد كافٍ من أرقام π لإنتاج نتائج صحيحة.
2. تنفيذ واحد لتمثيلات متعددة: تنفيذ تقريب متعدد الحدود واحد يمكنه إنتاج نتائج مقربة بشكل صحيح لتمثيلات متعددة من 10 إلى 32 بت وجميع أنماط التقريب القياسية.
3. تحسين الأداء: يحسن تقليل النطاق القائم على الأعداد الصحيحة الأداء بنسبة 19% مقارنة بالاستراتيجية العشرية، والأداء الإجمالية أسرع أو مكافئة للمكتبات السائدة.
4. مكتبة دوال مثلثية كاملة: توفير تنفيذات سريعة وصحيحة لدوال sin و cos و tan.

شرح الطريقة

الفكرة الأساسية لطريقة RLIBM

الرؤية الأساسية لطريقة RLIBM هي تقريب نتيجة التقريب الصحيح مباشرة، بدلاً من القيمة الحقيقية للدالة. بالنسبة لنتيجة التقريب الصحيح لمدخل معين، يوجد فاصل قيمة حقيقية، وأي قيمة داخل هذا الفاصل ستقرب إلى النتيجة الصحيحة. يوفر هذا درجات حرية أكبر من طريقة minimax (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):

• استخدام 256/π بـ 80 بت، مقسمة إلى قيمتي double
• تجنب أخطاء التقريب الوسيطة
• استخدام الضرب الجزئي الدقيق لحساب k والجزء الكسري r

معالجة المدخلات الكبيرة (2^30 ≤ |x|):

• الإصدار 1: تقسيم 256/π إلى شرائح 28 بت مخزنة في مصفوفة double، مع استخدام نمط القطع لكل شريحة
• الإصدار 2: استخدام شرائح بدقة 53 بت، مع الاستفادة من تعليمات الضرب والجمع المدمجة لتقليل أخطاء التقريب

استراتيجية التنفيذ الصحيح

تحسين المدخلات الصغيرة:

• استخدام 256/π بـ 80 بت، مقسمة إلى عددين صحيحين 40 بت P1 و P0
• تحديد العدد الصحيح k والبتات الكسرية من خلال عمليات الإزاحة
• تجنب فقدان الدقة في العمليات الحسابية العشرية

معالجة المدخلات الكبيرة:

• استخدام 256/π بـ 192 بت، مقسمة إلى ثلاثة أعداد صحيحة 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.

إعداد التجارب

بيئة الاختبار

• الأجهزة: خادم Intel Xeon(R) Silver 4310 بسرعة 2.10GHz، 256GB RAM
• نظام التشغيل: Ubuntu 24.04.1 LTS
• أداة القياس: عدادات الأداء

المكتبات المقارنة

• GLIBC: libm للأعداد العشرية والمزدوجة
• Core-Math: مكتبة التقريب الصحيح
• تنفيذ RLIBM: متغيرات استراتيجيات تقليل النطاق المختلفة

مؤشرات التقييم

• الصحة: التحقق من صحة جميع المدخلات من خلال التعداد الكامل
• الأداء: نسبة التسريع بالنسبة للمكتبات الأخرى

نتائج التجارب

التحقق من الصحة

• دوال RLIBM: تنتج نتائج مقربة بشكل صحيح لجميع المدخلات لجميع التمثيلات من 10 إلى 32 بت
• GLIBC float libm: يحتوي على آلاف النتائج الخاطئة لـ sin و cos و tan للمدخلات 32 بت
• GLIBC double libm: أكثر دقة من إصدار float لكن لا يزال يحتوي على أخطاء
• Core-Math: ينتج نتائج صحيحة فقط لـ 32 بت، ويفشل في نطاق 10-32 بت بسبب أخطاء التقريب المزدوج

نتائج الأداء

تأثير تحسينات تقليل النطاق

الطريقة المختلطة (عشرية للمدخلات الصغيرة، صحيحة للمدخلات الكبيرة) مقارنة بالاستراتيجيات الأخرى:

• أسرع بنسبة 19% من الطريقة العشرية الأولية (FP V1)
• تحسن كبير مقارنة بالطريقة العشرية البديلة (FP V2)
• أسرع بنسبة 4% من الطريقة الصحيحة البحتة

المقارنة مع المكتبات الأخرى

• أسرع بمتوسط 10% من Core-Math
• أسرع بمتوسط 137% من دوال GLIBC double
• يعزى تحسن الأداء بشكل أساسي إلى تقليل النطاق الفعال وميزات الدقة في العمليات الحسابية الصحيحة

نقاط الابتكار التقني

1. توازن الدقة والأداء

• توفر العمليات الحسابية الصحيحة دقة أعلى من 64 بت double (uint64_t و uint128_t)
• تقليل عدد الضربات الجزئية المطلوبة للحصول على دقة كافية لتقليل المدخل

2. استراتيجية تقليل نطاق مختلطة

• استخدام العمليات الحسابية العشرية للمدخلات الصغيرة (عندما يكون الجزء الصحيح من 256*x/π صغيراً بما يكفي)
• استخدام العمليات الحسابية الصحيحة للمدخلات الكبيرة (توفير دقة أعلى وعمليات بت أبسط)

3. تحسينات العمليات البتية

• استخدام عمليات الإزاحة لتحديد الأجزاء ذات الصلة بـ 256*x/π المتعلقة بالمدخل المقلل و k
• تجنب تراكم الأخطاء في العمليات الحسابية العشرية

الأعمال ذات الصلة

الطرق التقليدية

• تقريب Minimax: خوارزميات مثل 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 للفاصلة العائمة

تقدم هذه الورقة مساهمة مهمة في مجال الحسابات الرقمية، حيث تحول الطرق النظرية بنجاح إلى تنفيذ عملي عالي الأداء، وتوفر حلاً فعالاً لمشكلة التقريب الصحيح في الحسابات العلمية.