Орта шаршы әдісі: Санақтан туындаған жасанды кездейсоқтық
Middle-square method
Жалған кездейсоқ сандарды жасау әдісі – орталық квадрат әдісі. Бұл әдіс кемшіліктерімен белгілі, қысқа периоды бар және циклға түсуі мүмкін. Математика, информатика.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Математика мен информатикада ортаңғы квадрат әдісі – псевдокездейі сандарды жасау әдісі. Іс жүзінде, бұл әдіс көптеген қолданулар үшін өте қателі, себебі оның периоды көбінесе өте қысқа және бірнеше елеулі кемшіліктері бар; жеткілікті рет қайталанса, ортаңғы квадрат әдісі бірдей санды қайталап шығаруға немесе тізбектегі бұрынғы санға оралып, шексіз циклге түсуі мүмкін.
In mathematics and computer science, the middle square method is a method of generating pseudorandom numbers. In practice it is a highly flawed method for many practical purposes, since its period is usually very short and it has some severe weaknesses; repeated enough times, the middle square method will either begin repeatedly generating the same number or cycle to a previous number in the sequence and loop indefinitely.
Математикадан
Джон фон Нейман бұл әдісті ойлап тапты және 1949 жылы өткен конференцияда оны сипаттады. 1949 жылғы баяндамасында фон Нейман: "Кездейсоқ сандарды алудың арифметикалық әдістерін қарастыратын адам, әрине, күнәде" деп әзілдеді. Оның түсіндіргеніндей, "нақты кездейсоқ сандар" деген жоқ, оларды жасаудың ғана жолдары бар, ал "ортаңғы квадрат әдісі сияқты қатаң арифметикалық процедура" – мұндай әдіс емес. Дегенмен, ол осы әдістерді перфокарталардан "шын" кездейсоқ сандарды оқудан жүздеген есе жылдам деп тапты, бұл оның ENIAC жұмысы үшін маңызды болды. Ортаңғы квадрат тізбектерінің "жойылуы" олардың артықшылығы екенін анықтады, себебі оны оңай байқауға болады: "әрқашан анықталмаған қысқа циклдар пайда болады деген қорқыныш бар". Ивар Экландтың "Бұзылған текше" кітабында бұл әдісті 1240-1250 жылдар аралығында Эдвин ағасы деп белгілі францискан монах қалай ойлап тапқаны туралы толық мәлімет берілген. Дереккөздерге сәйкес, қолжазба қазір жоғалып кеткен, бірақ Хорхе Луис Борхес Экеландқа Ватикан кітапханасынан алған көшірмесін жіберді. Ортаңғы квадрат алгоритмін Вейль тізбегімен толықтыру кезеңділігі мен кездейсоқтығын жақсартады.
The method was invented by John von Neumann, and was described by him at a conference in 1949. In the 1949 talk, Von Neumann quipped that "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin." What he meant, he elaborated, was that there were no true "random numbers", just means to produce them, and "a strict arithmetic procedure", like the middle square method, "is not such a method". Nevertheless, he found these methods hundreds of times faster than reading "truly" random numbers off punch cards, which had practical importance for his ENIAC work. He found the "destruction" of middle square sequences to be a factor in their favor, because it could be easily detected: "one always fears the appearance of undetected short cycles". The book The Broken Dice by Ivar Ekeland gives an extended account of how the method was invented by a Franciscan friar known only as Brother Edvin sometime between 1240 and 1250. Supposedly, the manuscript is now lost, but Jorge Luis Borges sent Ekeland a copy that he made at the Vatican Library. Modifying the middle square algorithm with a Weyl sequence improves period and randomness.
Әдіс
N цифрлі псевдокездейсоқ сандар тізбесін жасау үшін N цифрлы бастапқы мән құрылады және оның квадраты 2N цифрлы санды береді. Егер нәтиже 2N-ден аз цифрдан тұрса, толықтыру үшін басында нөлдер қосылады. Нәтижедегі ортаңғы N цифр кезектіліктегі келесі сан болып табылады және нәтиже ретінде қайтарылады. Бұл процесс одан әрі қайталанып, қосымша сандар алынады. Әдіс жұмыс істеуі үшін N-нің мәні жұп болуы керек, өйткені N-нің мәні тақ болса, таңдауға бірегей анықталған «ортадағы N цифр» болмайды. Мысалы, егер 3 цифрлы санның квадратын табақ, 6 цифрлы сан шығуы мүмкін (мысалы, 5402 = 291600). Егер ортаңғы 3 цифр болса, онда 6 – 3 = 3 цифр сол және оң жаққа бөлінуі керек. Бұл цифрларды ортаңғы санның екі жағына тең бөлу мүмкін емес, сондықтан «ортаңғы цифрлар» жоқ. N цифрлы жұп санды құру үшін бастапқы мәндерді сол жағынан нөлдермен толықтыруға болады (мысалы, 540 → 0540). N цифрлы сандар генераторы үшін кезең 8N-ден аспауы керек. Егер ортаңғы N цифрдың барлығы нөл болса, генератор мәңгілікке нөлдерді шығарады. Егер тізбектегі санның бірінші жартысы нөлдерден тұрса, келесі сандар нөлге дейін азаяды. Бұл нөлдік тізбектерді анықтау оңай болғанымен, олар бұл әдісті практикалық қолдану үшін тым жиі кездеседі. Ортаңғы квадрат әдісі нөлден басқа да бір санға тоқтап қалуы мүмкін. N = 4 үшін бұл 0100, 2500, 3792 және 7600 мәндерімен болады. Басқа бастапқы мәндер өте қысқа қайталанатын циклдар құрайды, мысалы, 0540 → 2916 → 5030 → 3009. Бұл құбылыстар N = 2 болғанда одан да айқын көрінеді, өйткені 100 мүмкін бастапқы мәннің ешқайсысы 10, 20, 60, 80 немесе 42 ↔ 75 циклға қайта оралмай-ақ 14 итерациядан артық жасамайды.
To generate a sequence of n digit pseudorandom numbers, an n digit starting value is created and squared, producing a 2n digit number. If the result has fewer than 2n digits, leading zeroes are added to compensate. The middle n digits of the result would be the next number in the sequence and returned as the result. This process is then repeated to generate more numbers. The value of n must be even in order for the method to work if the value of n is odd, then there will not necessarily be a uniquely defined "middle n digits" to select from. Consider the following: If a 3 digit number is squared, it can yield a 6 digit number (e. g. 5402 = 291600). If there were to be middle 3 digits, that would leave 6 − 3 = 3 digits to be distributed to the left and right of the middle. It is impossible to evenly distribute these digits equally on both sides of the middle number, and therefore there are no "middle digits". It is acceptable to pad the seeds with zeros to the left in order to create an even valued n digit number (e. g. 540 → 0540). For a generator of n digit numbers, the period can be no longer than 8n. If the middle n digits are all zeroes, the generator then outputs zeroes forever. If the first half of a number in the sequence is zeroes, the subsequent numbers will be decreasing to zero. While these runs of zero are easy to detect, they occur too frequently for this method to be of practical use. The middle squared method can also get stuck on a number other than zero. For n = 4, this occurs with the values 0100, 2500, 3792, and 7600. Other seed values form very short repeating cycles, e. g., 0540 → 2916 → 5030 → 3009. These phenomena are even more obvious when n = 2, as none of the 100 possible seeds generates more than 14 iterations without in reverting to 10, 20, 60, 80, or a 42 ↔ 75 loop.