Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Про алгоритм rand, srand


Автор: bugmenot 14.6.2009, 01:02
Я знаю, что в Visual C++ эти функции заданы примерно так:

Код

unsigned int seed;

void srand(unsigned int new_seed)
{
    seed = new_seed;
}

int rand()
{
    return ((seed = seed * 214013 + 2531011) >> 16) & 0x7FFF;
}


А это значит, что seed после каждого вызова rand будет равняться:
(seed*214013+2531011)&0xFFFFFFFF

И не вызывая rand, мы можем узнать, какой seed будет, например, через 5 вызовов.
А вопрос у меня такой: зная текущий seed, можно ли узнать предыдущий?


С математической точки зрения:
a = (b*214013+2531011) mod 0x100000000
Зная b, можно легко узнать a
А вот зная только a, можно узнать b? (Не делая данную операцию 0xFFFFFFFF раз smile)
P.S. 0x100000000 равняется 4294967296

В Википедии про это тоже что-то написано, но я ничего не понял %)
http://ru.wikipedia.org/wiki/%D0%9B%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D1%8B%D0%B9_%D0%BA%D0%BE%D0%BD%D0%B3%D1%80%D1%83%D1%8D%D0%BD%D1%82%D0%BD%D1%8B%D0%B9_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4

Автор: Pavia 14.6.2009, 02:51
a = (b*214013+2531011) mod 0x100000000
Тут нет однозначности есть множество вариантов ответов.

Возможно два случая 

(b*214013+2531011) меьше 0x100000000 и тогда (b*214013+2531011) равно a
И второй вариант  (b*214013+2531011) больше 0x100000000 и тогда  с учетом что и b тоже 32 бита.
(b*214013+2531011) =a+I*0x100000000
(0xFFFFFFFF*214013+2531011)=0x343FD00235AC6  откуда I от 0 до 214014

b=(a+I*0x100000000 - 2531011) / 214013
В висуале идет вычисления в long формате в отличии от твоего кода. 

Автор: bugmenot 15.6.2009, 22:50
Например b=123456
a = (123456*214013+2531011) & 0xFFFFFFFF = 0x626F9F803 & 0xFFFFFFFF = 0x26F9F803

А теперь ситуация, в которой мы знаем только то, что a=0x26F9F803 (653916163)
Можно ли узнать b?
По форумуле: b=(a+I*0x100000000 - 2531011) / 214013
Какой I брать?

Цитата(Pavia @  14.6.2009,  02:51 Найти цитируемый пост)
В висуале идет вычисления в long формате в отличии от твоего кода.  

Да, верно.
Но в 32 битной системе это не имеет значение.

Автор: Pavia 16.6.2009, 00:27
Цитата(bugmenot @  15.6.2009,  22:50 Найти цитируемый пост)
Какой I брать?

Все брать и все дадут верное решение.

Автор: bugmenot 16.6.2009, 00:32
Что значит все?
То есть любой?
0, например, не подходит, получается дробь

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)