HELP

From

Max Alekseyev (2:5015/60)

To

Ianos Gnatiuc

Date

2002-10-09T18:49:46Z

Area

RU.ALGORITHMS

████ OS/2        Hi, Ianos !

Replying to a message of Ianos Gnatiuc to Max Alekseyev:

 IG>>> inline DWORD irand()
 IG>>> {
 IG>>>     iholdrand *= 214013;
 IG>>>     iholdrand += 2531011;
 IG>>>     return iholdrand;
 IG>>> }

 MA>> Где такой irand() используется? В каком-то рантайме или самопальный?

 IG> частично свой, константы брал из стандартной библиотечке C, в которой
 IG> rand возвращает число из [0..7FFF] (m == 0x8000)

Точнее она взята из рантайма MSVC++. Я константы в десятичной записи не признал ;-)
А стандарт ANSI на RNG в C выглядит так:

unsigned int rand()
{
    seed = seed * 0x41C64E6Du + 0x3039;
    return (seed>>0x10)&0x7FFF;
}

 IG> нужно было случайное 32 битное число, и остался озадаченным, когда
 IG> понял, что те же константы подойдут и для чисел больше чем 7FFF.

 IG> хотя такая функция не совсем корректно работает, так как одно и тоже
 IG> число не может появиться 2 раза подряд, 

Может. После 2^32 итераций.

 IG> поэтому хочется эту функцию на _int64 переселить. :)

Выбирай любые константы, удовлетворяющие указанной теореме для m=2^64.
Можно использовать те же самые кстати, только разрядность увеличить до 64-х.

 MA>> В Кнута есть такая теорема:

 MA>> Длина периода линейной конгруэнтной последовательности (т.е.
 MA>> последовательности, вида X = (a*X+c) % m) равна m тогда и только
 MA>> тогда, когда: 
 MA>> 1. НОД(c,m) = 1 (т.е. c и m взаимно просты) 
 MA>> 2. b=a-1 кратно p для всех простых p - делителей m 
 MA>> 3. b кратно 4, если m кратно 4

Regards,      °°
        Max    ~

--- FleetStreet 1.27.3.8
 * Origin:  (2:5015/60)