Машинная арифметика в рациональных числах (лекция 8)

1.

Контрольная работа
по курсу
«Машинная арифметика в рациональных числах»
Москва, 2020

2.

Китайская теорема об остатках и обратное преобразование
X ( x1 , x2 ,..., xn ),
x1 x mod m1 ,
x2 x mod m2
...
xn x mod mn ,
m1 , m2 ,..., mn модули
Китайская теорема об остатках –
существует только одно число,
имеющее остатки по модулям в
диапазоне до произведения модулей
минус один
2

3.

Контрольная работа
Задача 1. Вариант 1. Доказать, что 2n+6∙9n кратно 7
Указание. При доказательстве можно воспользоваться формулой
Задача 1. Вариант 2. Доказать, что если a и b сравнимы по модулю p,
то они также будут сравнимы по модулю d, где d - делитель p
Задача 2. Составить программу для перевода из многомодульной
системы счисления по основаниям m 1 = 3, m 2 = 7, m 3 = 11 числа
Вариант 1: число (2,1,4)
Вариант 2: число (1,5,9)
Задача 3. Сравнить два числа с помощью перевода в смешанную
систему счисления по модулям
m1 = 3; m2 = 5; m3 = 7
Вариант 1: Числа (2,4,6), (1,3,6)
Вариант 2: Числа (1,4,5), (2,4,3)
3

4.

Контрольная работа
Задача 4. Вариант 1 Составить программу для сложения,
вычитания, умножения и прямого преобразования двух
целых чисел по фиксированному набору модулей с
проверкой результатов
Задача 4. Вариант2. Составить программу для обратного
преобразования целого числа по фиксированному набору
модулей с проверкой результатов .
Задача 5. Используя симметрическую модулярную систему
подсчитать
Вариант 1. Чему равно -11+9 по модулям m1 = 3; m2 = 5; m3
= 7. Проверить результат
Вариант 2. Чему равно -9-18 по модулям m1 = 3; m2 = 5; m3 =
7. Проверить результат
4

5.

Контрольная работа
Задача 6. Вариант 1 Вычислить какой максимальный порядок
дроби Фарея данного выражения (a+b) ∙ c + d, если a,b, c, d – дроби
Фарея 2 порядка. Найти значение выражения при a = 1/2, b=1, c=-2,
d=-1/2
Задача 6. Вариант 2 Вычислить какой максимальный порядок
дроби Фарея данного выражения (a-b) ∙ (c + d), если a,b, c, d – дроби
Фарея 2 порядка. Найти значение выражения при a = 1/2, b=1/3,
c=2/3, d=-1/2
5

6.

Представление в смешанной системе счисления
6

7.

Представление в смешанной системе счисления
7

8.

Представление в смешанной системе счисления
t1 = A = d0 + m1(d1 + d2 (m2) + … + dn-1 (m2*m3*…*mn-1 ) )
t1 = d0 + m1*t2
A = t1 mod m1 = d0
t2 = d1 + d2 (m2) + … + dn-1 (m2*m3*…*mn-1 )
t2 mod m2= d1
…
8

9.

Представление в смешанной системе счисления
A = (1, 0, 6)
A = d0 + m1 *d1 + m1 * m2 *d2= 1+ 2 *3+ 3 * 5 *3
d0 = 1
(A-d0) = m1 *d1 + m1 * m2 *d2
(1, 0, 6) – (1,1,1) = (0,4,5)
3^-1 mod 5 = 2
3^-1 mod 7 = 5
m1 ^-1 mod m1 = ?
m1 ^-1 mod m2 =2
m1 ^-1 mod m3=5
(m1 ^-1) = (?, 2,5)
(A-d0)*(m1 ^-1) = (0,4,5)*(?, 2,5) = (?, 3, 4)
d1 = 3
9

10.

Представление в смешанной системе счисления
(A-d0)*(m1 ^-1) = d1 + m2 *d2
(A-d0)*(m1 ^-1) - d1=m2 *d2
(?, 3, 4) – 3 = (?,0,1)
m2 ^(-1) mod m3 = 3
(?,?,3)
d2=(?,0,1)*(?,?,3) = 3
10