Составители:
Рубрика:
такое упорядочение чисел ω
j
, j = 0, 1, . . . , n − 1, что каждый
многочлен q
l,m
имеет вид
x
2
m
− ω
s
при некотором неотрицательном целом s.
Д о к а з а т е л ь с т в о этого факта следует из леммы 2.
Определение 8. Пусть j – целое число, 0 ≤ j < 2
k
, a
[d
k−1
d
k−2
. . . d
0
] – его двоичное представление,
j =
k−1
X
i=0
d
i
2
i
, d
i
∈ {0, 1}.
Инверсией числа j будем называть целое число j с двоичным пред-
ставлением [d
0
d
1
. . . d
k−1
],
j =
k−1
X
i=0
d
i
2
k−1−i
.
Операцию перехода от j к
j обозначают rev
k
(от английского
reverse order),
rev
k
: j → j,
т.е. j = rev
k
(j).
Свойство инверсии. Для 0 ≤ j < 2
k−1
справедлива формула
rev
k
(2j) = rev
k
(j)/2. (8.14)
Д о к а з а т е л ь с т в о. Ввиду условия 0 ≤ j < 2
k−1
имеем
j =
P
k−2
i=0
d
i
2
i
, d
i
∈ {0, 1}, и поэтому
rev
k
(j) =
k−2
X
i=0
d
i
2
k−1−i
. (8.15)
2
j
=
k−1
X
i=1
d
i−1
2
i
.
Из последнего соотношения найдём (подстановкой i
0
= i − 1)
rev
k
(2j) =
k−1
X
i=1
d
i−1
2
k−1−i
=
k−2
X
i
0
=0
d
i
0
2
k−2−i
0
. (8.16)
19
Страницы
- « первая
- ‹ предыдущая
- …
- 16
- 17
- 18
- 19
- 20
- …
- следующая ›
- последняя »
