перекладу, як традиційні (метод ортогональних базисів; переклад числа в ОПС), так і недавно з'явилися інтервальні методи перекладу.
. 3.1 Метод ортогональних базисів
Метод відновлення числа по його рештках був знайдений ще в Китаї 2 тис. років тому. Основою цього методу є теорема, названа тому китайська теорема про залишки (КТО).
Теорема. Нехай - попарно взаємно прості числа,
тоді існує єдине невід'ємне рішення по модулю P наступної системи порівнянь:
,
,
...
,
, де.
Ця теорема лежить в основі методу ортогональних базисів при перекладі з системи залишкових класів у позиційну систему числення [7].
Числа, у яких всі цифри нульові, за винятком цифри по підставі, тобто числа виду будемо називати ортогональними по підставі числами.
Нехай підстави системи залишкових класів;
обсяг діапазону системи. З вибором системи визначаються її основні константи - базиси,. Завдання перекладу числа в ПСС полягає у визначенні таких чисел, щоб. Для однозначного визначення на базиси системи накладається ряд обмежень, яким відповідають базиси
,
,
...
які є ортогональними.
Тоді у разі ортогональних базисів,. Ортогональні базиси визначають за формулою
,. (1.18)
де - цілі позитивні числа, які називаються вагами базису, їх визначають з порівнянь
. (1.19)
Систему з підставами, діапазоном, ортогональними базисами,, ...,, ваги яких відповідно рівні,, ...,, називатимемо нормованої по підставі, якщо має місце умова.
Якщо система унормована по найбільшому основи, то таку систему підстав будемо називати просто нормованої системою.
Згідно Китайської теоремі про залишки, число
.
Т.а., якщо знайдені ортогональні базиси для системи підстав, то для переведення числа досить обчислити і ввести цю суму в діапазон відніманням величини, кратній Р, т.е.
(1.20)
де - ранг числа А, що показує скільки разів треба відняти величину діапазону Р з отриманого числа, щоб повернути його в діапазон.
Так як ортогональні базиси повністю визначаються вибором підстав системи, то вони можуть бути заздалегідь обчислені, причому єдиний раз. Рішення порівнянь (1.19) пропонується шукати за допомогою розширеного алгоритму Евкліда.
Приклад. Нехай дана система підстав,, обсяг діапазону. Перевести число в позиційну систему.
Обчислимо ортогональні базиси.
Для цього знайдемо величини
,,,,
.
Шукаємо ваги базисів по (1.19):
;
;
;
.
Тоді по (1.18) отримуємо самі базиси:
,
,
,
,
.
Обчислимо величину числа А, згідно (1.20):
.
Недолік розглянутого методу полягає в тому, що доводиться мати справу з великими числами і, крім того, дії додавання і множення треба виконувати в позиційній системі числення, а отриманий результат необхідно вводити в діапазон відніманням величини, кратній Р.
1.3.2 Переклад в узагальнену позиційну систему числення
Інший метод визначення величини числа пов'язаний з переведенням числа з системи залишкових класів до узагальненої позиційну систему числення (ЗПСО). Для того щоб розглянути цей метод, виявимо зв'язок між поданням деякого числа A в цих двох системах.
Нехай СОК задається основаниями і - число в цій системі. І нехай, - також підстави ОПСС, тоді число A можна представити у вигляді
(1.21)
де () - коефіцієнти (цифри) ОПСС.
Очевидно, що діапазони чисел, які представлені у СОК і ОПСС збігаються, тобто можна говорити про наявність взаємооднозначної відповідності між безліччю представлень чисел в СОК і ОПСС.
Рівність (1.21) можна переписати у вигляді
,
звідки випливає, що цифри ОПСС можуть бути отримані з співвідношень:
, де,
, де,
...
, де (1.22)
Причому при визначенні чисел за формулами (1.22) всі обчислення можна вести в СОК.
Дійсно, з (1.22) випливає, що, тобто- Перша СОК цифра або. Для отримання, спершу представимо у залишковому коді. Очевидно ділиться на. Більше того, взаємно просто з усіма іншими модулями. Отже, для знаходження цифри може бути використана процедура ділення без залишку:. Таким шляхом, за допомогою віднімання і ділення в остаточний записи всі цифри ОПСС можуть бути отримані. При цьому відмічено, що,, і, взагалі, для.
Переклад, здійснюваний згідно з алгоритмом (1.22), містить всього залишкові арифметичні операції віднімання і ділення без залишку, де n...
