درست وقتی که فکر کردم طلسم سریال فیبوناچی از بین رفته است ، به زندگی من برگشت. من اخیراً جعبه ابزار الگوریتمی دوره Coursera تا کنون فوق العاده را شروع کردم که بخشی از ساختار داده ها و الگوریتم های 1 است. اولین مشکل پیشرفت در هفته دوم به شرح زیر است.

مشکل (اکتشافی طول صف): با توجه به دو عدد صحیح n و m ، خروجی $ f_n متن< mod >m $ (یعنی باقیمانده $ f_n $ در هنگام تقسیم توسط m).

قالب ورودیورودی شامل دو عدد صحیح N و M است که در همان خط (جدا شده توسط یک فضا) ارائه شده است.

محدودیت ها.$ 1 leq n leq 10^$ ، $ 2 leq m leq 10^5 $.

فرمت خروجی. خروجی $ f_n متن< mod >m$

نکته (محدودیت های زمانی): زبان C C ++ Java Python C# Haskell JavaScript Ruby Scala (SEC) 1 1 1. 5 5 1. 5 2 5 5 3

مدتی طول کشید تا مشکل را پشت سر بگذارم ، و به همین دلیل و این واقعیت که این یک نمونه غیر مهم دیگر بود که شامل دنباله فیبوناچی بود ، تصمیم گرفتم در مورد آن 2 وبلاگ نویسی کنم.

من فکر می کنم این مشکل به معنای نشان دادن است که گاهی اوقات کارآمدترین الگوریتم ها فقط در صورتی انجام می شود که بینش غیرقانونی در مورد مشکل داشته باشید. در این حالت ، راهنمای مشکل ارائه شده به عنوان یک اشاره به واقعیت $ f_n متن< mod >M $ یک توالی دوره ای تولید می کند که خود را پس از تعدادی به نام دوره Pisano تکرار می کند که به عنوان $ pi (m) 3 دلار حاشیه نویسی می شود. هر چرخه مکرر همیشه با 0 ، 1 شروع می شود زیرا این اولین چرخه برای هر متن $ f_n است< mod >m $ with $m >1 $به عنوان مثال ، در مورد M = 2 و 3 توالی موارد زیر است:

$ f_n متن< mod >2 = 0 ، 1 ، 1 ، 0 ، 1 ، 1 ، 0 ، 1 ، 1 ، 0 ،… $

$ f_n متن< mod >3 = 0 ، 1 ، 1 ، 2 ، 0 ، 2 ، 2 ، 0 ، 1 ، 1 ،… $

بنابراین ، اگر برای یک modulo معین $ m $ ، دوره $ pi (m) $ دنباله $ f_n را می دانید< mod >M $ پس از آن نتیجه می گیرد

این بدان معنی است که به جای محاسبه "$ f_n متن< mod >m$” you can in principle compute “$f_ pi(m)> mod m $ "که می تواند در پیچیدگی 4 کوچکتر باشد. بنابراین ، یک شبه کد که این ایده را اعمال می کند ، زیر نشان داده شده است.

من امیدوارم که شما بتوانید از ماهیت جالب توجه الگوریتم قدردانی کنید ، که برای محاسبه عظیم فیبوناکیمودولو ، شما هنوز هم نیاز به اجرای تا حدودی خوب از Fibonaccimodulo دارید. این اجرای نه تنها برای بازگشت عملکرد بلکه از همه مهمتر هنگام جستجوی دوره Pisano مورد نیاز است.

رویکرد ساده لوحانه محاسبه شماره فیبوناچی و سپس گرفتن مدول آن کارآمد نیست. این امر به این دلیل است که شما باید قبل از ساخت ماژول ، تعداد زیادی از آنها تولید کنید و شانس سرریز عدد صحیح را افزایش دهید. بنابراین ، این ترفند برای دیدن اینکه آیا راهی برای استفاده از مدول در مراحل واسطه در هنگام تولید سری وجود دارد یا خیر. برای این کار ، ما می توانیم با استفاده از خاصیت اضافی ماژولار 5 و در نتیجه اینکه ماژول سری فیبوناچی $ m $ $ را می توان با بازگشت زیر تعریف کرد

٪٪ f_n متن< mod >m = (f_ متن< mod >m + f_ متن< mod >م) متن< mod >m متن< for any >n >1 ٪٪

with initial values $f_0 = 0$ and $f_1 = 1$ assuming $m >1 $شبه کد زیر این بازگشت را اجرا می کند.

با ترکیب تمام این رویه ها می توانید یک نسخه ساده از این الگوریتم بنویسید. من آن را برای تکمیل این تکلیف به خواننده واگذار می کنم.

آیا این همه کار می کند؟خوب ، نوع. این می تواند یک ماژول شماره فیبوناچی عظیم $ m $ را محاسبه کند ، اما گاهی اوقات ممکن است چند ثانیه طول بکشد تا دوره Pisano را هنگام اجرای در C ++ برای برخی از مقادیر M $ $ پیدا کند. این امر نیازهای زمان مسئله را نقض می کند ، اگرچه این الگوریتم در یک زمان معقول (ده ها ثانیه) موفق به انجام کار در حداکثر کار است.

دلیل کاهش سرعت این است که ارزش دوره Pisano می تواند برای هر $ M $ به شدت تغییر کند. شکل زیر یک نمونه تصادفی یکنواخت از 5000 مقادیر $ $ بین 2 $ و 10^5 $ و $ $ pi (m) $ را نشان می دهد. به راحتی می توان مشاهده کرد که با افزایش $ pi (m) $ بیشتر است ، اگرچه الگوی بی اهمیت وجود ندارد. بنابراین ، یک اسکن سیستماتیک برای یک دوره $ pi (m) $ با توجه به modulo $ m $ برای پیش بینی زمان اجرای سخت است ، اگرچه به طور متوسط برای تعداد بیشتری بیشتر می شود.

این بدان معناست که دو گزینه دیگر وجود دارد ، یا شما یک الگوریتم دقیق تر برای یافتن دوره Pisano با بهره برداری از بینش های عمیق تر از نظریه شماره 6 یا ، می توانید از ترکیبی از نیروی بی رحم و یک جدول جستجو استفاده کنید. البته ، من زمین بالاتر (با نام مستعار ترسو) را گرفتم و با اسکن برای دوره Pisano برای مقادیر ماژول 2 leq m leq 10^5 $ ، یک جدول جستجو ایجاد کردم. این تنها به لطف تعداد محدودی از مقادیر مدول مجاز توسط بیانیه مشکل ممکن است. راه حلی که من پیشنهاد می کنم ممکن است به محض اجازه دادن به $ m $ به یک مقدار سفارش بالاتر باشد.

با فرض اینکه تمام دوره های Pisano عدد صحیح 32 بیتی هستند ، ما فقط به 100000 از آنها یا 400 کیلوبایت حافظه در محدودیت حافظه نیاز داریم. اسکن برای تمام مقادیر دوره Pisano حدود 72 ساعت در چندین محدوده با قیمت M $ $ به طور همزمان در یک پردازنده Intel i7 انجام شد.

من فقط تمام مؤلفه های لازم را به شما می دهم تا یک کد با مقادیر دوره Pisano سخت کدگذاری شده ایجاد کنید. تست استرس نسخه C ++ من از این کد ، فهمیدم که حداکثر اجرا می شود~1ms به خوبی در مورد نیازهای مشکل!

منابع

در اصل پیچیدگی از $ o (n^2) $ به $ o (n text می رود< mod > pi (m)) $ در صورتی که ارزش $ m $ را می توان در 32 بیت عدد صحیح ثابت کرد. این امر به این دلیل است که هر مبلغ تکرار هنگام محاسبه الگوریتم فیبوناکیمودولو (به بعداً در پست مراجعه کنید) به دلیل این واقعیت که هیچ شماره واسطه ای از $ M $ بزرگتر نخواهد بود ، $ (1) $ خواهد بود.↩

توجه داشته باشید از یک بین المللی توسط ویکتور E. Bazterra تحت یک مجوز بین المللی و نه مجوز بین المللی ، دارای مجوز Creative Commons است.< pan> با فرض اینکه تمام دوره های Pisano عدد صحیح 32 بیتی هستند ، ما فقط به 100000 از آنها یا 400 کیلوبایت حافظه در محدودیت های حافظه نیاز داریم. اسکن برای تمام مقادیر دوره Pisano حدود 72 ساعت در چندین محدوده با قیمت M $ $ به طور همزمان در یک پردازنده Intel i7 انجام شد.