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

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

Рассмотрим СОК, заданную системой оснований $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 ]$,

в котором находится число $A$ и по цифре $\alpha_i$ числа $A$ в СОК по модулю $p_i$, т.е. $A = p_i \cdot l_A + {\alpha}_i$.

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

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

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

Подставляя выражение для $A$ в ..., получаем

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