Интервальные методы перевода

Достаточно эффективными методами перевода чисел из СОК в ПСС являются интервальные методы, основанные на интервальных характеристиках чисел. Одна из таких характеристик – номер интервала.

Рассмотрим СОК, заданную системой оснований $p_1, p_2, \ldots, p_n$ с объёмом диапазона $P = p_1\cdot p_2\cdot \ldots \cdot p_n$. Выберем дробящий модуль $p_i$ и проведём дробление заданного диапазона на интервалы путём деления $P$ на модуль $p_i$. Тогда количество интервалов $m = P_i = \frac {P}{p_i}$, а длина интервала определяется величиной модуля.

В результате величину любого числа $A$, заданного в СОК по выбранным основаниям, можно определить по номеру интервала:

$l_A = \left [\frac {A}{p_i}\right ]$ (1),

в котором находится число $A$, и по цифре $\alpha_i$ числа $A$ в СОК по модулю $p_i$, т.е.

$A = p_i \cdot l_A + {\alpha}_i$ (2).

Так как $(p_i, P_i) = 1$, то по теореме Эйлера:

${P_i}^{\varphi(p_i)} \equiv 1\pmod {p_i}$ (3),

где $\varphi(p_i)$ - – функция Эйлера. Причём если $p_i$ – простое число, то $\varphi(p_i) = p_i - 1$.

Число $A$ можно представить в виде

$A = \left| \sum _{i = 1}^{n} {P_i}^{\varphi(p_i)} \cdot \alpha_i \right| \pmod P$ (4).

Для определения номера интервала $l_A$, подставим выражение (4) в (1):

$l_A = \left [\frac {A}{p_i}\right ]$