Специальные системы модулей — различия между версиями
Материал из Модулярная арифметики
Turbo (обсуждение | вклад) |
Ssapra (обсуждение | вклад) (→4-элементные системы) |
||
| (не показано 12 промежуточных версии 2 участников) | |||
| Строка 5: | Строка 5: | ||
=== {2n-1, 2n, 2n+1} === | === {2n-1, 2n, 2n+1} === | ||
Общий случай предыдущей системы. Оличается легкостью создания обратных преобразователей. | Общий случай предыдущей системы. Оличается легкостью создания обратных преобразователей. | ||
| + | |||
| + | === {2<sup>n</sup>-1, 2<sup>n</sup>, 2<sup>n-1</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) | ||
| + | |||
| + | === {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-элементные системы == | ||
| − | === 2<sup>n</sup>-1, 2<sup>n</sup>, 2<sup>n</sup>+1, 2<sup>n+1</sup>-1 === | + | === {2<sup>n</sup>-1, 2<sup>n</sup>, 2<sup>n</sup>+1, 2<sup>n+1</sup>-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\}$ | * 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\}$ | ||
| − | === 2<sup>n</sup>-1, 2<sup>n</sup>, 2<sup>n</sup>+1, 2<sup>n-1</sup>-1 === | + | === {2<sup>n</sup>-1, 2<sup>n</sup>, 2<sup>n</sup>+1, 2<sup>n-1</sup>-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\}$ | * 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\}$ | ||
| − | === 2<sup>n</sup>-1, 2<sup>n</sup>, 2<sup>n</sup>+1, 2<sup>2n</sup>+1 === | + | === {2<sup>n</sup>-1, 2<sup>n</sup>, 2<sup>n</sup>+1, 2<sup>2n</sup>+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 | * 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 | ||
| + | |||
| + | === {2<sup>n</sup>-1, 2<sup>n</sup>, 2<sup>n</sup>+1, 2<sup>n-1</sup>+1} === | ||
| + | Модули взаимнопросты для n = 2k + 1, k = 1, 2, 3... | ||
| + | |||
| + | === {2<sup>n+2</sup>+3, 2<sup>n+1</sup>+1, 2<sup>n</sup>+1, 2} === | ||
| + | Модули взаимнопросты для всех 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-элементные системы == | ||
| + | === {2<sup>n</sup>-1, 2<sup>n</sup>, 2<sup>n</sup>+1, 2<sup>n+1</sup>-1, 2<sup>n-1</sup>-1} === | ||
| + | Работает для четных n. Динамический диапазон 5n-1 бит. | ||
| + | * A Residue-to-Binary Converter for a New Five-Moduli Set | ||
| + | |||
| + | == Удобные простые числа == | ||
| + | === Близкие к степени 2 === | ||
| + | '''2<sup>n</sup>-1''': 3 (2<sup>2</sup>-1) 7 (2<sup>3</sup>-1) 31 (2<sup>5</sup>-1) 127 (2<sup>7</sup>-1) 8191 (2<sup>13</sup>-1) 131071 (2<sup>17</sup>-1) | ||
| + | |||
| + | '''2<sup>n</sup>+1''': 5 (2<sup>2</sup>+1) 17 (2<sup>4</sup>+1) 257 (2<sup>8</sup>+1) 65537 (2<sup>16</sup>+1) | ||
| + | |||
| + | |||
| + | |||
| + | '''2<sup>n</sup>-3''': 13 (2<sup>4</sup>-3) 29 (2<sup>5</sup>-3) 61 (2<sup>6</sup>-3) 509 (2<sup>9</sup>-3) 1021 (2<sup>10</sup>-3) 4093 (2<sup>12</sup>-3) 16381 (2<sup>14</sup>-3) | ||
| + | |||
| + | '''2<sup>n</sup>+3''': 11 (2<sup>3</sup>+3) 19 (2<sup>4</sup>+3) 67 (2<sup>6</sup>+3) 131 (2<sup>7</sup>+3) 4099 (2<sup>12</sup>+3) 32771 (2<sup>15</sup>+3) 65539 (2<sup>16</sup>+3) 262147 (2<sup>18</sup>+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-битная система == | ||
Текущая версия на 08: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
