Кіріспе
Лагг Фибоначчи генераторы (LFG немесе кейде LFib) – псевдокездейсоқ сан генераторының мысалы. Бұл кездейсоқ сан генераторлары класы «стандартты» сызықтық конгруенциялық генераторды жақсартуға бағытталған. Олар Фибоначчи тізбегінің жалпылауына негізделген. Фибоначчи тізбегін рекурренттік қатынас арқылы сипаттауға болады: демек, жаңа мүше – тізбектің соңғы екі мүшесінің қосындысы. Бұл тізбекке мынадай жалпылау қолданылуы мүмкін: Бұл жағдайда жаңа мүше – кез келген екі бұрынғы мүшенің комбинациясы болады. m әдетте 2-нің дәрежесі (m = 2M), көбінесе 232 немесе 264. Оператор – жалпы бинарлық операцияны білдіреді. Ол қосу, алу, көбейту немесе биттік эксклюзивті немесе операциясы (XOR) болуы мүмкін. Осы типтегі генератордың теориясы өте күрделі, сондықтан кездейсоқ мәндерді таңдау жеткіліксіз болуы мүмкін. Бұл генераторлар бастапқы мәндерге өте сезімтал. Осы типтегі генераторлар k сөздік күйді пайдаланады (олар соңғы k мәнді «есінде сақтайды»). Егер қолданылатын операция қосу болса, онда генератор АЛФГ (Additive Lagged Fibonacci Generator) деп аталады, егер көбейту болса, онда ол МЛФГ (Multiplicative Lagged Fibonacci Generator), ал егер XOR операциясы қолданылса, онда ол екі тактілі жалпыланған кері байланыс тізбегі немесе GFSR (Generalized Feedback Shift Register) деп аталады. Мерсенн Твистер алгоритмі – GFSR-дің бір түрі. GFSR сонымен қатар сызықтық кері байланыс тізбегімен (LFSR) де байланысты.
Hence, the new term is the sum of the last two terms in the sequence. This can be generalised to the sequence:
In which case, the new term is some combination of any two previous terms. m is usually a power of 2 (m = 2M), often 232 or 264. The operator denotes a general binary operation. This may be either addition, subtraction, multiplication, or the bitwise exclusive or operator (XOR). The theory of this type of generator is rather complex, and it may not be sufficient simply to choose random values for and These generators also tend to be very sensitive to initialisation. Generators of this type employ k words of state (they 'remember' the last k values). If the operation used is addition, then the generator is described as an Additive Lagged Fibonacci Generator or ALFG, if multiplication is used, it is a Multiplicative Lagged Fibonacci Generator or MLFG, and if the XOR operation is used, it is called a Two tap generalised feedback shift register or GFSR. The Mersenne Twister algorithm is a variation on a GFSR. The GFSR is also related to the linear feedback shift register, or LFSR.
LFG-мен проблемалар
Төрт кранды ауыстырып қосу тіркелімдері туралы мақалада Роберт М. Зифф XOR операторын пайдаланатын LFG туралы айта келе, былай дейді: "Қазір мұндай генераторлардың, әсіресе R(103, 250) сияқты екі кранды ережелері бар генераторлардың, айқын кемшіліктері бар екендігі кеңінен белгілі. Марсалья R(24, 55) және одан кіші генераторлармен өте нашар нәтижелерге тап болды және осы типтегі генераторларды пайдаланудан бас тартуға кеңес берді. Екі кранды генераторлардың, R(a, b) негізгі мәселесі – олардың генератордың өзі арқылы анықталатын , , және арасындағы үш нүктелік корреляцияға ие болуы. Бұл корреляциялар генератордың мөлшеріне тарағанымен, олар әлі де маңызды қателерге алып келуі мүмкін". Бұл тек стандартты LFG-ге қатысты, онда тізбектегі әрбір жаңа сан екі алдыңғы санға тәуелді. Үш кранды LFG кейбір статистикалық проблемаларды – мысалы, Туған күн аралықтары және жалпыланған үштік тесттерден өтпеу сияқты – жоюға көмектесетіні дәлелденді.
Қолданылуы
Freeciv кездейсоқ сандар генераторы ретінде {j = 24, k = 55} параметрімен кідірілген Фибоначчи генераторын пайдаланады. Boost кітапханасы кідірілген Фибоначчи генераторының реализациясын қамтиды. Көшірумен азайту, кідірілген Фибоначчи генераторының қозғалтқышы, C++11 кітапханасында бар. Oracle дерекқоры бұл генераторды өзінің DBMS RANDOM пакетінде (Oracle 8 және одан кейінгі нұсқаларда қолжетімді) іске асырады.