‏الگوریتم yy: سریع‌ترین راه تبدیل float به رشته

نویسنده این پست، که خودش کتابخونه تبدیل عدد به رشته Żmij رو نوشته، سراغ یه الگوریتم دیگه به اسم yy رفته که تو کتابخونه معروف yyjson استفاده می‌شه. جالبه که yy نه مقاله‌ای داره و نه اسم رسمی؛ فقط اسم فایل سورسش (yy_double.c) روش مونده. با این حال یکی از سریع‌ترین پیاده‌سازی‌های dtoa (تبدیل double به رشته) شناخته می‌شه.

yy تو خانواده الگوریتم‌های Schubfach جا می‌گیره؛ یعنی برای هر عدد باینری، کوتاه‌ترین عدد دهدهی که بشه دوباره به همون عدد باینری برگردوندش رو پیدا می‌کنه. تفاوت yy اینه که کل این کارو فقط با یه ضرب در توان از پیش محاسبه‌شدهٔ ۱۰ انجام می‌ده، در حالی که Schubfach کلاسیک به دو یا سه ضرب نیاز داره. این یعنی محاسبات خیلی سبک‌تر و سریع‌تر.

نویسنده برای توضیح بهتر، یه صفحهٔ تعاملی ساخته که روی فرمت ۸ بیتی E4M3 (که تو inference هوش مصنوعی روی GPUهای جدید استفاده می‌شه) کار می‌کنه، چون این فرمت فقط ۲۵۶ حالت داره و همه‌چی رو می‌شه رو یه صفحه دید. تو این ابزار یه مورد مرزی جالب پیدا کرده: عدد ۱۹۲ که در نگاه اول باید به‌صورت 19e1 چاپ بشه، ولی الگوریتم به‌خاطر یه جملهٔ تصحیح‌کننده که خطای گرد‌کردن جدول توان‌های ۱۰ رو جبران می‌کنه، به‌جاش کوتاه‌تر یعنی 2e2 چاپ می‌کنه؛ و هر دو خروجی درستن.

نویسنده می‌گه این جور الگوریتم‌ها که فقط تو کتابخونه‌های JSON زندگی می‌کنن، معمولاً به‌اندازهٔ الگوریتم‌های دارای مقالهٔ رسمی دیده نمی‌شن، ولی به‌نظرش yy ارزش شناختن داره.

نکات کلیدی:

• الگوریتم yy از کتابخونهٔ yyjson میاد و هیچ مقاله یا اسم رسمی نداره
• برخلاف Schubfach کلاسیک که ۲ یا ۳ ضرب لازم داره، yy فقط با یه ضرب کار می‌کنه
• صفحهٔ تعاملی نویسنده روی فرمت ۸ بیتی E4M3 عملکرد الگوریتم رو مرحله‌به‌مرحله نشون می‌ده
• تو عدد ۱۹۲، یه جملهٔ تصحیح باعث می‌شه خروجی کوتاه‌تر (2e2) به‌جای طولانی‌تر (19e1) چاپ بشه، و هر دو صحیحن