متد middle square

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو


در علم ریاضیات، متد مربع میانی (middle square) متدی برای تولید اعداد شبه تصادفی است. در واقع این متد، متد چندان خوبی نیست، زیرا دوره تکرار (priod) آن بسیار کوتاه است و چندین نقطه ضعف شدید دارد. یکی از این نقاط ضعف این است که دنباله خروجی آن همیشه همگرا به صفر است.

Msm-newpic.png

این متد توسط جان وان نیومن و نیکولاس متروپلیس در سال ۱۹۴۶ در آزمایشگاه‌های لس آلاموس برای شبیه‌سازی برخورد نوترون بعنوان قسمتی از پروژه منهتن توسعه یافت. این متد در ابتدا بدین صورت عمل می‌کرد:

«برای تولید یک دنباله ۴ رقمی از اعداد شبه تصادفی، یک مقدار اولیه ۴ رقمی ساخته و به توان ۲ رسانده شده است که درواقع یک عدد ۸ رقمی را تشکیل می‌دهد. اگر نتیجه کمتر از ۸ رقم داشت، باید با اضافه کردن صفر به اول آن، کمبود رقم آنرا جبران کرد. عدد ۴ رقم وسط این عدد، مشخص کننده رقم بعدی در دنباله است و بعنوان نتیجه بازگردانده می‌شود. این پروسه همچنان ادامه میابد تا اعداد تصادفی بیشتری تولید شوند.»

Msm-newpic2.png

برای یک سازنده اعداد n رقمی، دوره تکرار نمی‌تواند بیشتر 8n باشد. اگر تمام ۴ رقم وسط صفر باشند، ژنراتور (سازنده) تا ابد صفر را برمی‌گرداند. اگر نیمه اول یک عدد در دنباله صفر باشد، اعداد بعدی به سمت صفر کاهش میابند. متد middle-squared در اعداد غیر از صفر هم بهمین ترتیب به دام می‌افتد. مثلاً برای n = ۴، این اتفاق برای اعداد ۰۱۰۰، ۲۵۰۰، ۳۷۹۲ و ۷۶۰۰ رخ می‌دهد. باقی مقادیر seed (بذر) چرخه تکرار کوتاهی را می‌سازند، برای مثال ۰۵۴۰ → ۲۹۱۶ → ۵۰۳۰ → ۳۰۰۹. این پدیده‌ها در حالتی که n = ۲ باشد بیشتر قابل مشاهده هستند، چون هیچ‌یک از ۱۰۰ حالت ممکن برای seed، بیش از ۱۴ پیمایش را بدون رجوع به ۰، ۱۰، ۵۰، ۶۰ یا حلقه ۲۴ ↔ ۵۷ می‌سازد.

در مباحثه ۱۹۴۹، وان نیومن گفت: «هرکس که متدهای حسابی تولید ارقام تصادفی را مطرح کند، حقیقتاً مرتکب گناه شده است»، منظور وی از این گفته این بود که، هیچ «عدد تصادفی» معقولی وجود ندارد، تنها آنهارا بوسیله یک روش محاسباتی دقیق می‌سازند. با این وجود، وی این متدهارا صدها بار سریع تر از مطالعه اعداد تصادفی واقعی کارت‌های پانچ می‌دانست، که اهمیت زیادی برای کار ENIAC وی داشت. نیکولاس متروپلیس دنباله‌هایی با ۷۵۰٬۰۰۰ رقم را (قبل آنکه به اعداد مخرب برسد)، بوسیله ۳۸ بیت با استفاده از همین متد گزارش کرده است.

افسانه[ویرایش]

کتاب تاس شکسته (The Broken Dice) نوشته Ivar Ekeland شرح می‌دهد که چگونه متد توسط یک راهب صومعه فرانسیسکن ملقب به «برادر ادوین» در زمانی بین ۱۲۴۰ تا ۱۲۵۰ اختراع شد. ظاهراً نسخه خطی آن در حال حاضر گم شده است اما خورخه لوییس بورگس یک کپی از آن را که در کتابخانه واتیکان ساخته است را برای Ekeland ارسال کرد. برخی مواقع گفته می‌شود که این داستان واقعیت دارد اما توسط بازرسی‌های انجام شده مشخص شده که این داستان فانتزی بورگس بوده است.

دنباله ویل(Weyl)[ویرایش]

کاستی‌های مرتبط با سازنده اصلی middle-square می‌تواند بوسیله اجرا کردن middle square با دنباله ویل برطرف گردد. دنباله ویل از همگرایی به صفر جلوگیری می‌کند. پیاده‌سازی آن در زبان c در زیر آمده است:

1 #include <stdint.h>
2 
3 uint64_t x = 0, w = 0, s = 0xb5ad4eceda1ce2a9;
4 
5 inline static uint32_t msws() {
6    x *= x;
7    x += (w += s);
8    return x = (x>>32) | (x<<32);
9 }

دنباله ویل (w += s) به مربع x اضافه شده است. مقدار میانی (middle) با ۳۲ بیت شیفت دادن به سمت راست استخرج می‌شود.

یک بستته نرم‌افزاری آزاد در اینجا قابل دسترس است.

منابع[ویرایش]

  1. The 1949 papers were not reprinted until 1951. John von Neumann, “Various techniques used in connection with random digits,” in A.S. Householder, G.E. Forsythe, and H.H. Germond, eds. , Monte Carlo Method, National Bureau of Standards Applied Mathematics Series, vol. 12 (Washington, D.C. : U.S. Government Printing Office, 1951): pp. 36–38.
  2. Donald E. Knuth, The art of computer programming, Vol. 2, Seminumerical algorithms, 2nd edn. (Reading, Mass. : Addison-Wesley, 1981), ch. 3, section 3.1.
  3. Pierre L’Ecuyer & Richard Simard (2007), "TestU01: A Software Library in ANSI C for Empirical Testing of Random Number Generators", ACM Transactions on Mathematical Software, 33: 22