Спосіб рандомізації послідовності конгруентних чисел

УКРАЇНА (19) UA (11) 41079 (13) U (51) МПК (2009) G06F 7/58 МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ ДЕРЖАВНИЙ ДЕПАРТАМЕНТ ІНТЕЛЕКТУАЛЬНОЇ ВЛАСНОСТІ ОПИС видається під відповідальність власника патенту ДО ПАТЕНТУ НА КОРИСНУ МОДЕЛЬ (54) СПОСІБ РАНДОМІЗАЦІЇ ПОСЛІДОВНОСТІ КОНГРУЕНТНИХ ЧИСЕЛ 1 2 диться об'єднання всіх циклів, що породжуються генератором, в надцикл, для чого апріорі визначають і записують в пам'ять по одному представникові кожного циклу, а при застосуванні генератора і рандомізації породжуваної ним послідовності, в кінці поточного (на початку наступного) циклу, вибирають числа з пам'яті у випадковому порядку, без повторень і пропусків і використовують їх як вектор початкового завантаження. 2. Спосіб рандомізації за п. 1, який відрізняється тим, що для збільшення періоду повторення рандомізованої послідовності проводиться об'єднання всіх різних надциклів, що породжуються генератором, в гіперцикл, для чого в кожному надциклі міняють представників кілець і порядок вибірки їх з пам'яті. Корисна модель відноситься до обчислювальної техніки і може бути використаний для генерації рівноймовірно розподілених на інтервалі [0, (М-1)] чисел. Для створення послідовностей псевдовипадкових чисел (ПВЧ) широко використовуються генератори конгруентних чисел - пристроїв, які вирішують рівняння S(n)=|S(n-1)*K+C|M, (1) де К,С,М - константи, S(n),S(n-1) - числа, які породжені генератором в «n» і «n-1» дискретний момент часу відповідно. При фіксованому К,С,М такий генератор, може породжувати «k» циклів, що не перетинаються довжиною по t≤(M-1) чисел кожний. При цьому (M-1)=kt. (2) Лише при деяких співвідношеннях К,С,М, такий генератор породжує один цикл завдовжки (М1). Лише в цьому випадку конгруенц генератор по статистичних властивостях близький до генератора рівноймовірно розподілених чисел. У решті всіх випадків конгруенц генератор є генератором псевдовипадкових чисел і для його перетворення в генератор рівноймовірних чисел інтервалу [0,(М1)] необхідно виконати процедуру рандомізації. У [1] досліджені різні типи генераторів псевдо випадкових послідовностей (ПВП), надані рекомендації по підбору чисел К,С,М генератора конгруентних чисел і рекомендації по рандомізації ПВЧ. Слід зазначити, що аналітичних методів оптимального вибору значень не існує, а їх підбір вручну досить трудомісткий, і при уявній простоті, не гарантує рішення за заданий час. Відомий генератор рівноймовірно розподілених чисел [2], в якому завдання рандомізації вирішується шляхом включення в пристрій вузла генерації випадкових логічних рівнів, який складається з аналогового генератора "білого" шуму, підсилювача-обмежувача і рахункового тригера. Про те аналогові генератори "білого" шуму і підсилювачі обмежувачі мають недолік - температурний і часовий дрейф, що міняє статистику вихідної послідовності і, як наслідок, приводить до дрейфу від рівноймовірного розподілу чисел до не рівноймовірного, який не можна виявити. Найбільш близьким по сукупності ознак є генератор рівноймовірно розподілених чисел [3] в якому завдання рандомізації вирішується шляхом включення в пристрій групи вузлів генерації випадкових логічних рівнів, кожен з яких складається з послі (19) UA (11) 41079 (13) U (21) u200808187 (22) 17.06.2008 (24) 12.05.2009 (46) 12.05.2009, Бюл.№ 9, 2009 р. (72) МІТЯНКІНА ТАМАРА ВІКТОРІВНА, UA, ШВИДКИЙ ВАЛЕРІЙ ВАСИЛЬОВИЧ, UA, ЩЕРБА АНАТОЛІЙ ІВАНОВИЧ, UA, МІТЯНКІН МИХАЙЛО ОЛЕКСАНДРОВИЧ, UA (73) ЧЕРКАСЬКИЙ ДЕРЖАВНИЙ ТЕХНОЛОГІЧНИЙ УНІВЕРСИТЕТ, UA (57) 1. Спосіб рандомізації послідовності конгруентних чисел, що породжується при вирішенні рівняння S(n)=|S(n-1)*K+C|M, (1) в якій створюється k циклів з числами в кожному циклі, що не повторюються, який відрізняється тим, що для забезпечення генерації рівноймовірно розподілених на інтервалі [0,(М-1)] чисел прово 3 41079 довно сполучених аналогового генератора "білого" шуму, підсилювача-обмежувача і рахункового тригера. Однак наявність групи аналогових генераторів «білого» шуму, підсилювачів-обмежувачів не усуває, а лише зменшує величину температурного і тимчасового дрейфу, за рахунок взаємної компенсації дрейфів різних генераторів, і, отже, підвищує стабільність роботи не виключаючи дрейфу статистики. Задачею даної корисної моделі є гарантоване перетворення псевдовипадкової послідовності конгруентних чисел в рівноймовірно розподілену на інтервалі [0,(М-1)] послідовність чисел. Даний технічний результат може бути досягнутий, якщо апріорі, до початку застосування генератора, визначити і записати в пам'ять по одному представникові кожного циклу, а з початком застосування, в моментичасу n=dt (d=0.1, 2.(k-1)) вибирати числа з пам'яті у випадковому порядку, без повторень і пропусків і використовувати їх як вектор початкового завантаження (ВПЗ) - числа S(n1). По суті це означає, що задавши на початку ро Комп’ютерна верстка О. Рябко 4 боти ВПЗ одного з циклів генеруємо весь цей цикл, потім завантажуємо ВПЗ іншого циклу і генеруємо другий цикл. Далі процес перебору векторів початкового завантаження і генерації циклів, відповідних цьому ВПЗ необмежено може бути продовжений, за умови випадковості вибору ВПЗ. Це гарантує рівноймовірний розподіл чисел на інтервалі [0,(М-1)] і об'єднання окремих циклів в надцикл. Окремі надцикли можуть бути об'єднані в цикл вищого порядку - в гіперцикл, якщо в процесі формування кожного циклу в надциклі міняти своїх представників, а в кожному надциклі міняти послідовність вибору представників циклів. Перелік джерел: 1. Патент України №31076 «Спосіб генерації випадкових чисел» автори Паршуков С.С., Горицький В.М., Іванченко С.О., кл. G06F7/58, опублікований 15.12.2000. 2. Патент України №36108 «Спосіб генерації випадкових чисел та пристрій для його здійснення» автори Торба О.О., кл. G06F7/58 G07F15/00 опублікований 15.09.2003. Підписне Тираж 28 прим. Міністерство освіти і науки України Державний департамент інтелектуальної власності, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601