Arithmetic complexity of the Stirling transformsстатья
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 19 сентября 2015 г.
Аннотация:Abstract: For the linear Stirling transforms of both kinds, which are well-known in combinatorics, we obtain
close to optimal estimates of the complexity of computation by vector addition chains and non-branching
programs composed of arithmetic operations over real numbers. A relation between these problems and the
Lagrange and Newton interpolation is discussed.
Keywords: Stirling transforms of the 1st and 2nd kinds, addition vector chains, circuits in arithmetic bases,
the Lagrange and Newton interpolation, Vandermonde matrices, the Gauss q-binomial coefficient.