Главное


Выбор оптимальных оснований СОК

Пусть диапазон представления чисел в СОК равен P = p1 p2 . pn. Поскольку желательно, чтобы P было как можно большим, проще всего принять p1 наибольшим нечетным числом, соответствующим машинному слову, в качестве p2 принять наибольшее нечетное число < p1, взаимно простое с p1, а в качестве p3 - наибольшее нечетное число < p2, взаимно простое как с p1, так и с p2, и т.д., пока не наберется столько pj, сколько будет достаточно для образования нужного P [1].

При работе на двоичных компьютерах иногда желательно выбирать модули pj иным образом:

pj = 2ej - 1. (1.11)

Другими словами, значение каждого модуля на единицу меньше очередной степени двойки. Такой выбор значения модуля pj зачастую упрощает выполнение основных арифметических операций, т.к. выполнять вычисления с числами, представленными по модулю 2ej - 1, несколько проще, чем с числами, представленными в обратном коде. После того, как значения модулей выбраны таким образом полезно несколько ослабить условие 0 ≤ ai < pj и потребовать только, чтобы

0 ≤ ai < 2ej, (1.12)

ai ≡ N (mod 2ej - 1), (1.13) = (а1, а2, ., аn). (1.14)

Таким образом, значение pj = 2ej - 1 принимается в качестве оптимального, поскольку это означает, что pj может быть любым ej - битовым двоичным числом [1].

Для работы с модулями вида 2ej - 1 необходимо знать, при каких условиях число 2e - 1 является взаимно простым с числом 2f - 1. К счастью для этого существует очень простое правило

gcd(2e - 1, 2f - 1) = 2 gcd(e, f) - 1. (1.15)

Формула (2.15) утверждает в частности, что 2e - 1 и 2f - 1 взаимно просты тогда и только тогда, когда взаимно просты e и f. Формула (1.15) следует из алгоритма Евклида и тождества

(2e - 1) (mod(2f - 1)) = 2e(mod f) - 1. (1.16)

Поэтому на компьютере с длиной слова 232 можно выбрать p1 = 229 - 1, p2 = 225 - 1, p3 = 223 - 1, p4 = 219 - 1, p5 = 217 - 1, p6 = 213 - 1, p7 = 211 - 1, p8 = 27 - 1 что обеспечивает эффективность сложения, вычитания и умножения целых чисел в интервале вплоть до p1 p2 p3 p4 p5 p6 p7 p8 < 2144 . В данном курсовом проекте для представления 64-х битных чисел используется следующая система модулей: (13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61) - все они взаимно просты друг с другом, их произведение равно 50 774 191 064 678 342 417> 18 446 744 073 709 551 616. Каждый из модулей не превышает 6 бит, то есть операции сложения и умножения будут производиться над 6-битными числами.

Другие статьи по теме

Исследование параметров и аномалий длинной оптической линии
В настоящее время системы связи стали одной из основ развития общества. Спрос на услуги связи, от обычной телефонной связи до широкополосного доступа в Интернет, постоянно растет. Это п ...

Исследование звуковой системы ПК с помощью диодной пластины
С ростом популярности беспроводных технологий расширяется и сфера их применения. В дипломной работе рассмотрено решение, построенное на принципе передачи медиаданных по беспроводным кан ...

Усилитель мощности переменного сигнала
Темой курсовой работы является разработка усилителя мощности переменного сигнала. Усилитель имеет дифференциальный вход, бестрансформаторный выход и плавную регулировку усиления от «0» д ...

www.techspirit.ru © 2021