/>
(2.1)
або.
Для твору отримаємо вираз
, (2.2)
де - ціле невід'ємне число, що задовольняє умові,
. Прирівнюючи НД до A, отримаємо:
(2.3)
Вираз (2.3) однозначно визначає цифри приватного. Таким чином, поділ у разі, коли воно точно здійснимо (т. Е. Коли А кратно В), може здійснюватися порозрядним поділом цифр на. Тут поразрядное поділ розуміється в тому сенсі, що якщо безпосередньо не ділиться без остачі на, то до додається стільки разів, щоб ділилося без остачі на ().
За умови такий розподіл єдиним чином визначить цифру. Зауважимо, що такий поділ можливий при додатковому умови.
Приклад. Нехай дана система підстав, обсяг діапазону. Розділимо число на.
Підбираємо числа: отримуємо
. Використовуючи будь-який з розглянутих вище методів перекладу, можна переконатися, що
Ми розглянули найбільш простий випадок ділення, а саме коли ділене остачі поділялося на дільник. У загальному ж випадку поділ представляє одну з найбільш трудомістких арифметичних операцій.
Перед розглядом інших випадків поділу в системі залишкових класів розглянемо одну з найважливіших операцій - операцію розширення системи підстав.
Завдання розширення системи підстав можна сформулювати наступним чином: знайти залишкове подання числа за новим основи (новими підставах), якщо відомо подання числа з інших підстав, тобто знайти залишок від ділення на число, якщо відомі залишки від ділення на інші числа.
Один із шляхів розширення системи підстав полягає у перекладі числа в позиційну систему числення і обчисленні залишку від ділення на новий модуль. Треба визнати, що цей шлях не є раціональним з погляду кількості операцій.
Інший метод розширення системи підстав дозволяє визначити цифру числа за новим основи, базуючись на таких позиційних характеристиках числа, як ранг числа, слід числа, які вимагають розрахунку ряду параметрів (ортогональних базисів, їх ваг, мінімальних псевдоортогональних чисел, їх рангів з кратностями ), обчислення яких може здатися громіздким. Проте всі ці параметри визначаються тільки підставами системи, тому можуть бути розраховані заздалегідь. Більш того, за допомогою зазначених позиційних характеристик можуть бути організовані й інші немодульние процедури, що дозволяє побудувати машинну арифметику.
Ще один шлях вирішення поставленого завдання являє собою переклад числа з СОК в ОПСС з додатковим фінальним кроком, причому даний метод має низку переваг перед іншими:
по-перше, всі обчислення йдуть в паралельних каналах по окремим модулям;
по-друге, не потрібно обчислення великої кількості додаткових величин (необхідна наявність в пам'яті тільки констант);
по-третє, можливе отримання розширеного представлення числа відразу по декількох додатковим підставах, що не впливає на швидкодію всієї операції.
Розглянемо цей метод.
Нехай СОК складається з підстав. Обсяг діапазону цієї системи буде. Додамо до числа підстав СОК нову підставу. Обсяг діапазону цієї системи. Тоді будь-яке число A з діапазону в узагальненій позиційній системі числення представимо у вигляді. Якщо число A буде лежати в первісному діапазоні, то в ОПСС цифра. Цей факт і використовується для отримання залишку від ділення числа A на нову підставу СОК.
Нехай число A мало уявлення з таких підстав. Додаємо нову підставу, тоді число в системі підстав, де - залишок від ділення числа A на, тобто шукана цифра по новому основи.
Для визначення цієї цифри розглядаємо алгоритм переведення числа з СОК в ОПСС, включаючи невідому цифру в проведені операції. При цьому ми послідовно будемо отримувати цифри ОПСС і вираз для цифри. Але так як за припущенням число, то цифра. З отриманого співвідношення і визначаємо шукану цифру.
Цей алгоритм може бути трохи видозмінений за рахунок наступного властивості:
Фактично величина використовується тільки на останньому кроці визначення цифри. Тому в стовпці по новому основи з самого початку можна записати нуль і застосувати алгоритм переведення числа з СОК в ОПСС.
Нехай за цим алгоритмом буде отримано що для числа. Тоді для числа A можна знайти із співвідношення:
Так як результат освіти цифри в СОК по новому основи залежить тільки від перших цифр, то операцію розширення можна проводити відразу по декількох підставах.
Приклад. Нехай задана система підстав,,,
, обсяг діапазону. І нехай задано число в цій системі підстав. Знайдемо розширене подання цього числа, додаючи модулі і.
Для цього запишемо нулі в якості невідомих цифр і застосуємо вищерозглянутий алгоритм розширення системи підстав.
Константи обчислені заздалегідь і записані у вигляді матриці
.
Тоді отримуємо:
Таблиця 2.1 ...
