الگوریتم اسپیگوت

الگوریتم اسپیگوت (به انگلیسی: Spigot Algorithm) یک نوع خاص از الگوریتم‌ها است که برای محاسبه ی مقدار یک ثابت ریاضی مانند π یا e استفاده می‌شود، که می‌تواند یک رشته ی خروجی از ارقام را بدون نیاز به استفاده ی مجدد از آنها تولید کند.این اسم از کاربرد کلمۀ اسپیگوت در برخی از شاخه‌های انگلیسی به معنی دریچه یا شیری که جریان یک مایع را کنترل می‌کند برگفته شده است.

علاقه به چنین الگوریتم‌هایی در روز‌های آغازین ریاضیات محاسباتی با تاکید شدید بر حافظه رواج پیدا کرد، و یک نمونه از این الگوریتم‌ها برای محاسبۀ ارقام عدد e می‌باشد. منتشرشد. نام الگوریتم اسپیگوت توسط استنلی رابینوویتز و استان واگن ابداع شد که الگوریتم ابداعی آنها برای محاسبه عدد π برخی اوقات تحت عنوان اگوریتم اسپگوت برای " π" نام برده می‌شود.

الگوریتم اسپیگوت رابینوویتز و ویگن کران‌دار است،به این معنا که تعداد ارقام خواسته شده باید از قبل مشخص باشد. جرمی گیبسون از اصطلاح الگوریتم‌های زنجیره‌ای برای معرفی الگوریتم‌هایی که به صورت نامحدود و بدون کران از پیش تعیین شده می‌توانند اجرا شوند،استفاده می‌کند . پیشرفت‌های بیشتر منجر به ابداع الگوریتم ای گردید که قابلیت محاسبه یک عدد دلخواه را بدون نیاز به محاسبه ارقام پیشین آن در وهله اول،دارا است : فرمول بیلی-بوروین-پلوفه نمونه‌ای از این الگوریتم است.یک الگوریتم تجزیه ارقامی برای عدد π که ارقام را در مبنای ۶ تولید می‌کند.

مثال

این مثال نحوه ی کار کردن الگوریتم اسپیگوت را با محاسبه ی ارقام باینری لگاریتم طبیعی ۲ نشان می‌دهد (دنباله ی A068426 درOEIS ) با استفاده از تساوی ذیل :

$\ln(2)=\sum _{k=1}^{\infty }{\frac {1}{k2^{k}}}\,.$

برای محاسبه ارقام باینری از جایگاه هشتم ما طرفین تساوی فوق را در 2⁷ ضرب می‌کنیم ( با توجه به اینکه ۷=۸-۱)

$2^{7}\ln(2)=2^{7}\sum _{k=1}^{\infty }{\frac {1}{k2^{k}}}\,.$

سپس ما سری نا محدود را به دو قسمت تقسیم می‌کنیم : قسمت "head" که در آن توان ۲ بزرگتر یا مساوی ۰ است و قسمت "tail" که در آن توان ۲ منفی است.

$2^{7}\ln(2)=\sum _{k=1}^{7}{\frac {2^{7-k}}{k}}+\sum _{k=8}^{\infty }{\frac {1}{k2^{k-7}}}\,.$

از آنجایی که ما فقط علاقه‌مند به بخش کسری این مقدار هستیم می‌توانیم هر مؤلفه سری در "head" را با مقدار زیر جایگزین کنیم

${\frac {2^{7-k}\mod k}{k}}\,.$

با محاسبه هر کدام از این مقادیر و اضافه کردن آنها به سری کلی که در حال اجراست ( که مجدداً در این سری کلی ما تنها علاقه‌مند به بخش کسری هستیم) به نتایج زیر می‌رسیم :

k	A = 27-k	B = A mod k	C = B / k	Sum of C mod 1
۱	۶۴	۰	۰	۰
۲	۳۲	۰	۰	۰
۳	۱۶	۱	۱/۳	۱/۳
۴	۸	۰	۰	۱/۳
۵	۴	۴	۴/۵	۲/۱۵
۶	۲	۲	۱/۳	۷/۱۵
۷	۱	۱	۱/۷	۶۴/۱۰۵

ما مقادیری را به بخش "tail" می‌افزاییم،با توجه به اینکه خطای تولید شده به موجب کوتاه کردن سری کمتر از مقدار نهایی است.

k	D = 1/k2k-7	Sum of D	Maximum error
۸	۱/۱۶	۱/۱۶	۱/۱۶
۹	۱/۳۶	۱۳/۱۴۴	۱/۳۶
۱۰	۱/۸۰	۳۷/۳۶۰	۱/۸۰

با اضافه کردن بخش "head" و تعداد اندکی از مقادیر نخستین بخش "tail" به نتایج زیر می‌رسیم :

$2^{7}\ln(2)\mod {1}\approx {\frac {64}{105}}+{\frac {37}{360}}=0.10011100\cdots _{2}+0.00011010\cdots _{2}=0.1011\cdots _{2}\,,$

بنابراین ارقام ۸ ام تا ۱۱ ام در بسط باینری (ln(2 ارقام ۱،۱،۰،۱ می‌باشند.توجه کنید که ما مقادیر ۷ رقم نخست باینری را محاسبه نکرده‌ایم - در واقع تمامی اطلاعات مربوط به آنها با استفاده از هم نهشتی(نظریه اعداد) در بخش سری "head" به صورت عمدی حذف شده است. روش مشابهی می‌تواند برای محاسبه ی ارقام بسط باینری (ln(2 با شروع از جایگاه دلخواه n ام مورد استفاده قرار بگیرد. تعداد عبارت‌های موجود درقسمت "head" سری به صورت خطی با n افزایش میابد ، اما چناچه یک روش کارآمدی با استفاده از به‌توان‌رساندن مدولار به کار گرفته شود پیچیدگی هرعبارت تنها با لگاریتم n افزایش میابد. دقت محاسبات،نتایج میانی و تعداد عبارت‌های گرفته شده از قسمت "tail" سری همگی مستقل از n می‌باشند و تنها وابسته به تعداد ارقام باینری هستند که در حال محاسبه است - یک واحد محاسباتی می‌تواند برای محاسبه حدودا ۱۲ رقم باینری صرف نظر از جایگاه شروع مورد استفاده قرار گیرد.

مطالعات بیشتر

• Arndt, Jorg; Haenel, Christoph, π unleashed, Springer Verlag, 2000.
• Weisstein, Eric W. "Spigot algorithm". MathWorld.

لینک‌های خارجی

• Simon Singh. "Pi in the Simpsons (and four fingers)". Numberphile. Brady Haran.