Оптимизация умножения больших N-разрядных чисел на основе N-разрядных ДПФ
Рассматривается операция умножения больших чисел, от быстродействия которой зависит быстродействие ассиметричной криптографии. Приведено детальное описание алгоритма реализации операции умножения N-разрядных чисел на основе вычисления N-разрядных БПФ с использованием операций “распаковки” и “упаковк...
Збережено в:
| Дата: | 2012 |
|---|---|
| Автори: | , |
| Мова: | Russian |
| Опубліковано: |
Інститут програмних систем НАН України
2012
|
| Назва видання: | Проблеми програмування |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/86645 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Оптимизация умножения больших N-разрядных чисел на основе N-разрядных ДПФ / А.Н. Терещенко, В.К. Задирака // Проблеми програмування. — 2012. — № 4. — С. 116-130. — Бібліогр.: 6 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-86645 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-866452015-09-25T03:01:59Z Оптимизация умножения больших N-разрядных чисел на основе N-разрядных ДПФ Терещенко, А.Н. Задирака, В.К. Прикладні засоби програмування та програмне забезпечення Рассматривается операция умножения больших чисел, от быстродействия которой зависит быстродействие ассиметричной криптографии. Приведено детальное описание алгоритма реализации операции умножения N-разрядных чисел на основе вычисления N-разрядных БПФ с использованием операций “распаковки” и “упаковки”. Описана процедура, позволяющая строить более простой алгоритм с использованием только формул “распаковки” или только формул “упаковки”. 2012 Оптимизация умножения больших N-разрядных чисел на основе N-разрядных ДПФ / А.Н. Терещенко, В.К. Задирака // Проблеми програмування. — 2012. — № 4. — С. 116-130. — Бібліогр.: 6 назв. — рос. 1727-4907 http://dspace.nbuv.gov.ua/handle/123456789/86645 519.6 ru Проблеми програмування Інститут програмних систем НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Прикладні засоби програмування та програмне забезпечення Прикладні засоби програмування та програмне забезпечення |
| spellingShingle |
Прикладні засоби програмування та програмне забезпечення Прикладні засоби програмування та програмне забезпечення Терещенко, А.Н. Задирака, В.К. Оптимизация умножения больших N-разрядных чисел на основе N-разрядных ДПФ Проблеми програмування |
| description |
Рассматривается операция умножения больших чисел, от быстродействия которой зависит быстродействие ассиметричной криптографии. Приведено детальное описание алгоритма реализации операции умножения N-разрядных чисел на основе вычисления N-разрядных БПФ с использованием операций “распаковки” и “упаковки”. Описана процедура, позволяющая строить более простой алгоритм с использованием только формул “распаковки” или только формул “упаковки”. |
| author |
Терещенко, А.Н. Задирака, В.К. |
| author_facet |
Терещенко, А.Н. Задирака, В.К. |
| author_sort |
Терещенко, А.Н. |
| title |
Оптимизация умножения больших N-разрядных чисел на основе N-разрядных ДПФ |
| title_short |
Оптимизация умножения больших N-разрядных чисел на основе N-разрядных ДПФ |
| title_full |
Оптимизация умножения больших N-разрядных чисел на основе N-разрядных ДПФ |
| title_fullStr |
Оптимизация умножения больших N-разрядных чисел на основе N-разрядных ДПФ |
| title_full_unstemmed |
Оптимизация умножения больших N-разрядных чисел на основе N-разрядных ДПФ |
| title_sort |
оптимизация умножения больших n-разрядных чисел на основе n-разрядных дпф |
| publisher |
Інститут програмних систем НАН України |
| publishDate |
2012 |
| topic_facet |
Прикладні засоби програмування та програмне забезпечення |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/86645 |
| citation_txt |
Оптимизация умножения больших N-разрядных чисел на основе N-разрядных ДПФ / А.Н. Терещенко, В.К. Задирака // Проблеми програмування. — 2012. — № 4. — С. 116-130. — Бібліогр.: 6 назв. — рос. |
| series |
Проблеми програмування |
| work_keys_str_mv |
AT tereŝenkoan optimizaciâumnoženiâbolʹšihnrazrâdnyhčiselnaosnovenrazrâdnyhdpf AT zadirakavk optimizaciâumnoženiâbolʹšihnrazrâdnyhčiselnaosnovenrazrâdnyhdpf |
| first_indexed |
2025-07-06T14:08:31Z |
| last_indexed |
2025-07-06T14:08:31Z |
| _version_ |
1836906878306615296 |
| fulltext |
Прикладні засоби програмування та програмне забезпечення
© А.Н. Терещенко, В.К. Задирака, 2012
116 ISSN 1727-4907. Проблеми програмування. 2012. № 4
УДК: 519.6
А.Н. Терещенко, В.К. Задирака
ОПТИМИЗАЦИЯ УМНОЖЕНИЯ БОЛЬШИХ
N-РАЗРЯДНЫХ ЧИСЕЛ НА ОСНОВЕ N-РАЗРЯДНЫХ ДПФ
Рассматривается операция умножения больших чисел, от быстродействия которой зависит быстродей-
ствие ассиметричной криптографии. Приведено детальное описание алгоритма реализации операции
умножения N-разрядных чисел на основе вычисления N-разрядных БПФ с использованием операций
“распаковки” и “упаковки”. Описана процедура, позволяющая строить более простой алгоритм с ис-
пользованием только формул “распаковки” или только формул “упаковки”.
Введение
Характерной особенностью реше-
ния многих задач аппроксимации функ-
ций, моделирования физических, химиче-
ских (биохимических) процессов, аэроди-
намики, гидродинамики, защиты инфор-
мации является использование вычислений
над многоразрядными числами. Это обу-
славливает актуальность создания эффек-
тивных алгоритмов выполнения операций
над многоразрядными числами для после-
дующей программной реализации на уни-
версальных ЭВМ и для спе-
циализированных аппаратных и програм-
мно-аппаратных комплексов. В данной
статье рассматривается эффективная реа-
лизация операции умножения с использо-
ванием дискретного преобразования Фурье
(ДПФ) [1–5], которое связано с быстрым
вычислением циклической свертки двух
дискретных сигналов. При умножении
двух N -разрядных чисел получается N2 -
разрядный результат, из-за чего не-
обходимо вычислять N2 -разрядную
свертку и N2 -разрядные ДПФ мно-
жителей. В данной работе, которая являет-
ся продолжением [6], описан эффективный
метод вычисления операции умножения с
использованием ДПФ, при котором раз-
рядность исходного N -разрядного сигна-
ла не изменяется, а для вычисления ре-
зультата умножения достаточно знать
1+N первых значений N2 -разрядной
свертки. Для этого приводятся формулы
перехода ДПФ от разрядности N к ДПФ
разрядности N2 и наоборот. Метод [6] по-
зволяет уменьшить число комплексных
операций умножения приблизительно в 2
раза по сравнению со стандартным алго-
ритмом умножения на основе БПФ, при
котором необходимо вычислять все N2
значений свертки. В работе приведена оп-
тимизация метода [6], позволяющая упро-
стить алгоритмическую (программную)
реализацию операции умножения больших
N -разрядных чисел.
Приведем два свойства ДПФ сигна-
лов (см. [6]), которые позволяют упростить
реализацию операции умножения.
Лемма 1 [6]. (Распаковка. Переход
от меньшей разрядности N к большей
N2 ). Четные и нечетные компоненты пер-
вых 1+N разрядов ДПФ 2
ˆ
NZ действи-
тельного сигнала ( )2NZ r , 12,0 −= Nr ,
могут быть вычислены на основе ДПФ NX̂
сигнала ( ) ( ) ( )2 22 2 1N N NX r Z r i Z r= + + ,
0, 1r N= − , используя следующие соотно-
шения:
( ) ( ) ( )2
ˆ ˆ ˆ0 Re 0 Im 0N N NZ X X= + ,
( ) ( ) ( )2 Re 0 Im 0N N NZ N X X= − ,
*
2
ˆ ˆ( 2) ( 2)N NZ N X N= .
( ) ( ) ( )2 2 2
ˆ
N N NZ r A r S r= + ,
( ) ( )* *
2 2 2
ˆ ( )N N NZ N r A r S r− = − ,
( ) ( )( )*
2
1 ˆ ˆ ( )
2 N NNA r X r X N r= + − ,
( ) ( ) ( )( )*2
2
ˆ ˆ
2
r
N
N N N
WS r X r X N r
i
= − − ,
2
2
2
i ir rr N N
NW e e
π π
− −
= = , 12,1 −= Nr .
Прикладні засоби програмування та програмне забезпечення
117
Лемма 2 [6]. (Упаковка. Переход от
большей разрядности N2 к меньшей N ).
В условиях Леммы 1 справедливы сле-
дующие соотношения:
( ) ( ) ( )( )( 2 2
1ˆ ˆ ˆ0 Re 0 Re
2N N NX Z Z N= + +
( ) ( )( ))2 2
ˆ ˆRe 0 ReN Ni Z Z N+ − ,
( ) ( )*
2
ˆ ˆ2 2N NX N Z N= .
( ) ( ) ( )2 2
ˆ
N N NX r A r S r= − ,
( ) ( ) ( )* *
2 2
ˆ
N N NX N r A r S r− = + ,
( ) ( ) ( )( )*
2 22
1 ˆ ˆ
2 N NNA r Z r Z N r= + − ,
( ) ( ) ( )( )*2
2 2 22
r
N
N N N
WS r Z r Z N r
i
−
= − − ,
2
i rr N
NW e
π
−
= , 12,1 −= Nr . (1)
Алгоритм 1. Реализация операции
умножения двух N -разрядных сигналов
на основе N -разрядных ДПФ с использо-
ванием формул распаковки и упаковки.
Приведем его пошаговое описание.
Вход: ( )NU r , )(rVN , 1,0 −= Nr –
N -разрядные множители.
Выход: NR2 – N2 -разрядный ре-
зультат умножения.
Шаг 1. Предвычисление векторов
)(rBN , )(rCN , 1,0 −= Nr .
( )0 0NB ← , ( )0 1NC ← , 0←r ,
Nn 2log← .
1+← rr , ( ) 2cos
2N
vC r
N
π⎛ ⎞← − ⋅⎜ ⎟
⎝ ⎠
,
vrBN ←)( , dkBv N +← )( , 1,0 −= jk ,
2 pj ← , 12n pd − −← , 1,0 −= np .
Шаг 2. Инициализация сигналов ,
( )N̂Y r из ( )NU r , ( )NV r , 1,0 −= Nr .
( ) ( ) ( )2 2 1N N NX r U r iU r← + + ,
)12()2()( ++← riVrVrY NNN , 12,0 −= Nr .
( ) ( ) 0N NX r Y r← ← ,
1,2 −= NNr .
Шаг 3. Вычисление БПФ сигналов
( )ˆ
NX r , ( )N̂Y r , 1,0 −= Nr .
( ) ( )ˆ ˆ1 1N NX i X i X← + , ˆ ˆ( 2) ( 1)N NX i X i X← − ,
( ) ( )ˆ ˆ1 1N NY i Y i Y← + , ( ) ( )ˆ ˆ2 1N NY i Y i Y← − ,
WXX ⋅← , ( )ˆ 2NX X i← , WYY ⋅← ,
( )ˆ 2NY Y i← ,
2
2
1, при 0
, при 1
, при 2
,, при 3
0, ( ) ( 1)
, при 3
1, ( ) ( 1)
N N
N N
W k
W i k
W S iS k
W S iS k
k C k iC k
W k
k C k iC k
← =⎧ ⎫
⎪ ⎪← − =⎪ ⎪
⎪ ⎪← − =⎪ ⎪
⎨ ⎬← − − =
⎪ ⎪
⎪ ⎪⎧ ⎫= + +⎪ ⎪← >⎪ ⎪⎨ ⎬
= − −⎪ ⎪⎪ ⎪⎩ ⎭⎩ ⎭
2
2
←S , rsi +← 11 , rsi +← 22 ,
dss +← 12 , )2(1 dks ⋅⋅← , 1,0 −= dr ,
1,0 −= jk , 12n pd − −← , 2 pj ← ,
1,0 −= np .
Шаг 4. Битовая инверсия сигналов
)(ˆ rX N , )(ˆ rYN , 1,0 −= Nr .
ˆ ˆ( ), ( );
ˆ ˆ ˆ ˆ, ( ) ( ), ( ) ( );
,ˆ ˆ( ) , ( ) .
ˆ ˆ ˆ ˆ, ( ) ( ), ( ) ( )
N N
N N N N
N N
N N N N
X X j Y Y j
r j X j X r Y j Y r
X r X Y r Y
r j X r X r Y r Y r
⎧ ⎫⎧ ⎫← ←
⎪ ⎪⎪ ⎪⎪ ⎪⎪ ⎪< ← ←⎨ ⎬⎪ ⎪
⎨ ⎬⎪ ⎪← ←⎪ ⎪⎪ ⎪⎩ ⎭
⎪ ⎪
≥ ← ←⎪ ⎪⎩ ⎭
)(rBj N← , 1,0 −= Nr .
Шаг 5. Распаковка сигналов
( )ˆ
NX r , ( )N̂Y r , 0, 1r N= − .
( )ˆ 0 Re ImNX X X← + ,
( )ˆ 0 Re ImNY Y Y← + ,
ˆ ( ) Re ImNX N X X← − , ( )ˆ 0NX X← .
ˆ ( ) Re ImNY N Y Y← − , ( )ˆ 0NY Y← .
( ) ( )*ˆ ˆ2 2N NX N X N← ,
( ) ( )*ˆ ˆ2 2N NY N Y N← .
( )ˆ
NX r AX SX← + , ( )N̂Y r AY SY← + ,
**)(ˆ SXAXrNX N −←− , SXWSX ⋅← ,
* *ˆ ( )NY N r AY SY− ← − , SYWSY ⋅← ,
Прикладні засоби програмування та програмне забезпечення
118
( ) ( )( )*1 ˆ ˆ
2 N NAX X r X N r← + − ,
( ) ( )( )*1 ˆ ˆ
2 N NSX X r X N r
i
← − − ,
))(ˆ)(ˆ(
2
1 * rNYrYAY NN −+← ,
))(ˆˆ(
2
1 * rNYY
i
SY NN −−← ,
⎭
⎬
⎫
⎩
⎨
⎧
−−=
++=
←
)1()(,1
)1()(,0
2
2
kiCkCk
kiCkCk
W
NN
NN ,
( )Nk B r← , 12,0 −= Nr .
Шаг 6. Комплексное умножение
сигналов 1
ˆ
NX + , 1N̂Y + , Nr ,0= .
( ) ( ) ( )1 1 1
ˆ ˆ ˆ
N N NZ r X r Y r+ + +← ⋅ , Nr ,0= .
Шаг 7. Упаковка сигнала ( )1
ˆ
NZ r+ ,
Nr ,0= .
( ) ( ) ( )( )(1ˆ ˆ ˆ0 Re 0 Im
2N N NZ Z Z N← + +
( ) ( )( ))ˆ ˆRe 0 ImN Ni Z Z N+ − ,
( ) ( )*ˆ ˆ2 2N NZ N Z N← .
SArZ N −←)(ˆ , **)(ˆ SArNZ N +←− ,
( )*S W S← ⋅ , ( ) ( )( )*1 ˆ ˆ
2 N NA Z r Z N r← + − ,
( ) ( )( )*1 ˆ ˆ
2 N NS Z r Z N r
i
← − − ,
⎭
⎬
⎫
⎩
⎨
⎧
−−=
++=
←
)1()(,1
)1()(,0
2
2
kiCkCk
kiCkCk
W
NN
NN ,
)(rBk N← , 12,0 −= Nr .
Шаг 8. Комплексное сопряжение
сигнала )(ˆ rZN , 1,0 −= Nr .
)(ˆ)(ˆ * rZrZ NN ← , 1,0 −= Nr .
Шаг 9. Вычисление БПФ сигнала
( )ˆ
NZ r , 1,0 −= Nr .
( ) ( )1 1N NZ i Z i Z← + ,
( ) ( )2 1N NZ i Z i Z← − , WZZ ⋅← ,
( )2NZ Z i← ,
2
2
1, при 0
, при 1
, при 2
,, при 3
0, ( ) ( 1)
,при 3
1, ( ) ( 1)
N N
N N
W k
W i k
W S iS k
W S iS k
k C k iC k
W k
k C k iC k
← =⎧ ⎫
⎪ ⎪← − =⎪ ⎪
⎪ ⎪← − =⎪ ⎪
⎨ ⎬← − − =
⎪ ⎪
⎪ ⎪⎧ ⎫= + +⎪ ⎪← >⎪ ⎪⎨ ⎬
= − −⎪ ⎪⎪ ⎪⎩ ⎭⎩ ⎭
22←S , rsi +← 11 , rsi +← 22 ,
dss +← 12 , )2(1 dks ⋅⋅← , 1,0 −= dr ,
1,0 −= jk , pnd −−← 12 , pj 2← , 1,0 −= np .
Шаг 10. Битовая инверсия сигналов
NZ , 1,0 −= Nr .
( )
( ) ( )
( )
,
, ,
, ( ) ( )
N
N N
N
N N
Z r Z
r j Z j Z r
Z Z j
r j Z r Z r
⎧ ⎫⎧ ⎫←
⎪ ⎪⎪ ⎪
< ←⎪ ⎪⎨ ⎬
⎨ ⎬⎪ ⎪←⎪ ⎪⎩ ⎭
⎪ ⎪≥ ←⎩ ⎭
, ( )Nj B r← ,
1,0 −= Nr .
Шаг 11. Комплексное сопряжение
сигнала ( )NZ r , 1,0 −= Nr .
( ) ( )*
N NZ r Z r← , 1,0 −= Nr .
Шаг 12. Результат умножения из
сигнала NẐ , 1,0 −= Nr .
( ) ( )2 2 ReN NR r Z r← ,
( ) ( )2 2 1 ImN NR r Z r+ ← , 1,0 −= Nr .
Примечание. На 5-м шаге (Распа-
ковка) длина сигналов NX̂ , NX̂ увеличи-
вается на один разряд, а на 7-м шаге
(Упаковка) длина сигнала 1
ˆ
+NZ уменьша-
ется на один разряд.
Алгоритм 2. Реализация операции
умножения двух N -разрядных сигналов
на основе N -разрядных ДПФ с исполь-
зованием формул распаковки и упаковки
(в виде подалгоритмов).
Вход: ( )NU r , ( )NV r , 1,0 −= Nr –
N -разрядные множители,
N – число разрядов множителей.
Прикладні засоби програмування та програмне забезпечення
119
Выход: 2NR – N2 -разрядный ре-
зультат умножения.
Шаг 1. ( NС , )NB ←Предвычисле-
ние ( N )1 (см. Алгоритм 3).
Шаг 2. ( NX , )NY ←Инициализа-
ция ( NU , NV , )N (см. Алгоритм 4).
Шаг 3. ˆ
NX ←БПФ ( NX , NC , )N
(см. Алгоритм 5).
Шаг 4. N̂Y ←БПФ ( NY , NC , )N
(см. Алгоритм 5).
Шаг 5. ˆ
NX ←Битовая инверсия
( ˆ
NX , NB , )N (см. Алгоритм 6).
Шаг 6. N̂Y ←Битовая инвер-
сия ( N̂Y , NB , )N (см. Алгоритм 6).
Шаг 7. 1
ˆ
NX + ←Распаковка ( ˆ
NX ,
NC , NB , N ) (см. Алгоритм 7).
Шаг 8. 1N̂Y + ←Распаковка( NŶ , NC ,
NB , N ) (см. Алгоритм 7).
Шаг 9. 1
ˆ
NZ + ←Умножение( 1
ˆ
+NX ,
1
ˆ
+NY , N ) (см. Алгоритм 8).
Шаг 10. ˆ
NZ ←Упаковка( 1
ˆ
+NZ , NC ,
NB , N ) (см. Алгоритм 9).
Шаг 11. NẐ ←Комплексное сопря-
жение( NẐ , N ) (см. Алгоритм 10).
Шаг 12. NZ ←БПФ( NẐ , NC , N )
(см. Алгоритм 5).
Шаг 13. NZ ←Битовая инвер-
сия( NZ , NB , N ) (см. Алгоритм 6).
Шаг 14. NZ ←Комплексное сопря-
жение( NZ , N ) (см. Алгоритм 10).
Шаг 15. 2NR ←Результат умноже-
ния( NZ , N ) (см. Алгоритм 11).
Примечание. См. табл. 1–11. Ре-
зультат вычисления Алгоритмов при
16=N .
Алгоритм 3. Предвычисление.
1 Алгоритмы 3-11 описаны далее
Вход: N – число разрядов ком-
плексного сигнала.
Выход: )(rCN , 1,0 −= Nr – вектор
предвычисленных косинусов,
)(rBN , 1,0 −= Nr – вектор номе-
ров строк для битовой инверсии.
Шаг 1. ( )0 0NB ← ; ( )0 1NC ←
(или ))0(cos()0( NN BC ← ); 0←r ,
Nn 2log← .
Шаг 2. 1←j , 2Nd ← .
Шаг 3. Для p от 0 до 1−n .
Шаг 4. Для k от 0 до 1−j .
Шаг 5. dkBv N +← )( .
Шаг 6.
( )NB r v← , ( ) 2cos .
2N
vC r
N
π⎛ ⎞← − ⋅⎜ ⎟
⎝ ⎠
.
Шаг 7. 1+← rr .
Шаг 8. Конец цикла по k .
Шаг 9. jj ⋅← 2 , 2dd ← .
Шаг 10. Конец цикла по p .
Алгоритм 4. Инициализация.
Вход: )(rU N , )(rVN , 1,0 −= Nr –
действительные сигналы,
N – число разрядов в действитель-
ных и комплексных сигналах.
Выход: )(rX N , )(rYN , 1,0 −= Nr –
комплексные сигналы.
Шаг 1. Для r от 0 до 12 −N .
Шаг 2.
( ) ( ) ( )2 2 1N N NX r U r iU r← + + .
Шаг 3. )12()2()( ++← riVrVrY NNN .
Шаг 4. Конец цикла по r .
Шаг 5. Для r от 2N до 1−N .
Шаг 6. 0←rx , 0←ry .
Шаг 7. Конец цикла по r .
Алгоритм 5. БПФ (Быстрое преоб-
разование Фурье) оптимизированный.
Вход: ( )ˆ
NX r , 1,0 −= Nr – ком-
плексный сигнал,
Прикладні засоби програмування та програмне забезпечення
120
( )NC r , 1,0 −= Nr – вектор пред-
вычисленных косинусов (см. Алгоритм 3.
Предвычисления),
N – число разрядов комплексного
сигнала.
Выход: )(ˆ rX N , 1,0 −= Nr – ДПФ
входного комплексного сигнала ( )ˆ
NX r ,
1,0 −= Nr .
Шаг 1. 22←S , 1←j , 2Nd ← .
Шаг 2. Для p от 0 до 1−n .
Шаг 3. Для k от 0 до 1−j .
Шаг 4. ( )1 2s k d← ⋅ ⋅ , dss +← 12 .
Шаг 5. Для r от 0 до 1−d .
Шаг 6. rsi +← 11 , rsi +← 22 .
Шаг 7. ( )ˆ 2NX X i← ;
2
2
, при 0
( ), при 1
( ), при 2
( ), при 3
0, ( ) ( 1)
, при 3
1, ( ) ( 1)
N N
N N
X X k
X X i k
X X S iS k
X X S iS k
k C k iC k
X X k
k C k iC k
← =⎧ ⎫
⎪ ⎪← ⋅ − =⎪ ⎪
⎪ ⎪← ⋅ − =⎪ ⎪
⎨ ⎬← ⋅ − − =
⎪ ⎪
⎪ ⎪⎧ ⎫= + +⎪ ⎪← ⋅ >⎪ ⎪⎨ ⎬
= − −⎪ ⎪⎪ ⎪⎩ ⎭⎩ ⎭
Шаг 8. ( ) ( )ˆ ˆ2 1N NX i X i X← − ,
( ) ( )ˆ ˆ1 1N NX i X i X← + .
Шаг 9. Конец цикла по r .
Шаг 10. Конец цикла по k .
Шаг 11. Конце цикла по p .
Алгоритм 6. Битовая инверсия.
Вход: ( )ˆ
NX r , 1,0 −= Nr – ком-
плексный сигнал,
( )NB r , 1,0 −= Nr – вектор номе-
ров строк для битовой инверсии (см. Алго-
ритм 3),
N – число разрядов комплексного
сигнала.
Выход: NX̂ – результат битовой
инверсии входного комплексного сигнала
NX̂ .
Шаг 1. Для r от 0 до 1−N .
Шаг 2. ( )Nj B r← .
Шаг 3. Если jr < , то ( )ˆ
NX r X← ,
( ) ( )ˆ ˆ
N NX j X r← , )(ˆ jXX N← .
Шаг 4. Конец цикла по r .
Алгоритм 7. Распаковка.
Вход: ( )ˆ
NX r , Nr ,0= – комплекс-
ный сигнал,
( )NC r , Nr ,0= – вектор предвы-
численных косинусов,
)(rBN , Nr ,0= – вектор номеров
строк для битовой инверсии (см. Алгоритм
3. Предвычисления),
N – число разрядов комплексного
сигнала.
Выход: ( )1
ˆ
NX r+ , Nr ,0= – 1+N
первых разрядов ДПФ действительного
сигнала ( )NU r , Nr ,0= , добавленного N
старшими нулями.
Шаг 1. ( )ˆ 0 Re ImNX X X← + ,
( )ˆ Re ImNX N X X← − ,
( )ˆ 0NX X← .
Шаг 2. Для r от 1 до 1
2
−
N .
Шаг 3. ( )Nk B r← ;
⎭
⎬
⎫
⎩
⎨
⎧
−−=
++=
←
)1()(,1
)1()(,0
2
2
kiCkCk
kiCkCk
W
NN
NN .
Шаг 4. ( ) ( )( )*1 ˆ ˆ
2 N NA X r X N r← + − ,
( ) ( )( )*1 ˆ ˆ
2 N NS X r X N r← − − .
Шаг 5. ( )S i W S← − ⋅ ⋅ .
Шаг 6. ( )ˆ
NX r A S← + ,
( ) * *ˆ
NX N r A S− ← − .
Шаг 7. Конец цикла по r .
Алгоритм 8. Умножение.
Вход: ( )1
ˆ
NX r+ , ( )1N̂Y r+ , Nr ,0= –
1+N первых разрядов ДПФ действитель-
ных сигналов ( )NU r и ( )NV r , Nr ,0= ,
добавленных N старшими нулями;
Прикладні засоби програмування та програмне забезпечення
121
N – число разрядов комплексного
сигнала.
Выход: ( )1
ˆ
NZ r+ , Nr ,0= – резуль-
тат умножения сигналов ( )1
ˆ
NX r+ , ( )1N̂Y r+ ,
Nr ,0= .
Шаг 1.
( ) ( ) ( )1 1 1
ˆ ˆ ˆ0 Re 0 Re 0N N NZ X Y+ + +← ⋅ ,
( ) ( ) ( )1 1 1
ˆ ˆ ˆRe ReN N NZ N X N Y N+ + +← ⋅ .
Шаг 2. Для r от 1 до 1−N .
Шаг 3. ( ) ( ) ( )1 1 1
ˆ ˆ ˆ
N N NZ r X r Y r+ + +← ⋅ .
Шаг 4. Конец цикла по r .
Алгоритм 9. Упаковка.
Вход: ( )1
ˆ
NZ r+ , Nr ,0= – 1+N
первых разрядов умножения ДПФ дейст-
вительных сигналов ( )NU r и ( )NV r ,
1,0 −= Nr , добавленных N старшими
нулями.
( )NC r , 1,0 −= Nr – вектор пред-
вычисленных косинусов,
( )NB r , 1,0 −= Nr – вектор номе-
ров строк для битовой инверсии (см. Алго-
ритм 3. Предвычисления),
N – число разрядов комплексного
сигнала.
Выход: ( )ˆ
NZ r , 1,0 −= Nr – об-
ратное ДПФ сигнала ( )NZ r , 1,0 −= Nr .
Шаг 1.
( ) ( )( )(
( ) ( )( ))
1ˆ ˆ ˆ0 Re 0 Re ( )
2
ˆ ˆRe 0 Re .
N N N
N N
Z Z Z N
i Z Z N
← + +
+ −
Шаг 2. Для r от 1 до 1
2
−
N .
Шаг 3. ( )Nk B r← ;
( ) ( )
( ) ( )
2
2
0, 1
1, 1
N N
N N
k C k iC k
W
k C k iC k
⎧ ⎫= + +⎪ ⎪← ⎨ ⎬
= − −⎪ ⎪⎩ ⎭
.
Шаг 4. ( )( )*1 ˆ ˆ ( )
2 N NA Z r Z N r← + − ,
( ) ( )( )*1 ˆ ˆ
2 N NS Z r Z N r← − − .
Шаг 5. ( ) ( )*S i W S← − ⋅ ⋅ .
Шаг 6. ( )ˆ
NZ r A S← − ,
( ) * *ˆ
NZ N r A S− ← + .
Шаг 7. Конец цикла по r .
Алгоритм 10. Комплексное сопря-
жение.
Вход: ( )ˆ
NX r , 1,0 −= Nr – ком-
плексный сигнал,
N – число разрядов комплексного
сигнала.
Выход: ( )ˆ
NX r , 1,0 −= Nr – ре-
зультат комплексного сопряжения входно-
го сигнала ( )ˆ
NX r , 1,0 −= Nr .
Шаг 1. Для r от 0 до 1−N .
Шаг 2. ( ) ( )*ˆ ˆ
N NZ r Z r← .
Шаг 3. Конец цикла по r .
Алгоритм 11. Результат умноже-
ния.
Вход: ( )NZ r , 1,0 −= Nr – ком-
плексный сигнал,
N – число разрядов комплексного
сигнала.
Выход: ( )2NR r , 12,0 −= Nr –
действительный сигнал, результат умно-
жения )(rU N и )(rVN , 1,0 −= Nr .
Шаг 1. Для r от 0 до 1−N .
Шаг 2. ( ) ( )2 2 ReN NR r Z r N← ,
( ) ( )2 2 1 ImN NR r Z r N+ ← .
Шаг 3. Конец цикла по r .
Далее приводятся табл. 1 – 12 про-
межуточных результатов выполнения каж-
дого шага Алгоритма 2 на примере опера-
ции умножения двух 16-разрядных чисел,
все разряды которых одинаковые и равны
1, что соответствует операции возведения
в квадрат 16-разрядного числа.
Прикладні засоби програмування та програмне забезпечення
122
Таблица 1. Результат вычисления
Алгоритма 3. Предвычисления ( 16=N )
r )(rСN )(rBN
0 1 0
1 0 8
2 0.7071067812 4
3 –0.7071067812 12
4 0.9238795325 2
5 –0.3826834324 10
6 0.3826834324 6
7 –0.9238795325 14
8 0.9807852804 1
9 –0.195090322 9
10 0.555570233 5
11 –0.8314696123 13
12 0.8314696123 3
13 –0.555570233 11
14 0.195090322 7
15 –0.9807852804 15
Таблица 2. Результат вычисления
Алгоритма 4. Инициализация ( 16=N )
r )(),( rVrU NN
)(ˆIm),(ˆIm
),(ˆRe),(ˆRe
rYrX
rYrX
NN
NN ,
0 1 1
1 1 1
2 1 1
3 1 1
4 1 1
5 1 1
6 1 1
7 1 1
8 1 0
9 1 0
10 1 0
11 1 0
12 1 0
13 1 0
14 1 0
15 1 0
Таблица 3. Результат итераций ( 2,1,0=p ) Алгоритма 5. БПФ сигналов ( )ˆ
NX r , ( )N̂Y r
Вход 0=p 1=p 2=p 3=p
r Re Im Re Im Re Im Re Im Re Im
0 1 1 1 1 2 2 4 4 8 8
1 1 1 1 1 2 2 4 4 0 0
2 1 1 1 1 2 2 0 0 0 0
3 1 1 1 1 2 2 0 0 0 0
4 1 1 1 1 0 0 0 0 0 0
5 1 1 1 1 0 0 0 0 0 0
6 1 1 1 1 0 0 0 0 0 0
7 1 1 1 1 0 0 0 0 0 0
8 0 0 1 1 2 0 3.414213562 –1.414213562 6.027339492 –4.027339492
9 0 0 1 1 2 0 3.414213562 –1.414213562 0.8010876326 1.198912367
10 0 0 1 1 2 0 0.5857864376 1.414213562 1.668178638 0.3318213621
11 0 0 1 1 2 0 0.5857864376 1.414213562 –0.4966057627 2.496605763
12 0 0 1 1 0 2 1.414213562 0.5857864376 2.496605763 –0.4966057627
13 0 0 1 1 0 2 1.414213562 0.5857864376 0.3318213621 1.668178638
14 0 0 1 1 0 2 –1.414213562 3.414213562 1.198912367 0.8010876326
15 0 0 1 1 0 2 –1.414213562 3.414213562 –4.027339492 6.027339492
Прикладні засоби програмування та програмне забезпечення
123
Таблица 4. Результат Алгоритма 6. Битовая инверсия сигналов ( )ˆ
NX r , ( )N̂Y r
Вход ( )ˆ
NX r Выход ( )ˆIm NX r
r
Re Im Re Im
0 8 8 8 8
1 0 0 6.027339492 –4.027339492
2 0 0 0 0
3 0 0 2.496605763 –0.4966057627
4 0 0 0 0
5 0 0 1.668178638 0.3318213621
6 0 0 0 0
7 0 0 1.198912367 0.8010876326
8 6.027339492 –4.027339492 0 0
9 0.8010876326 1.198912367 0.8010876326 1.198912367
10 1.668178638 0.3318213621 0 0
11 –0.4966057627 2.496605763 0.3318213621 1.668178638
12 2.496605763 –0.4966057627 0 0
13 0.3318213621 1.668178638 –0.4966057627 2.496605763
14 1.198912367 0.8010876326 0 0
15 –4.027339492 6.027339492 –4.027339492 6.027339492
Таблица 5. Результат Алгоритма 7. Распаковка ( )ˆ
NX r , ( )N̂Y r
Вход ( )ˆ
NX r Выход ( )1
ˆ
NX r+
r
Re Im Re Im
0 8 8 16 0
1 6.027339492 –4.027339492 1 –10.15317039
2 0 0 0 0
3 2.496605763 –0.4966057627 1 –3.296558209
4 0 0 0 0
5 1.668178638 0.3318213621 1 –1.870868412
6 0 0 0 0
7 1.198912367 0.8010876326 1 –1.218503526
8 0 0 0 0
9 0.8010876326 1.198912367 1 –0.8206787908
10 0 0 0 0
11 0.3318213621 1.668178638 1 –0.534511136
12 0 0 0 0
13 –0.4966057627 2.496605763 1 –0.3033466836
14 0 0 0 0
15 –4.027339492 6.027339492 1 –0.09849140336
16 0 0
Прикладні засоби програмування та програмне забезпечення
124
Таблица 6. Результат Алгоритма 8. Умножение ( ) ( )1 1
ˆ ˆ
N NX r Y r+ +⋅
Вход ( )1
ˆ
NX r+ , ( )1N̂Y r+ Выход ( )1
ˆRe NZ r+
r
Re Im Re Im
0 16 0 256 0
1 1 –10.15317039 –102.0868689 –20.30634078
2 0 0 0 0
3 1 –3.296558209 –9.867296025 –6.593116418
4 0 0 0 0
5 1 –1.870868412 –2.500148614 –3.741736824
6 0 0 0 0
7 1 –1.218503526 –0.4847508419 –2.437007051
8 0 0 0 0
9 1 –0.8206787908 0.3264863223 –1.641357582
10 0 0 0 0
11 1 –0.534511136 0.7142978455 –1.069022272
12 0 0 0 0
13 1 –0.3033466836 0.9079807895 –0.6066933672
14 0 0 0 0
15 1 –0.09849140336 0.9902994435 –0.1969828067
16 0 0 0 0
Таблица 7. Результат Алгоритма 9. Упаковка ( )( )ˆ
NZ r
Вход ( )1
ˆ
NZ r+ Выход ( )ˆ
NZ r
r
Re Im Re Im
0 256 0 128 128
1 –102.0868689 –20.30634078 –30.43892677 –58.60296372
2 0 0 0 0
3 –9.867296025 –6.593116418 1.506765433 –5.472869143
4 0 0 0 0
5 –2.500148614 –3.741736824 1.779789167 –0.2292826602
6 0 0 0 0
7 –0.4847508419 –2.437007051 0.7165172097 1.523043005
8 0 0 0 0
9 0.3264863223 –1.641357582 –0.8747817293 2.318692475
10 0 0 0 0
11 0.7142978455 –1.069022272 –3.565639936 2.443431891
12 0 0 0 0
13 0.9079807895 –0.6066933672 –10.46608067 0.5135539076
14 0 0 0 0
15 0.9902994435 –0.1969828067 –70.65764271 –38.49360575
16 0 0
Прикладні засоби програмування та програмне забезпечення
125
Таблица 8. Результат Алгоритма 10. Комплексное сопряжение ( )( )ˆ
NZ r
Вход ( )ˆ
NZ r Выход ( )ˆ
NZ r
r
Re Im Re Im
0 128 128 128 –128
1 –30.43892677 –58.60296372 –30.43892677 58.60296372
2 0 0 0 0
3 1.506765433 –5.472869143 1.506765433 5.472869143
4 0 0 0 0
5 1.779789167 –0.2292826602 1.779789167 0.2292826602
6 0 0 0 0
7 0.7165172097 1.523043005 0.7165172097 –1.523043005
8 0 0 0 0
9 –0.8747817293 2.318692475 –0.8747817293 –2.318692475
10 0 0 0 0
11 –3.565639936 2.443431891 –3.565639936 –2.443431891
12 0 0 0 0
13 –10.46608067 0.5135539076 –10.46608067 –0.5135539076
14 0 0 0 0
15 –70.65764271 –38.49360575 –70.65764271 38.49360575
Таблица 9. Результат Алгоритма 5.
БПФ ( )ˆ
NZ
Таблица 10. Результат Алгоритма 6.
Битовая инверсия ( )( )ˆ
NZ r
Вход ( )ˆ
NZ r Выход ( )ˆ
NZ r
ˆ ˆr
Re Im Re Im
0 128 –128 16 –32
1 –30.43892677 58.60296372 240 –224
2 0 0 144 –160
3 1.506765433 5.472869143 122 –96
4 0 0 80 –96
5 1.779789167 0.2292826602 176 –160
6 0 0 208 –224
7 0.7165172097 –1.523043005 48 –32
8 0 0 48 –64
9 –0.8747817293 –2.318692475 208 –192
10 0 0 176 –192
11 –3.565639936 –2.443431891 80 –64
12 0 0 112 –128
13 –10.46608067 –0.5135539076 144 –128
14 0 0 240 –256
15 –70.65764271 38.49360575 16 0
Вход ( )ˆ
NZ r Выход )(ˆ rZ N
r
Re Im Re Im
0 16 –32 16 –32
1 240 –224 48 –64
2 144 –160 80 –96
3 122 –96 112 –128
4 80 –96 144 –160
5 176 –160 176 –192
6 208 –224 208 –224
7 48 –32 240 –256
8 48 –64 240 –224
9 208 –192 208 –192
10 176 –192 176 –160
11 80 –64 144 –128
12 112 –128 112 –96
13 144 –128 80 –64
14 240 –256 48 –32
15 16 0 16 0
Прикладні засоби програмування та програмне забезпечення
126
Таблица 11. Результат Алгоритма 10.
Комплексное сопряжение ( )(ˆ rZ N )
Таблица 12. Результат Алгоритма 11.
Результат умножения ( )(2 rR N )
Вход )(ˆ rZ N Выход )(ˆ rZ N
r
Re Im Re Im
0 16 –32 16 32
1 240 –224 48 64
2 144 –160 80 96
3 122 –96 112 128
4 80 –96 144 160
5 176 –160 176 192
6 208 –224 208 224
7 48 –32 240 256
8 48 –64 240 224
9 208 –192 208 192
10 176 –192 176 160
11 80 –64 144 128
12 112 –128 112 96
13 144 –128 80 64
14 240 –256 48 32
15 16 0 16 0
Вход )(ˆ rZ N Выход )(ˆ rZ N
r
Re Im )2(2 rR N )12(2 +rR N
0 16 32 1 2
1 48 64 3 4
2 80 96 5 6
3 112 128 7 8
4 144 160 9 10
5 176 192 11 12
6 208 224 13 14
7 240 256 15 16
8 240 224 15 14
9 208 192 13 12
10 176 160 11 10
11 144 128 9 8
12 112 96 7 6
13 80 64 5 4
14 48 32 3 2
15 16 0 1 0
Лемма 3. (Распаковка-Упаковка.
Переход от большей разрядности N2 к
меньшей N , используя фломулы распа-
ковки). В условиях леммы 1 справедливы
следующие соотношения:
( ) ( )*ˆ ˆ
NNZ r Z r← , 1,0 −= Nr . (2)
( ) ( ) ( )( )(1ˆ ˆ ˆ0 Re 0 Re
2N N NX Z Z N← + +
( ) ( )( ))ˆ ˆRe 0 ReN Ni Z Z N+ − ,
( ) ( )*ˆ ˆ2 2N NX N Z N← . (3)
( ) ( ) ( )2 2
ˆ
N N NX r A r S r← + ,
( ) ( ) ( )* *
2 2
ˆ
N N NX N r A r S r− ← − , (4)
( ) ( ) ( )( )*
2
1 ˆ ˆ
2 N NNA r Z r Z N r← + − ,
( ) ( ) ( )( )*2
2
ˆ ˆ
2
r
N
N NN
WS r Z r Z N r
i
← − − , (5)
r
N
i
r
N eW
π
−
=2 , 12,1 −= Nr . (6)
( ) ( )*ˆ ˆ
NNX r X r← , 1,0 −= Nr . (7)
Доказательство. Видно, что форму-
лы (3)–(6) являются формулами распаковки
(лемма 1). Рассмотрим сначала выражения
(2), (3), (7) для 0=r . Так как ( )ˆ 0NZ ,
)(ˆ NZ N – действительные числа, то выпол-
нение выражения (2) для 0=r не оказыва-
ет влияния на результат ( )ˆ 0NX . При
2Nr = выражения )(ˆ)(ˆ * rZrZ NN ← ,
)2(ˆ)2(ˆ * NZNX NN ← ,
( ) ( )*ˆ ˆ2 2NNX N X N← дают результат
)2(ˆ)2(ˆ * NZNX NN ← с учетом свойства
комплексных чисел ( )**a a← .
Сделаем подстановку (2) в (5) и (4)
в (7):
( ) ( ) ( )( )*2 2
ˆ
N N NX r A r S r= + ,
( ) ( ) ( )( )** *
2 2
ˆ
N N NX N r A r S r− = − ,
( ) ( )( ) ( )( )** *
2
1 ˆ ˆ
2 N NNA r Z r Z N r⎛ ⎞= + −⎜ ⎟
⎝ ⎠
,
( ) ( )( ) ( )( )** *2
2
ˆ ˆ ,
2
r
N
N N N
WS r Z r Z N r
i
⎛ ⎞= − −⎜ ⎟
⎝ ⎠
2
i rr N
NW e
π
−
= , 12,1 −= Nr . (8)
С учетом свойств *** )( gfgf ±=± ,
r
N
r
N WW 2
*
2 )( =− , * * *( )f g f g⋅ = ⋅ ,
**f f
i i
⎛ ⎞= −⎜ ⎟
⎝ ⎠
,
Прикладні засоби програмування та програмне забезпечення
127
i
i
−=
1 где f и g – комплексные числа,
выражения для ( )2NA r и ( )2NS r при-
мут вид:
( ) ( )( ) ( )( )** *
2
1 ˆ ˆ
2 N NNA r Z r Z N r⎛ ⎞= + − =⎜ ⎟
⎝ ⎠
( ) ( )( )**1 ˆ ˆ
2 N NZ r Z N r= + − ,
( ) ( )( ) ( )( )
( ) ( )( )
** *2
2
**2
ˆ ˆ
2
ˆ ˆ
2
r
N
N N N
r
N
N N
WS r Z r Z N r
i
W Z r Z N r
i
⎛ ⎞= − − =⎜ ⎟
⎝ ⎠
= − − =
( ) ( )( )
*
*2 ˆ ˆ
2
r
N
N N
W Z r Z N r
i
−⎛ ⎞
= − − −⎜ ⎟⎜ ⎟
⎝ ⎠
.
Подставляя полученные выражения
в (8) получим (1), что и требовалось дока-
зать.
Свойство, доказанное выше, позво-
ляет заменить формулы упаковки формула-
ми распаковки при 12,1 −= Nr , что
уменьшает число подпрограмм при реали-
зации операции умножения больших чисел.
Интересно, что аналогичным обра-
зом можно избежать использования фор-
мул распаковки, заменив их формулами
упаковки.
Алгоритм 12. Распаковка-Упаковка.
Вход: ( )ˆ
N MX r+ , 1,0 −= Nr
( )( 1
ˆ
NX r+ , Nr ,0= , при 1=M ) – ком-
плексный сигнал,
( )NC r , 1,0 −= Nr – вектор пред-
вычисленных косинусов,
( )NB r – вектор номеров строк для
битовой инверсии (см. Алгоритм 3. Пред-
вычисления),
N – число разрядов комплексного
сигнала.
M – режим вычисления (0 – распа-
ковка, 1 – упаковка).
Выход: 1
ˆ
N MX + − , Nr ,0= , ( ˆ ( )NX r ,
1,0 −= Nr , при 1=M ) – преобразован-
ный ДПФ.
Шаг 1. Если 0=M , то
Шаг 2. ( )1
ˆ 0 Re ImNX X X+ ← + ,
( )1
ˆ Re ImNX N X X+ ← − , ( )ˆ 0NX X← .
Шаг 3. Иначе
Шаг 4.
( ) ( ) ( )( )( 1 1
1ˆ ˆ ˆ0 Re 0 Re
2N N NX X X N+ +← + +
( ) ( )( ))1 1
ˆ ˆRe 0 ReN Ni X X N+ ++ − .
Шаг 5. Конец если.
Шаг 6. Для r от 1 до 12 −N .
Шаг 7. ( )Nk B r← ;
⎭
⎬
⎫
⎩
⎨
⎧
−−=
++=
←
)1()(,1
)1()(,0
2
2
kiCkCk
kiCkCk
W
NN
NN .
Шаг 8.
( ) ( )( )*1 ˆ ˆ
2 N NA X r X N r← + − ,
( ) ( )( )*1 ˆ ˆ
2 N NS X r X N r← − − .
Шаг 9. SWiS ⋅⋅−← )( .
Шаг 10. ( )ˆ
NX r A S← + ,
**)(ˆ SArNX N −←− .
Шаг 11. Конец цикла по r .
Тогда в Алгоритме 2 шаг 7–11 за-
меняются следующими выражениями:
Шаг 7. 1
ˆ
+NX ←Распаковка-Упаков-
ка( NX̂ , NB , NB , N , 0) (см. Алгоритм 12).
Шаг 8. 1
ˆ
+NY ←Распаковка-Упаковка
( NŶ , NC , NB , N , 0) (см. Алгоритм 12).
Шаг 9. 1
ˆ
+NZ ←Умножение( 1
ˆ
+NX ,
1
ˆ
+NY , N ) (см. Алгоритм 8).
Шаг 10. NẐ ←Комплексное сопря-
жение( NẐ , N ) (см. Алгоритм 10).
Шаг 11. NẐ ←Распаковка-Упаков-
ка ( )1
ˆ , , , , 1N N NZ C B N+ (см. Алгоритм 12).
Видим, что в оптимизированном ал-
горитме комплексное сопряжение выпол-
няется сразу после поразрядного умноже-
ния сигналов.
Далее приведены реализации Алго-
ритма 2 и его оптимизация (язык програм-
мирования APL).
Прикладні засоби програмування та програмне забезпечення
128
Прикладні засоби програмування та програмне забезпечення
129
Прикладні засоби програмування та програмне забезпечення
130
Выполнение программ FFTMainF2
и FFTMainF2Opt дают одинаковый ре-
зультат:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 02
Младший разряд слева.
Вывод
Предложена оптимизация алгорит-
ма умножения больших N -разрядных чи-
сел на основе N -разрядных БПФ с ис-
пользованием формул распаковки-упако-
вки [6]. Оптимизация позволяет умень-
шить число модулей (подпрограмм), что
уменьшает общую сложность алгоритма
умножения. Показан метод замены формул
упаковки формулами распаковки. Приве-
дено детальное описание алгоритма реали-
зации операции умножения.
1. Задірака В., Олексюк О. Комп’ютерна
арифметика багаторозрядних чисел. – К.:
Наук. думка, 2003. – 263 с.
2. Schonhage A., Strassen V. Schnelle Mul-
tiplikation grossen Zahnel // Computing. –
1971. – 7, N 3–4. – P. 281–292.
3. Шенхаге А., Шрассен В. Быстрое умноже-
ние больших чисел // Кибернетика. – 1972.
– Вып. 2. – С. 87–98.
4. Cooley J.W., Tukey J.W. An algorithm for the
machine calculation of complex Fourier Se-
ries // Math Compt. – 1965. Apr. –
P. 257–301.
5. Березовский А.И., Задирака В.К., Шевчук
Л.Б. О тестировании быстродействия ал-
горитмов и программ выполнения основ-
ных операций для асимметричной крипто-
графии // Кибернетика и системный ана-
лиз. – 1999. – № 5. – С. 61–68.
6. Терещенко А.Н. Умножение больших N-
разрядных чисел с вычислением только N-
разрядных ДПФ // Компьютерная матема-
тика. – 2008. – № 1. – С. 122–130.
Получено 13.08.2012
2 Каждый разряд – 1 байт
Об авторах:
Терещенко Андрей Николаевич,
кандидат физико-математических наук,
начальник отдела по поддержке
информационных систем,
Задирака Валерий Константинович,
доктор физико-математических наук,
профессор, член-корреспондент
НАН Украины,
заведующий отделом.
Место работы авторов:
ООО «Симкорп Украина»,
Киев, ул. В. Стусса 35-37,
teramidi@ukr.net
Институт кибернетики
имени В.М. Глушкова НАН Украины,
03680, Київ-187,
проспект Академика Глушкова, 40,
(044) 526 4568,
zvk140@ukr.net
|