Abstract
The binary signed-digit (BSD) representation of integers is used for efficient integer computation in various settings. The Stern polynomial is a polynomial extension of the well-studied Stern diatomic sequence. In this paper, we show previously unknown connections between BSD integer representations and the Stern polynomial. We then exploit these connections to devise a fast algorithm to count optimal BSD representations on a range of integers and calculate their weights.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Data availability
Not applicable.
Code availability
Not applicable.
References
Avizienis A.: Signed-digit number representations for fast parallel arithmetic. IRE Trans. Comput. 10(3), 389–400 (1961).
Booth A.D.: A signed binary multiplication technique. Q. J. Mech. Appl. Math. 4(2), 236–240 (1951). https://doi.org/10.1093/qjmam/4.2.236.
Dilcher K., Tomkins H.: Square classes and divisibility properties of Stern polynomials. Integers 18, A29 (2018).
Eğecioğlu Ö., Koç Ç.K.: Fast modular exponentiation. In: Proceedings of 1990 Bilkent International Conference on New Trends in Communication, Control, and Signal Processing, vol. 1, pp. 188–194 (1990).
Ganesan P., Manku G.S.: Optimal routing in Chord. In: ACM SIAM Symposium on Discrete Algorithms (SODA 2004) (2004). http://ilpubs.stanford.edu:8090/640/.
Grabner P., Heuberger C.: On the number of optimal base 2 representations of integers. Des. Codes Cryptogr. 40, 25–39 (2006). https://doi.org/10.1007/s10623-005-6158-y.
Klavžar S., Milutinović U., Petr C.: Stern polynomials. Adv. Appl. Math. 39(1), 86–95 (2007). https://doi.org/10.1016/j.aam.2006.01.003.
Koblitz N.: CM-curves with good cryptographic properties. In: Feigenbaum, J. (ed.) Advances in Cryptology — CRYPTO ’91, pp. 279–287. Springer, Berlin, Heidelberg (1992). https://doi.org/10.1007/3-540-46766-1_22.
Monroe L.: Binary signed-digit integers and the Stern diatomic sequence. Des. Codes Cryptogr. 89(12), 2653–2662 (2021). https://doi.org/10.1007/s10623-021-00903-6.
Morain F., Olivos J.: Speeding up the computations on an elliptic curve using addition-subtraction chains. RAIRO Theor. Inform. Appl. 24, 531–544 (1990). https://doi.org/10.1051/ita/1990240605311.
Reitwiesner G.W.: Binary arithmetic. In: Advances in Computers, vol. 1, pp. 231–308. Elsevier (1960). https://doi.org/10.1016/S0065-2458(08)60610-5.
Reznick B.: Some binary partition functions. In: Berndt B.C., Diamond H.G., Halberstam H., Hildebrand A. (eds.) Analytic Number Theory: Proceedings of a Conference in Honor of Paul T. Bateman, pp. 451–477. Birkhäuser Boston, Boston (1990). https://doi.org/10.1007/978-1-4612-3464-7_29.
Sawada J.: A simple Gray code to list all minimal signed binary representations. SIAM J. Discret. Math. 21(1), 16–25 (2007). https://doi.org/10.1137/050641405.
Schinzel A.: The leading coefficients of Stern polynomials. In: Sander J., Steuding J., Steuding R. (eds.) From Arithmetic to Zeta-Functions: Number Theory in Memory of Wolfgang Schwarz, pp. 427–434. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-28203-9_25.
Schinzel A.: On the factors of Stern polynomials: remarks on the preceding paper of M. Ulas. Publ. Math. Debrecen 79, 83–88 (2011). https://doi.org/10.5486/PMD.2011.5110.
Shallit J.: A primer on balanced binary representations. http://cs.uwaterloo.ca/~shallit/Papers/bbr.pdf (1992).
Shannon C.E.: A symmetrical notation for numbers. Am. Math. Mon. 57(2), 90–93 (1950).
Tůma J., Vábek J.: On the number of binary signed digit representations of a given weight. Comment. Math. Univ. Carolin. 56(3), 287–306 (2015). https://doi.org/10.14712/1213-7243.2015.129.
Ulas M.: On certain arithmetic properties of Stern polynomials. Publ. Math. Debrecen 79(1–2), 55–81 (2011).
Ulas M.: Arithmetic properties of the sequence of degrees of Stern polynomials and related results. Int. J. Number Theory 8, 669–687 (2012). https://doi.org/10.1142/S1793042112500388.
Acknowledgements
The author wishes to thank the anonymous reviewers of [9] for helpful suggestions relating to the extension of that work.
Funding
This work has been authored by an employee of Triad National Security, LLC, operator of the Los Alamos National Laboratory under Contract No.89233218CNA000001 with the U.S. Department of Energy. This work was also supported by LANL’s Ultrascale Systems Research Center at the New Mexico Consortium (Contract No. DE-FC02-06ER25750).). The United States Government retains and the publisher, by accepting this work for publication, acknowledges that the United States Government retains a nonexclusive, paid-up, irrevocable, world-wide license to publish or reproduce this work, or allow others to do so for United States Government purposes.
Author information
Authors and Affiliations
Contributions
Not applicable; only one author. This publication has been assigned the LANL identifier LA-UR-23-27982.
Corresponding author
Ethics declarations
Conflict of interest
The author declares no conflict of interest.
Ethical approval
Not applicable.
Consent to participate
Not applicable.
Consent for publication
Not applicable.
Additional information
Communicated by J. Jedwab.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Monroe, L. Optimal binary signed-digit representations of integers and the Stern polynomial. Des. Codes Cryptogr. 92, 1501–1516 (2024). https://doi.org/10.1007/s10623-023-01355-w
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10623-023-01355-w