الگوریتمی جدید و سریع‌تر برای تقسیم بر کف علامت‌دار ۶۴ بیتی

مقدمه و زمینه

تقسیم بر کف (Floor Division) عملیاتی است که برخلاف تقسیم استاندارد (Truncated Division) که به سمت صفر گرد می‌کند، نتیجه را به سمت بی‌نهایت منفی (-∞) گرد می‌کند. این نوع تقسیم برای مواردی مانند پردازش تایم‌استمپ‌های یونیکس، چرخش زاویه‌ها یا موقعیت‌دهی کاشی‌ها بسیار حیاتی است. با این حال، دنیای محاسبات عدد صحیح در این زمینه با مشکلاتی روبه‌رو است:

• بسیاری از کامپایلرها و زبان‌های برنامه‌نویسی主流 (مانند C و C++ و Go و Swift) از آن به صورت بومی پشتیبانی نمی‌کنند.
• کتابخانه‌هایی که آن را پیاده‌سازی کرده‌اند، اغلب از سریع‌ترین الگوریتم‌ها استفاده نمی‌کنند.
• منابع آموزشی آنلاین و ابزارهای هوش مصنوعی معمولاً کدهای کند یا حتی دارای باگ (مانند سرریز در اعداد منفی) پیشنهاد می‌دهند.
• کتاب مرجع «Hacker's Delight» که به عنوان کتاب مقدس ریاضیات سطح پایین شناخته می‌شود، اطلاعات جامع و به‌روزی در این مورد ارائه نداده است.

جزئیات فنی و الگوریتم جدید

این مقاله تکنیک جدیدی را معرفی می‌کند که با استفاده از ضرب و شیفت بیتی پیشرفته (Wide Multiplication)، عمل تقسیم با مقادیر ثابت را به شدت سرعت می‌بخشد. به عنوان مثال، در تقسیم عدد ۶۴ بیتی بر 86400 (تعداد ثانیه‌های یک روز)، روش‌های سنتی نیاز به محاسبه جداگانه باقیمانده و اصلاح خطاهای اعداد منفی دارند که سربار زیادی ایجاد می‌کند.

رویکرد جدید با انتخاب دقیق ضریب و استفاده از انواع داده‌ی __int128، محاسبات را به صورت خطی و بدون نیاز به دستورات پرهزینهٔ شرطی یا محاسبه‌ی مجدد باقیمانده انجام می‌دهد. نمونه کد این روش برای عدد 86400 به شکل زیر است:

inline int64_t fast_i64_floordiv_86400(int64_t x) {
    const int64_t M = ((__int128(1) << 79) / 86400 + 1);
    const int64_t m = M + (x >> 63);
    return (__int128) x * m >> 79;
}

نتایج بنچمارک و عملکرد

بر اساس بنچمارک‌های انجام‌شده روی تراشه‌های مختلف:

• روی پردازنده‌های ARM: این الگوریتم توانسته است بین ۱۰ تا ۲۰ درصد پهنای باند و کارایی بهتری نسبت به روش‌های موجود برای اکثر مقسوم‌علیهای ۶۴ بیتی ارائه دهد.
• روی پردازنده‌های x86: در حدود ۸۰ درصد از مقسوم‌علیهای مثبت (و ۶۰ درصد از مقسوم‌علیهای منفی)، ۵ تا ۱۰ درصد بهبود سرعت در Throughput مشاهده می‌شود.

چرا این موضوع برای مهندسان اهمیت دارد؟

عملیات تقسیم یکی از کندترین دستورات سخت‌افزاری در پردازنده‌هاست (اغلب چندین سیکل کلاک مصرف می‌کند). در سیستم‌های با پردازش بالا (High-Performance Computing) که پردازش تایم‌استمپ‌ها، گرافیک یا پردازش سیگنال انجام می‌شود، بهینه‌سازی تقسیم ثابت می‌تواند به طور چشمگیری بار پردازشی را کاهش دهد. این مقاله منبعی ارزشمند برای توسعه‌دهندگانی است که می‌خواهند کتابخانه‌های سریع‌تر بنویسند یا محدودیت‌های کامپایلرها را دور بزنند.