ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Oleg I. Khovayko                     2:5020/400     25 Jun 2001  19:50:33
 To : All
 Subject : Re: rnd
 -------------------------------------------------------------------------------- 
 

 Alexander Hritonenkov wrote:
 
 > 
 > Диапазон выводимых чисел - любой. Распpеделение пpямоyгольное (pавномеpное).
 > 
 > Итак, сам алгоpитм.
 > 
 > Имеем n-pазpядное число (для ULONG n=32).
 > 
 >             bitn -> ..... -> bit3 -> bit2 -> bit1 -> bit0
 >               |                        |               |
 >               ^                        v               v
 >               |             /----------+               |
 >               +----------XOR                           |
 >                             \--------------------------+
 > 
 
 Hе так все просто.
 Отвод (левый) не всегда надо делать от bit2. А зависимость эта
 неоднозначная, и определяется приводимостью полинома на поле Галуа.
 
 Как это точно делать - я уже забыл (а занимался этим году эдак в 1992-m), 
 уж извините.
 Hо таблица отводов приведена в книге Хоровиц, Хилл "Искусство схемотехники".
 Там были прописаны отводы для n == 0..31.
 
 Кстати, для n == 22 (или 23 - не помню точно) отводы надо делать из битов
 0 и 1, то есть из соседних.
 В связи с этим есть красивый алгоритм построения такого 22-х битного генератора.
 Смысл алгоритма состоит в том, что при сдвиге int-a влево самый старший, 31-й
 бит задвигается в "C", а предыдущий, 30-и - становится 31-м, то есть знаковым
 "N".
 А если вспомнить о существовании бита переполнения "V", который есть не что
 иное, 
 как V = N xor C, то алгоритм получается таким:
 
 ; r1 - наше число
 
 rndbit:
   asl  r1      ; Сдвинули R1 влево - при этом автоматически случился XOR C,N
   bvc  exit    ; Если V сброшен - ничего не делаем, нолик уже и так там есть
   bis  #^b10000000000,r1 ; Установили младший бит нашего кольца в 1, то есть 
       ; перенесли V в начало кольца
 exit:  return
 
 -- 
 #include <best/regards.hpp>
 Oleg I. KHOVAYKO  
 (301)435-5885 || WEB: http://olegh.spedia.net
 --- ifmail v.2.15dev5
  * Origin: National Center for Biotechnology Information (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    rnd   Gleb Belyakov   06 Jun 2001 12:34:54   Re: rnd   Abbat   07 Jun 2001 05:21:16   rnd   Gleb Belyakov   08 Jun 2001 15:20:42   rnd   Alexander Hritonenkov   12 Jun 2001 12:15:34   Re: rnd   Pavel Fomin   13 Jun 2001 01:26:04   rnd   Ivan Mak   14 Jun 2001 20:38:34   Re: rnd   Oleg I. Khovayko   25 Jun 2001 19:50:33