Hello, ALL
Приветствую Вас, господа МАТЕМАТИКИ !

Возникла такая вот задача.

Имеется 2 числовых ряда: ( в {} ,будут примеры )

a. Фибоначчи - { 1 2 3 5 8 13 ... } = R1
b. типа Фибоначчи - { 1 3 4 7 11 18 ... } = R2

на _заданном_ отрезке N
{ N ~ 8-ми байтовое целое, т.е. ~ 2^64 }

Дано множество, вычисляемое по формуле:

C = A * R % N , где

С - вычисленный член множества
А - заданная константа
N - отрезок поиска, (N > R, мощность множества)
R - _любое_ число из R1 или R2
% - операция "остаток от деления" в "C" ,
или mod(N) в математической записи

НАЙТИ: R =?= A * R % N
т. е. имеются ли пересечения рядов R и множества
A * R % N, и найти это(и) пересечение(я) (по возможности).
При решении задачи "в лоб" перебором, при N = 2^32 (4 байта)
P3-833 в чистом DOS "дохнет" :-(
Буду весьма признателен за помощь (желательно алгоритм).

Удачи !

Найти пересечение достаточно просто - храни значение элемента множества в бите.
Т.е., сначала R1=R2=0;
...
Ri = Ri-2 + Ri-1
R1 = R1 OR (1 SHL (CRi - 1))

Ну и т.д.

А результат:
Res1 = R1 AND C
Res2 = R2 AND C

останется просмотреть единичные биты....

Задача сводится к следующей:

Пусть R3 = R1+R2.
Для всех Ri принадлежащих R3, Ri<N, найти Rj принадлежащее R3, такое что Ri= ( A*Rj ) mod N , либо доказать что оно не существует.

Если Rj должно быть меньше N, то :

1) Вычисляем R1 и R2 пока Ri < N (они будут содержать ~ по 60-70 членов)
2) Вычисляем С - оно будет содержать не более чем |R1| + |R2| членов.
3) Вычислем собственно пересечение.

На все это потребуется несколько секунд машинного времени

Если Rj может возрастать неограничено, то
Ri=A*Rj mod N=A*(R(j-1)+R(j-2)) mod N = A*R(j-1) + A*R(j-2) mod N = ( (A*R(j-1) mod N ) + (A*R(j-2) mod N) mod N. Т.е. все вычисления ведем в группе вычетов по модулю N (вроде так если я не забыл).

Соответственно алгоритм 3) получается примерно следующий:

Код

R1_j2=0; R1_j1=A % N; R2_j1=A % N; R2_j2=( 3*A ) % N; steps=0; End=0; while(!End){    //Считаем ряд R1    tmp=R1_j1;    R1_j1=( R1_j2 + R1_j1 ) mod N;    R1_j2=tmp;    //Считаем ряд R1    tmp=R2_j1;    R2_j1=( R2_j2 + R2_j1 ) mod N;    R2_j2=tmp;    if( ! ( member(R1_j1,R3)  || member(R2_j2,R3) ) ){        steps++;        if(steps>100) End=1;    }     if( member(R1_j1,R3) ){        steps=0;        delete_member(R1_j1,R3); //Удаляем R1_j1 из множества R3    }     if( member(R2_j1,R3) ){        steps=0;        delete_member(R2_j1,R3); //Удаляем R2_j1 из множества R3    }     if( empty(R3) ){        End=1;    } }

Т.е. считаем пока не найдем разложение каждого члена множества R3, либо за 100 шагов не найдем ни одного нового члена(это конечно эвристика, а что делать .
Наверно имеет смысл ограничить число нерезультативных шагов не константой и функцией от N, например sqrt(N) или N.

Удачи.