Составители:
Рубрика:
1. При q
−j
6= 1 внутренняя сумма в выражении (9.4) представ-
ляет собой сумму n членов геометрической прогрессии со знаме-
нателем q
−j
; используя формулу суммы и обозначение q = e
2π i/n
,
находим
n
X
k=1
q
−kj
= q
−j
n
X
k=1
q
−j(k−1)
= q
−j
n−1
X
k
0
=0
q
−jk
0
= q
−j
q
−nj
− 1
q
−j
− 1
=
= e
−j2πi/n
e
−j2πi
− 1
e
−j2πi/n
− 1
= 0.
2. Случай q
−j
= 1 получается лишь для тех j, для которых
e
−j2πi/n
= 1, что эквивалентно равенству j = nl при некотором
целом l; в этом случае q
−kj
= 1, и потому
n
X
k=1
q
−kj
= n.
Итак, из (9.4) имеем
S = −
X
0≤j<+∞
j=nl
l– целое число
x
j
n
X
k=1
q
−kj
= −n
+∞
X
l=0
x
nl
= −
n
1 − x
n
. (9.5)
Последнее означает, что (x
n
− 1)S = n. Вспоминая определение S
(см. (9.2)) и подставляя (9.5) в (9.2), убеждаемся в справедливо-
сти тождества (9.1). Благодаря аналитичности выражений в (9.2)
видим, что утверждение (9.1) справедливо для всех x 6= e
ik2π/n
,
k = 1, . . . , n. Лемма доказана.
Рассмотрим теперь следующий пример.
Пример. В условиях неограниченного параллелизма займемся
задачей о вычислении x
n
, где x — вещественное число, а n — нату-
ральное. Для отыскания x
n
по схеме сдваивания требуется dlog
2
ne
параллельных умножений.
Если воспользоваться леммой 1, то можно поступить следую-
щим образом:
1) сделать одно параллельное сложение для вычисления раз-
ностей
x − e
ikπ/n
, k = 1, . . . , n,
24
Страницы
- « первая
- ‹ предыдущая
- …
- 21
- 22
- 23
- 24
- 25
- …
- следующая ›
- последняя »
