Краткие сообщения

О времени параллельного сложения нескольких чисел

Д. А. Жуков


Аннотация: Пусть $(n,m)$-преобразование – это процедура, получающая из $n$ слагаемых $m$ чисел с той же суммой. Показано, что $(n,2)$-преобразование можно реализовать схемой глубины, асимптотически не превышающей $(1+O(\log\log k/\log k))\cdot\log_2n$, в базисе из двуместных функций $k$-значной логики (при растущем $n$).
Библиогр. 3.

УДК: 519.7

Поступила в редакцию: 20.04.2001

Реферативные базы данных:

• 
•