Если лень читать - надо быстро посчитать:
( 3877^n)- 1) / ( 3877 - 1 ) mod 139968, где n - числа порядка 10^9.Предыстория. Тут недавно в новостях в новости про раст разговор зашел про бенчмарки, а конкретно про fasta(http://benchmarksgame.alioth.debian.org/u64q/fasta-description.html#fasta), но это не важно.
Решил я значит тут запилить масштабируемый lc-генератор. Я искал в интернетах что-то подобное - нашел только: https://github.com/johannesgerer/jburkardt-c/blob/afff376e712b07088c09e729e89... но оно не работает и полезного я нашёл там только:
SEED(N) = a^N * SEED + ( a^N - 1) / ( a - 1 ) * b
Но до этого я смог дойти сам. В конечном итоге я всё запилил - всё работает, но при распараллеливании возникла проблема.
Надо инициализировать каждый воркер значением: a^N mod m и ( a^N - 1) / ( a - 1 ) mod m.
Посчитать быстро a^N mod m - труда не составляет, ибо a^(N/ 2) ^ 2 = a^N. Но вот как посчитать ( a^125000000 - 1) / ( a - 1 ) mod m - я так и не осилил.
Сейчас использую кастыль(но он работает дольше чем генерация 250кк чисел на одном ведре):
double mod_139968(double n) {
return n + (floor(n * 1. / 139968) * -139968);
}
double calc_sumpown(uint64_t n) {
double sum = 1, apown = 1;
while(--n) {
sum += (apown = mod_139968(apown * 3877));
}
sum = mod_139968(sum);
return sum;
}
Я уже сижу над этим дня 3-4 и перегуглил всё что мог - не помогло. Я даже не могу придумать/найти ключевые слова чтобы что-то на эту тему нагуглить.
По ссылке выше есть https://github.com/johannesgerer/jburkardt-c/blob/afff376e712b07088c09e729e89..., но она не работает, а что конкретно она там решает - я не понимаю.
