Специальные системы модулей

Материал из Модулярная арифметики
(Различия между версиями)
Перейти к: навигация, поиск
(32-битная система)
(4-элементные системы)
 
(не показаны 2 промежуточные версии 2 участников)
Строка 9: Строка 9:
 
Система позволяет избежать сложных операций по модулю вида 2<sup>n</sup>+1, но сокращает динамический диапазон.
 
Система позволяет избежать сложных операций по модулю вида 2<sup>n</sup>+1, но сокращает динамический диапазон.
 
* Residue-to-binary arithmetic converter for the moduli set (2< sup> k</sup>, 2< sup> k</sup>-1, 2< sup> k-1</sup>-1)
 
* Residue-to-binary arithmetic converter for the moduli set (2< sup> k</sup>, 2< sup> k</sup>-1, 2< sup> k-1</sup>-1)
 +
 +
=== {2<sup>2n+1</sup>+2<sup>n</sup>-1, 2<sup>2n+1</sup>-1, 2<sup>n</sup>-1, 2<sup>3n</sup>, 2<sup>3n+1</sup>-1} ===
 +
Система использует набор из трех оснований {2<sup>2n+1</sup>+2<sup>n</sup>-1, 2<sup>2n+1</sup>-1, 2<sup>n</sup>-1} для вычислений и 2 дополнительных модуля {2<sup>3n</sup>, 2<sup>3n+1</sup>-1} для обнаружения и исправления ошибок
 +
* Study of Error Controllability for the New Modulus {2<sup>2n+1</sup>+2<sup>n</sup>-1, 2<sup>2n+1</sup>-1, 2<sup>n</sup>-1, 2<sup>3n</sup>, 2<sup>3n+1</sup>-1}
  
 
== 4-элементные системы ==
 
== 4-элементные системы ==
Строка 26: Строка 30:
 
=== {2<sup>n+2</sup>+3, 2<sup>n+1</sup>+1, 2<sup>n</sup>+1, 2} ===  
 
=== {2<sup>n+2</sup>+3, 2<sup>n+1</sup>+1, 2<sup>n</sup>+1, 2} ===  
 
Модули взаимнопросты для всех n
 
Модули взаимнопросты для всех n
 +
 +
=== {2, 2<sup>n</sup>-1, 2<sup>n</sup>+2<sup>n-1</sup>-1, 2<sup>n+1</sup>+2<sup>n</sup>-1} ===
 +
* [http://elibrary.ru/item.asp?id=1333658 FOUR-MODULI SET {2, 2<sup>n</sup>-1, 2<sup>n</sup>+2<sup>n-1</sup>-1, 2<sup>n+1</sup>+2<sup>n</sup>-1} SIMPLIES THE RESIDUE TO BINARY CONVERTERS BASED ON CRT I]
  
 
== 5-элементные системы ==
 
== 5-элементные системы ==
Строка 49: Строка 56:
 
== 64-битная система ==
 
== 64-битная система ==
 
* 17*31*127*257*511*512*513*8191 = 18910047147635040768 > 2^64
 
* 17*31*127*257*511*512*513*8191 = 18910047147635040768 > 2^64
* 5*7*11*13*17*19*29*31*61*67*127*131*257 = 25396804364038562455 > 2^64
+
* 5*7*11*13*17*19*29*31*61*67*127*131*256 = 25297984113594832640 > 2^64
  
 
== 128-битная система ==
 
== 128-битная система ==

Текущая версия на 11:04, 29 апреля 2013

Содержание

[править] 3-элементные системы

[править] {2n-1, 2n, 2n+1}

{2n-1, 2n, 2n+1} - наиболее часто встречающийся набор специальных модулей. Преимущества: легкость реализаций сумматоров, умножителей и немодульных операций. Система отлично изучена и часто используется.

[править] {2n-1, 2n, 2n+1}

Общий случай предыдущей системы. Оличается легкостью создания обратных преобразователей.

[править] {2n-1, 2n, 2n-1-1}

Система позволяет избежать сложных операций по модулю вида 2n+1, но сокращает динамический диапазон.

  • Residue-to-binary arithmetic converter for the moduli set (2< sup> k</sup>, 2< sup> k</sup>-1, 2< sup> k-1</sup>-1)

[править] {22n+1+2n-1, 22n+1-1, 2n-1, 23n, 23n+1-1}

Система использует набор из трех оснований {22n+1+2n-1, 22n+1-1, 2n-1} для вычислений и 2 дополнительных модуля {23n, 23n+1-1} для обнаружения и исправления ошибок

  • Study of Error Controllability for the New Modulus {22n+1+2n-1, 22n+1-1, 2n-1, 23n, 23n+1-1}

[править] 4-элементные системы

[править] {2n-1, 2n, 2n+1, 2n+1-1}

  • Efficient reverse converters for the four-moduli sets $\{2^{n} - 1, 2^{n}, 2^{n} + 1, 2^{n + 1} - 1\}$ and $\{2^{n} - 1, 2^{n}, 2^{n} + 1, 2^{n-1} - 1\}$

[править] {2n-1, 2n, 2n+1, 2n-1-1}

  • Efficient reverse converters for the four-moduli sets $\{2^{n} - 1, 2^{n}, 2^{n} + 1, 2^{n + 1} - 1\}$ and $\{2^{n} - 1, 2^{n}, 2^{n} + 1, 2^{n-1} - 1\}$

[править] {2n-1, 2n, 2n+1, 22n+1}

  • An efficient reverse converter for the 4-moduli set $\{2^{n} - 1, 2^{n}, 2^{n} + 1, 2^{2n} + 1\}$ based on the new chinese remainder theorem

[править] {2n-1, 2n, 2n+1, 2n-1+1}

Модули взаимнопросты для n = 2k + 1, k = 1, 2, 3...

[править] {2n+2+3, 2n+1+1, 2n+1, 2}

Модули взаимнопросты для всех n

[править] {2, 2n-1, 2n+2n-1-1, 2n+1+2n-1}

[править] 5-элементные системы

[править] {2n-1, 2n, 2n+1, 2n+1-1, 2n-1-1}

Работает для четных n. Динамический диапазон 5n-1 бит.

  • A Residue-to-Binary Converter for a New Five-Moduli Set

[править] Удобные простые числа

[править] Близкие к степени 2

2n-1: 3 (22-1) 7 (23-1) 31 (25-1) 127 (27-1) 8191 (213-1) 131071 (217-1)

2n+1: 5 (22+1) 17 (24+1) 257 (28+1) 65537 (216+1)


2n-3: 13 (24-3) 29 (25-3) 61 (26-3) 509 (29-3) 1021 (210-3) 4093 (212-3) 16381 (214-3)

2n+3: 11 (23+3) 19 (24+3) 67 (26+3) 131 (27+3) 4099 (212+3) 32771 (215+3) 65539 (216+3) 262147 (218+3)

[править] 32-битная система

  • 3*5*7*11*13*17*19*31*32 = 4811046240

[править] 64-битная система

  • 17*31*127*257*511*512*513*8191 = 18910047147635040768 > 2^64
  • 5*7*11*13*17*19*29*31*61*67*127*131*256 = 25297984113594832640 > 2^64

[править] 128-битная система


Персональные инструменты
Пространства имён

Варианты
Действия
Навигация