Немного компьютерной археологии вам в ленту. Вчера мне понадоб | RUH8

Немного компьютерной археологии вам в ленту. Вчера мне понадобился алгоритм для детектирования циклов (пожалуйста, не спрашивайте зачем) и я взял алгоритм Флойда из Википедии, а заодно прошвырнулся по ссылкам. Меня заинтересовала статья Ричарда Брента (изобретателя похожего алгоритма, который он использовал для факторизации методом Полларда). Brent, R. P., "An improved Monte Carlo factorization algorithm", 1980. В статье, помимо прочего, он отмечает, что LCG в калькуляторах TI-58 (что-то вроде советской программируемой "Электроники", только раньше и мощнее) выдаёт куда более меньший период, чем обещано.

Параметры LCG: m, a, c = 199017, 24298, 99991. Проверил Флойдом. И действительно. Плохой, негодный генератор. С очень короткими циклами. Казалось бы, что тут еще можно добавить? Брент молодец, нашел "уязвимость" в TI. Только есть одно "но". Точность TI-58 десять десятичных разрядов. log2(10^10) = 33.21, длина в битах максимального значение генератора log2(199016*24298+99991) = 32.17. Брент пропустил integer overflow в собственной программе. Если на 64-битном компьютере заменить int на long, то период генератора 199017, как и было обещано. Параметры подобраны так, чтобы период был полным и не было переполнения на калькуляторе. TI - молодцы.

P.S. Это поучительная история, из которой стоит извлечь урок. Ричард Брент - прекрасный ученый, специалист по алгоритмам, и тем не менее, попытка портировать хрень со сраного калькулятора на комп привела к неверным результатам.