Система счисления остатков

Эта статья поднимает множество проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалить эти сообщения-шаблоны )

В этой статье отсутствует информация по многим аспектам предмета (см. Страницу обсуждения ). Пожалуйста, разверните статью, чтобы включить эту информацию. Более подробная информация может быть на странице обсуждения . ( Июль 2018 г. )

Эта статья в значительной степени или полностью основана на одном источнике . Соответствующее обсуждение можно найти на странице обсуждения . Пожалуйста, помогите улучшить эту статью , добавив ссылки на дополнительные источники .
Найти источники: «Система счисления остатков» - новости · газеты · книги · ученый · JSTOR ( июль 2018 г. )

Эта статья включает в себя список литературы , связанной литературы или внешних ссылок , но ее источники остаются неясными, поскольку в ней отсутствуют встроенные цитаты . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Июль 2018 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

( Узнайте, как и когда удалить этот шаблон сообщения )

Остаток система счисления ( РНС ) является системой счисления , представляющей целых числа от их значения по модулю несколько попарно копервичных целых чисел , называемых модулями. Такое представление разрешено китайской теоремой об остатках , которая утверждает, что если $N$ является произведением модулей, в интервале длины $N существует$ ровно одно целое число, имеющее любой заданный набор модульных значений. Арифметический остаток системы счисления также называются мульти-модульными арифметическим .

Мультимодульная арифметика широко используется для вычислений с большими целыми числами, обычно в линейной алгебре , поскольку она обеспечивает более быстрое вычисление, чем с обычными системами счисления, даже когда учитывается время преобразования между системами счисления. Другие приложения многомодульной арифметики включают полиномиальный наибольший общий делитель , вычисление базиса Гребнера и криптографию .

Определение [ править ]

Остаточная система счисления определяется набором из $k$ целых чисел

{\ displaystyle \ {m_ {1}, m_ {2}, m_ {3}, \ ldots, m_ {k} \},}

называемые модулями , которые обычно считаются попарно взаимно простыми (то есть любые два из них имеют наибольший общий делитель, равный единице). Системы счисления остатков были определены для непростых модулей, но обычно не используются из-за худших свойств. Поэтому в оставшейся части статьи они рассматриваться не будут. ^[1]

Целое число $x$ представлено в остаточной системе счисления множеством его остатков

{\ Displaystyle \ {x_ {1}, x_ {2}, x_ {3}, \ ldots, x_ {k} \}}

при евклидовом делении по модулям. Это

{\ displaystyle x_ {i} = x \ operatorname {mod} m_ {i},}

а также

{\ displaystyle 0 \ leq x_ {i} <m_ {i}}

для каждого $я$

Пусть $M$ будет произведением всех . Два целых числа, разность которых кратна $M,$ имеют одинаковое представление в остаточной системе счисления, определяемой $m$ $i$ s. Точнее, китайская теорема об остатках утверждает , что каждое из $M$ различных наборов возможных остатков представляет ровно один класс вычетов по модулю $M$ . То есть каждый набор остатков представляет ровно одно целое число в интервале . Для чисел со знаком динамический диапазон равен (когда четное, обычно отображается дополнительное отрицательное значение). ^[2] ${\ displaystyle m_ {i}}$ ${\ displaystyle X}$ ${\ Displaystyle 0, \ точки, М-1}$ ${\ textstyle - \ lfloor M / 2 \ rfloor \ leq X \ leq \ lfloor {\ frac {M-1} {2}} \ rfloor}$ ${\ displaystyle M}$

Арифметические операции [ править ]

Для сложения, вычитания и умножения чисел, представленных в системе счисления остатков, достаточно выполнить одну и ту же модульную операцию с каждой парой остатков. Точнее, если

{\ Displaystyle [м_ {1}, \ ldots, м_ {к}]}

- это список модулей, сумма целых чисел $x$ и $y$ , соответственно представленных остатками, и целое число $z,$ представленное таким, что ${\ Displaystyle [x_ {1}, \ ldots, x_ {k}]}$ ${\ displaystyle [y_ {1}, \ ldots, y_ {k}],}$ ${\ Displaystyle [z_ {1}, \ ldots, z_ {k}],}$

{\ displaystyle z_ {i} = (x_ {i} + y_ {i}) \ operatorname {mod} m_ {i},}

для $i = 1, ..., k$ (как обычно, mod обозначает операцию по модулю, состоящую в взятии остатка от евклидова деления на правый операнд). Аналогично определяются вычитание и умножение.

Для последовательности операций нет необходимости применять операцию по модулю на каждом шаге. Его можно применять в конце вычисления или во время вычисления, чтобы избежать переполнения аппаратных операций.

Однако такие операции, как сравнение величин, вычисление знака, обнаружение переполнения, масштабирование и деление, трудно выполнять в системе счисления остатков. ^[3]

Сравнение [ править ]

Если два целых числа равны, то все их остатки равны. И наоборот, если все остатки равны, то эти два числа равны, или их различие является кратным $M$ . Отсюда следует, что проверить равенство несложно.

Напротив, проверка неравенств ( $x < y$ ) затруднена и обычно требует преобразования целых чисел в стандартное представление. Как следствие, такое представление чисел не подходит для алгоритмов, использующих тесты неравенства, таких как евклидово деление и алгоритм Евклида .

Подразделение [ править ]

Деление в остаточных системах счисления проблематично. С другой стороны, если он взаимно прост с (то есть ), то ${\ displaystyle B}$ ${\ displaystyle M}$ ${\ displaystyle b_ {i} \ not = 0}$

{\ displaystyle C = A \ cdot B ^ {- 1} \ mod M}

легко рассчитывается по

c_{i}=a_{i}\cdot b_{i}^{-1}\mod m_{i},

где является мультипликативным обратным по модулю , и мультипликативен обратный по модулю . $B^{-1}$ $B$ $M$ $b_{i}^{-1}$ $b_{i}$ $m_{i}$

Приложения [ править ]

Этот раздел нуждается в расширении . Вы можете помочь, добавив к нему . ( Июль 2018 г. )

У RNS есть приложения в области цифровой компьютерной арифметики . Разложив при этом большое целое число на набор меньших целых чисел, большое вычисление может быть выполнено как серия меньших вычислений, которые могут выполняться независимо и параллельно.

См. Также [ править ]

Система покрытия
Система пониженного остатка

Ссылки [ править ]

^ Parhami, Behrooz (2010). Компьютерная арифметика: алгоритмы и конструкции оборудования (2-е изд.). Нью-Йорк, США: Издательство Оксфордского университета . ISBN 978-0-19-532848-6. Архивировано 4 августа 2020 года . Проверено 23 января 2021 . (xxv + 641 стр.)
^ Хунг, CY; Пархами, Б. (1 февраля 1994 г.). «Примерный метод определения знаков для номеров остатков и его применение в отделе RNS» (PDF) . Компьютеры и математика с приложениями . 27 (4): 23–35. DOI : 10.1016 / 0898-1221 (94) 90052-3 .
^ Исупов, Константин (2020-04-07) [2020-03-20, 2020-03-08, 2020-02-17]. «Использование интервалов с плавающей запятой для немодульных вычислений в системе счисления остатков» . Доступ IEEE . 8 : 58603–58619. DOI : 10,1109 / ACCESS.2020.2982365 . ISSN 2169-3536 . Архивировано 23 января 2021 года . Проверено 23 января 2021 .

Дальнейшее чтение [ править ]

Сабо, Николас С .; Танака, Ричард I. (1967). Остаточная арифметика и ее приложения к компьютерным технологиям (1-е изд.). Нью-Йорк, США: Макгроу-Хилл .
Сондерстранд, Майкл А .; Дженкинс, У. Кеннет; Jullien, Graham A .; Тейлор, Фред Дж., Ред. (1986). Арифметика системы счисления остатков: современные приложения в цифровой обработке сигналов . IEEE Press Reprint Series (1 ed.). Нью-Йорк, США: IEEE Circuits and Systems Society , IEEE Press . ISBN 0-87942-205-X. LCCN 86-10516 . Код заказа IEEE PC01982. (viii + 418 + 6 страниц)
Червяков, Н.И. Molahosseini, AS; Ляхов П.А. (2017). Преобразование остатков в двоичные для общих наборов модулей на основе приближенной китайской теоремы об остатках . Международный журнал компьютерной математики , 94: 9, 1833-1849, DOI: 10.1080 / 00207160.2016.1247439.
Финько [Финько], Олег Анатольевич [Олег Анатольевич] (июнь 2004 г.). «Большие системы булевых функций: реализация методами модульной арифметики» . Автоматизация и телемеханика . 65 (6): 871–892. DOI : 10,1023 / Б: AURC.0000030901.74901.44 . ISSN 0005-1179 . LCCN 56038628 . S2CID 123623780 . CODEN AURCAT . Mi at1588 .
Червяков, Н.И. Ляхов П.А.; Дерябин, М.А. (2020). Решение на основе системы счисления остатков для снижения стоимости оборудования сверточной нейронной сети . Neurocomputing , 407, 439-453, DOI: 10.1016 / j.neucom.2020.04.018.
Бахар, Жан-Клод; Мелони, Николас; Плантард, Томас (2006-10-06) [июль 2005]. Эффективные основы RNS для криптографии (PDF) . IMACS'05: Всемирный конгресс: Научные вычисления, прикладная математика и моделирование . Париж, Франция. Идентификатор HAL: lirmm-00106470. Архивировано (PDF) из оригинала 23 января 2021 года . Проверено 23 января 2021 . (1 + 7 страниц)
Омонди, Амос; Премкумар, Бенджамин (2007). Системы счисления остатков: теория и реализация . Лондон, Великобритания: Imperial College Press . ISBN 978-1-86094-866-4. (296 стр.)
Мохан, П.В. Ананда (2016). Системы счисления остатков: теория и приложения (1-е изд.). Биркхойзер / Springer International Publishing Switzerland . DOI : 10.1007 / 978-3-319-41385-3 . ISBN 978-3-319-41383-9. LCCN 2016947081 . (351 стр.)
Амир Саббаг, Молахоссейни; де Соуза, Леонель Сибра; Чип-Хонг Чанг, ред. (2017-03-21). Проектирование встроенных систем с использованием специальных арифметических и числовых систем (1-е изд.). Springer International Publishing AG . DOI : 10.1007 / 978-3-319-49742-6 . ISBN 978-3-319-49741-9. LCCN 2017934074 . (389 стр.)
https://web.archive.org/web/20050217165652/http://www.cs.rpi.edu/research/ps/93-9.ps . Архивировано из оригинала на 2005-02-17 . Проверено 23 января 2021 . Отсутствующие или пустые |title=( справка ) алгоритмы деления
Кнут, Дональд Эрвин . Искусство программирования . Эддисон Уэсли .
Харви, Дэвид (2010). «Мультимодульный алгоритм вычисления чисел Бернулли». Математика вычислений . 79 (272): 2361–2370.
Лесерф, Грегуар; Шост, Эрик (2003). «Быстрое умножение многомерного степенного ряда в нулевой характеристике». Электронный журнал SADIO по информатике и исследованиям операций . 5 (1): 1–10.
Апельсин, Себастьен; Рено, Генаэль; Ёкояма, Кадзухиро (2012). «Эффективная арифметика в последовательных алгебраических полях расширения с использованием симметрий». Математика в информатике . 6 (3): 217–233.
Ёкояма, Кадзухиро (сентябрь 2012 г.). «Использование модульных методов для эффективного вычисления идеальных операций». Международный семинар по компьютерной алгебре в научных вычислениях . Берлин / Гейдельберг, Германия: Springer. С. 361–362.
Гладик, Якуб; Шимечек, Иван (январь 2012 г.). «Модульная арифметика для решения линейных уравнений на графическом процессоре». Семинар по численному анализу . С. 68–70.
Перне, Клеман (июнь 2015 г.). «Точная алгоритмическая линейная алгебра: теория и практика». Труды 2015 ACM на Международном симпозиуме по символьным и алгебраическим вычислениям . Ассоциация вычислительной техники . С. 17–18.
Лесерф, Грегуар (2018). «О сложности алгоритма подрезультатов Ликтейга – Роя». Журнал символических вычислений .
Ёкояма, Кадзухиро; Норо, Масаюки; Такэсима, Таку (1994). "Многомодульный подход к факторизации за полиномиальное время двумерных интегральных многочленов". Журнал символических вычислений . 17 (6): 545–563.
Исупов, Константин (2021). «Высокопроизводительные вычисления в системе счисления остатков с использованием арифметики с плавающей запятой». Расчет . 9 (2): 9. DOI: 10.3390 / computation9020009 . ISSN 2079-3197.

[Parhami_2010-1] Parhami, Behrooz (2010). Компьютерная арифметика: алгоритмы и конструкции оборудования (2-е изд.). Нью-Йорк, США: Издательство Оксфордского университета . ISBN 978-0-19-532848-6. Архивировано 4 августа 2020 года . Проверено 23 января 2021 . (xxv + 641 стр.)

[2] Хунг, CY; Пархами, Б. (1 февраля 1994 г.). «Примерный метод определения знаков для номеров остатков и его применение в отделе RNS» (PDF) . Компьютеры и математика с приложениями . 27 (4): 23–35. DOI : 10.1016 / 0898-1221 (94) 90052-3 .

[Isupov_2020-3] Исупов, Константин (2020-04-07) [2020-03-20, 2020-03-08, 2020-02-17]. «Использование интервалов с плавающей запятой для немодульных вычислений в системе счисления остатков» . Доступ IEEE . 8 : 58603–58619. DOI : 10,1109 / ACCESS.2020.2982365 . ISSN 2169-3536 . Архивировано 23 января 2021 года . Проверено 23 января 2021 .

[1]