Система из 4 модулей (2^n-1, 2^n+1, 2^(n+1)-1, 2^(n+1)+1)

Материал из Модулярная арифметики
(Различия между версиями)
Перейти к: навигация, поиск
Строка 15: Строка 15:
 
<math>M = ((2^{2n} - 1)*(2^{2n+2} - 1))/3</math>
 
<math>M = ((2^{2n} - 1)*(2^{2n+2} - 1))/3</math>
  
−
== Прямое преобразование ==
+
== Таблица покрытия ==
  
 +
<table>
 +
<tr>
 +
<td style="text-align: center; border: 1px solid black; padding: 2px 5px;">
 +
n
 +
</td>
 +
<td style="text-align: center; border: 1px solid black; padding: 2px 5px;">
 +
Базис
 +
</td>
 +
<td style="text-align: center; border: 1px solid black; padding: 2px 5px;">
 +
Покрываемый интервал [0;M)
 +
</td>
 +
<td style="text-align: center; border: 1px solid black; padding: 2px 5px;">
 +
Бинарная битность
 +
</td>
 +
</tr>
 +
<tr>
 +
<td style="text-align: center; border: 1px solid black;">
 +
2
 +
</td>
 +
<td style="text-align: center; border: 1px solid black;">
 +
3, 5, 7, 9
 +
</td>
 +
<td style="text-align: center; border: 1px solid black;">
 +
[0; 315)
 +
</td>
 +
<td style="text-align: center; border: 1px solid black;">
 +
8
 +
</td>
 +
</tr>
 +
<tr>
 +
<td style="text-align: center; border: 1px solid black;">
 +
3
 +
</td>
 +
<td style="text-align: center; border: 1px solid black;">
 +
7, 9, 15, 17
 +
</td>
 +
<td style="text-align: center; border: 1px solid black;">
 +
[0; 5355)
 +
</td>
 +
<td style="text-align: center; border: 1px solid black;">
 +
12
 +
</td>
 +
</tr>
  
 +
<tr>
 +
<td style="text-align: center; border: 1px solid black;">
 +
4
 +
</td>
 +
<td style="text-align: center; border: 1px solid black;">
 +
15, 17, 31, 33
 +
</td>
 +
<td style="text-align: center; border: 1px solid black;">
 +
[0; 86955)
 +
</td>
 +
<td style="text-align: center; border: 1px solid black;">
 +
16
 +
</td>
 +
</tr>
  
−
== Таблица покрытия ==
+
<tr>
 +
<td style="text-align: center; border: 1px solid black;">
 +
8
 +
</td>
 +
<td style="text-align: center; border: 1px solid black;">
 +
255, 257, 511, 513
 +
</td>
 +
<td style="text-align: center; border: 1px solid black;">
 +
[0; 5726513835)
 +
</td>
 +
<td style="text-align: center; border: 1px solid black;">
 +
32
 +
</td>
 +
</tr>
  
 +
<tr>
 +
<td style="text-align: center; border: 1px solid black;">
 +
16
 +
</td>
 +
<td style="text-align: center; border: 1px solid black;">
 +
65535, 65537, 131071, 131073
 +
</td>
 +
<td style="text-align: center; border: 1px solid black;">
 +
[0; 24595658757787789995)
 +
</td>
 +
<td style="text-align: center; border: 1px solid black;">
 +
64
 +
</td>
 +
</tr>
  
 +
</table>
 +
 +
 +
== Прямое преобразование ==
  
 
== Обратное преобразование ==
 
== Обратное преобразование ==

Версия 11:59, 20 мая 2013

Система модулей {2n-1, 2n+1, 2n+1-1, 2n+1+1} - не является попарно взаимно простой, что несколько сокращает её динамический диапазон, но как будет показано не существенно.

Содержание

Динамический диапазон

M = HOK(2^n - 1, 2^n + 1, 2^{n+1} - 1, 2^{n+1}+1)

где HOK - наименьшее общее кратное.

Что бы найти M, требуется определить наибольший общий делитель(HOD) для всех четырех модулей. Так как 2^n - 1 и 2^n + 1, а также 2^{n+1} - 1 и 2^{n+1}+1 взаимнопросты, то необходимо найти наибольший общий делитель их попарного произведения.

HOD(2^{2n} - 1, 2^{2n+2} - 1) = 3

Отсюда по формуле для вычисления HOK:

M = ((2^{2n} - 1)*(2^{2n+2} - 1))/3

Таблица покрытия

n

Базис

Покрываемый интервал [0;M)

Бинарная битность

2

3, 5, 7, 9

[0; 315)

8

3

7, 9, 15, 17

[0; 5355)

12

4

15, 17, 31, 33

[0; 86955)

16

8

255, 257, 511, 513

[0; 5726513835)

32

16

65535, 65537, 131071, 131073

[0; 24595658757787789995)

64


Прямое преобразование

Обратное преобразование

Источник — «http://vscripts.ru/w/index.php?title=%D0%A1%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0_%D0%B8%D0%B7_4_%D0%BC%D0%BE%D0%B4%D1%83%D0%BB%D0%B5%D0%B9_(2%5En-1,_2%5En%2B1,_2%5E(n%2B1)-1,_2%5E(n%2B1)%2B1)&oldid=397»
Персональные инструменты
Пространства имён

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