Atena Editora

Este artigo propõe algoritmos

rápidos para computar a Transformada

Numérica de Pascal (TNP) de comprimentos

e . As simetrias da matriz da TNP, bem como

sua fatoração como um produto de Kronecker,

foram usadas para se obter uma redução da

complexidade multiplicativa para se implementar

a transformada. Os algoritmos propostos

resultaram em uma redução da complexidade

entre 84% e 99,9%. Considerando o critério

de complexidade multiplicativa, os melhores

resultados são obtidos quando o comprimento

da TNP é uma potência de um primo.

Ler mais

DOI: 10.22533/at.ed.4841924053
Palavras-chave: Transformada Numérica de Pascal, Triângulo de Pascal Modular, Algoritmos Rápidos, Produto de Kronecker
Keywords: Pascal Number-Theoretic Transform, Modular Pascal Triangle, Fast Algorithms, Kronecker Product.
Abstract:
This paper proposes fast

algorithms for computing the Pascal Number

Theoretic Transform (PNTT) of blocklengths

and . The symmetries of the PNTT as well as

its factorization as a Kronecker product were

explored to reduce the multiplicative complexity

for implementing the transform. The proposed

algorithms resulted in a complexity reduction

from 84% to 99.9%. Taking into account the

multiplicative complexity criterion, the best

results are obtained when the blocklength of the

PNTT is a prime power.
Número de páginas: 15

Download

Artigo