Binary Signed-Digit Integers and the Stern Polynomial

Abstract

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.

21 pages, 3 figures. Portions of this previously appeared as arXiv:2103.05810 which was split for publication