Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10333914 | Theoretical Computer Science | 2011 | 13 Pages |
Abstract
Motivated by multiplication algorithms based on redundant number representations, we study representations of an integer n as a sum n=âkεkUk, where the digits εk are taken from a finite alphabet Σ and (Uk)k is a linear recurrent sequence of Pisot type with U0=1. The most prominent example of a base sequence (Uk)k is the sequence of Fibonacci numbers. We prove that the representations of minimal weight âk|εk| are recognised by a finite automaton and obtain an asymptotic formula for the average number of representations of minimal weight. Furthermore, we relate the maximal number of representations of a given integer to the joint spectral radius of a certain set of matrices.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Peter J. Grabner, Wolfgang Steiner,