LINUX.ORG.RU
Форум — Development  

Помогите решить.

 , ,


1

4

Если лень читать - надо быстро посчитать:

 ( 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..., но она не работает, а что конкретно она там решает - я не понимаю.

 ← 1 2 →
Ответ на: комментарий от dikiy

я собирался считать то, что предлагалось в начале, т.е. (a^n - 1)/(a - 1) % m. только я сначала ступил и думал, что возводить надо по модулю m, затем понял, что по модулю m * (a - 1). далее просто делим результат на a - 1

f1u77y ★★★★
()
Ответ на: комментарий от f1u77y

затем понял, что по модулю m * (a - 1). далее просто делим результат на a - 1

да нифига.

5 mod 45 = 5

5 mod 7 тоже =5.

dikiy ★★☆☆☆
()
Ответ на: комментарий от tyakos

Штука в том, что в цикле мне не надо ничего искать. У меня уже всё найдено на предыдущей операции. На каждой итерации цикла - у меня есть предыдущая степени и сумма всех предыдущих степеней - бесплатно.

registrant27492
() автор топика
Ответ на: комментарий от dikiy

https://github.com/johannesgerer/jburkardt-c/blob/afff376e712b07088c09e729e89... - тут объясняется нормальным языком.


    We are considering a linear congruential random number generator.
    The LCRG takes as input an integer value called SEED, and returns
    an updated value of SEED,
      SEED(out) = ( a * SEED(in) + b ) mod c.
    and an associated pseudorandom real value
      U = SEED(out) / c.
    In most cases, a user is content to call the LCRG repeatedly, with
    the updating of SEED being taken care of automatically.
    The purpose of this routine is to determine the values of AN and BN
    that describe the LCRG that is equivalent to N applications of the
    original LCRG.
    One use for such a facility would be to do random number computations
    in parallel.  If each of N processors is to compute many random values,
    you can guarantee that they work with distinct random values
    by starting with a single value of SEED, using the original LCRG to generate
    the first N-1 "iterates" of SEED, so that you now have N "seed" values,
    and from now on, applying the N-th power of the LCRG to the seeds.
    If the K-th processor starts from the K-th seed, it will essentially
    be computing every N-th entry of the original random number sequence,
    offset by K.  Thus the individual processors will be using a random
    number stream as good as the original one, and without repeating, and
    without having to communicate.
    To evaluate the N-th value of SEED directly, we start by ignoring
    the modular arithmetic, and working out the sequence of calculations
    as follows:
      SEED(0)   =     SEED.
      SEED(1)   = a * SEED      + b
      SEED(2)   = a * SEED(1)   + b = a^2 * SEED           + a * b + b
      SEED(3)   = a * SEED(2)   + b = a^3 * SEED + a^2 * b + a * b + b
      ...
      SEED(N-1) = a * SEED(N-2) + b
      SEED(N) = a * SEED(N-1) + b = a^N * SEED
                                    + ( a^(n-1) + a^(n-2) + ... + a + 1 ) * b
    or, using the geometric series,
      SEED(N) = a^N * SEED + ( a^N - 1) / ( a - 1 ) * b
              = AN * SEED + BN
    Thus, from any SEED, we can determine the result of N applications of the
    original LCRG directly if we can solve
      ( a - 1 ) * BN = ( a^N - 1 ) * b in modular arithmetic,
    and evaluate:
      AN = a^N
registrant27492
() автор топика
Ответ на: комментарий от dikiy

Что-то я тут решил это прикрутить для общего случая - проверил - не смоглось.

теперь r:=n mod 46656.

И получается

(a^n-1)/(a-1) mod 139968 = (a^r-1)/(a-1) mod 139968.

Берём 46888, берём r 46888 mod 46656 = 232;

Считаем:

(((3877^232)-1)/(3877-1)) % 139968
123928
(((3877^46888)-1)/(3877-1)) % 139968
30616

Но чёт пока писал это взглянув на 46656 я что-то заподозрил и поделил его на 139968 и вот оно как вышло:

(((3877^(139968 + 232))-1)/(3877 - 1)) % 139968
123928

Что как бэ логично.

Так что переделываю этот пост из нытья в спасибо - работает.

Ещё раз - спасибо.

registrant27492
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
 ← 1 2 →
Development