В общем случае трансформирование системы
В общем случае трансформирование системы линейных уравнений по модулю простого числа имеет в три раза более высокую скорость исполнения. Это обусловлено отсутствием операций умножения рациональных чисел, каждая из которых содержит три операции умножения натуральных чисел (полагаем, что операции переноса и сложения имеют на порядок меньшую вычислительную трудоемкость по сравнению с операцией умножения). Исключение составляют исчисление по модулю 2 и по модулю 3.
Преобразование системы линейных уравнений по модулю 3 на множестве (-1, 0, +1) позволяет исключить из набора выполняемых операций умножение натуральных чисел. Все преобразования будут реализуемы с помощью сложения и арифметического отрицания. Это сокращает вычислительную трудоемкость проверки условия в несколько раз (в зависимости от параметров архитектуры ВС). Преобразование системы линейных уравнений по модулю 2 позволяет достичь еще большего быстродействия. Это достигается за счет возможности обрабатывать строки матрицы R как битовые последовательности, тем самым расходуя на сложение и перестановку строк по одной-двум командам микропроцессора. Перестановка столбцов при этом производится циклическими сдвигами двоичных значений.
Недостатками применения малых значений q при проверке необходимого условия является рост вероятности невыполнения условия при истинности значения критерия. Двумя величинами, критически влияющими на вероятность PFN в подобной ситуации, являются величина q и разность между количеством переменных и количеством условий, их связывающими (n-k). В первом приближении (без учета корреляции между значениями элементов матрицы R) данная зависимость описывается следующим выражением:
 |
22 |
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий