Про нахождение второго псевдослучайного числа

http://linuxforum.ru/viewtopic.php?id=1577

эта тема закрыта, и значит задача решена.

Решение - битовая маска, для 32х битной машины long == 32 бита, и значит 2^32 числа, нужна битовая маска длинной 2^32 /8 байт, ==2^29 байт == 512Mb
такую маску можно хранить на любом компе (если в память не влезет, засунем на диск)

А теперь другая задача:


У нас есть генератор ПСЧ, прям как там, только 64х битный. Вопрос - как найти первое повторение?
(битовая маска тут уже не поможет. И тем более SQL)

кстати, это вполне практическая задача. и у неё даже есть решение.

Ну возьмем обычный генератор псевдослучаных чисел - при генерации следующего числа он опирается на предыдущее сгенерированное число, притом там такие алгоритмы, что следующее число полностью определяется предыдущим.
Теперь методом мат. индукции можно легко доказать, что первым повторится именно первое число, ведь если повторится второе, значит перед ним было первое, а если k-ое, то перед ним было k-1-е.

Но это годится именно для математических методов генерации ПСЧ, если при этом используются некоторые случайные события, вроде последних нажатых клавиш и движений мышки - тут уже все не так посто.
Но ведь стандартный рандом именно математический.

drBatty написал:

http://linuxforum.ru/viewtopic.php?id=1577

эта тема закрыта, и значит задача решена.

Решение - битовая маска, для 32х битной машины long == 32 бита, и значит 2^32 числа, нужна битовая маска длинной 2^32 /8 байт, ==2^29 байт == 512Mb
такую маску можно хранить на любом компе (если в память не влезет, засунем на диск)

А теперь другая задача:


У нас есть генератор ПСЧ, прям как там, только 64х битный. Вопрос - как найти первое повторение?
(битовая маска тут уже не поможет. И тем более SQL)

кстати, это вполне практическая задача. и у неё даже есть решение.

Вы что хотите доказать? Что есть и другие задачи? Согласен с Вами. Вот еще одна: Есть односвязный список. Как доказать, что он не зациклен?

ialexander написал:

Но это годится именно для математических методов генерации ПСЧ, если при этом используются некоторые случайные события, вроде последних нажатых клавиш и движений мышки - тут уже все не так посто.

нет, просто: в условии сказано "ПСП". откуда у вас "случайные"? я не говорил про случайные числа.

Hvzh написал:

Вы что хотите доказать?

вам непонятно условие? я недостаточно чётко изложил? в чём непонятно?
или вам непонятен вопрос?
про списке и жизнь на Марсе я не спрашивал.

ialexander написал:

Теперь методом мат. индукции можно легко доказать, что первым повторится именно первое число, ведь если повторится второе, значит перед ним было первое, а если k-ое, то перед ним было k-1-е.

приведите доказательство (контрпример у меня уже наготове)

drBatty,
Я не про условие. Какая разница, какая разрядность? Мой вопрос в задаче был про алгоритм. Кстати, мою вторую задачу решили, или еще думаете?

Hvzh написал:

drBatty,
Я не про условие.
1)Какая разница, какая разрядность? Мой вопрос в задаче был про алгоритм.
2)Кстати, мою вторую задачу решили, или еще думаете?

1)в закрытой вами(?) теме решение было. но оно действительно только для 32х битного long'а. А если числа больше, то и памяти нужно больше. Как быть, если столько памяти просто нет? Вы полагаете, что это невозможно? ну докажите.
2)а что там думать, ответ в книжках есть. причём тут предложенная мной задача? (на которую кстати так-же дан ответ, например у Кнута).

Hvzh написал:

Есть односвязный список. Как доказать, что он не зациклен?

а чем, кстати, эта задача отличается от моей?

drBatty,
Блин...

drBatty написал:

приведите доказательство (контрпример у меня уже наготове)

Давайте контрпример, доказательство вы процитировали.

ialexander написал:

первым повторится именно первое число

x[n+1]=|x[n]-1|
при x[0]=7

drBatty написал:

x[n+1]=|x[n]-1|
при x[0]=7

расшифруйте пожалуйста. просто я не вижу здесь повторения.

n+1-ое число равно модулю предыдущего минус 1? при первом числе равном 7? не понимаю.

7 6 5 4 3 2 1 0 1 0 1 0 1 0 1...