Binary Signed-Digit Integers and the Stern Polynomial
| Autor: | Monroe, Laura |
|---|---|
| Rok vydání: | 2021 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | The binary signed-digit representation of integers is used for efficient computation in various settings. The Stern polynomial is a polynomial extension of the well-studied Stern diatomic sequence, and has itself has been investigated in some depth. In this paper, we show previously unknown connections between BSD representations and the Stern polynomial. We derive a weight-distribution theorem for $i$-bit BSD representations of an integer $n$ in terms of the coefficients and degrees of the terms of the Stern polynomial of $2^i-n$. We then show new recursions on Stern polynomials, and from these and the weight-distribution theorem obtain similar BSD recursions and a fast $\mathcal{O}(n)$ algorithm that calculates the number and number of $0$s of the optimal BSD representations of all of the integers of NAF-bitlength $\log(n)$ at once, which then may be compared. Comment: 21 pages, 3 figures. Portions of this previously appeared as arXiv:2103.05810 which was split for publication |
| Databáze: | arXiv |
| Externí odkaz: |
|