Top

Designs, Codes and Cryptography

Published in:

05-10-2021

Binary signed-digit integers and the Stern diatomic sequence

Author: Laura Monroe

Published in: Designs, Codes and Cryptography | Issue 12/2021

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Stern’s diatomic sequence is a well-studied and simply defined sequence with many fascinating characteristics. The binary signed-digit representation of integers is an alternative representation of integers with much use in efficient computation, coding theory and cryptography. We link these two ideas here, showing that the number of i-bit binary signed-digit representations of an integer n with \(n<2^i\) is the \((2^i-n)^{\text {th}}\) element in Stern’s diatomic sequence. This correspondence makes the vast range of results known for Stern’s diatomic sequence available for consideration in the study of binary signed-digit integers.

next article Walsh spectrum and nega spectrum of complementary arrays

Avizienis, A.: Signed-digit number representations for fast parallel arithmetic. IRE Trans. Comput. EC-10(3), 389–400 (1961)

Bates B., Mansour T.: The q-Calkin-Wilf tree. J. Combin. Theory Ser. A 118, 1143–1151 (2011).MathSciNetCrossRef

Booth A.D.: A signed binary multiplication technique. Quart. J. Mech. Appl. Math. 4(2), 236–240 (1951). https://doi.org/10.1093/qjmam/4.2.236.MathSciNetCrossRefMATH

Calkin N., Wilf H.S.: Recounting the rationals. Amer. Math. Monthly 107, 360–363 (2000).MathSciNetCrossRef

Carlitz, L.: A problem in partitions related to the Stirling numbers. Bull. Amer. Math. Soc. 70(2), 275–278 (1964). http://projecteuclid.org/euclid.bams/1183525946

Cauchy, A.L.: Sur les moyens d’eviter les erreurs dans les calculs numerique (1840). In: Œuvres complétes: Series 1, Cambridge Library Collection - Mathematics, vol. 5, pp. 431–442. Cambridge University Press (2009). https://doi.org/10.1017/CBO9780511702518

Colson, J.: A short account of negativo-affirmative arithmetick. Philos. Trans. Roy. Soc. (1683-1775) 34, 161–173 (1726). http://www.jstor.org/stable/103469

Dijkstra, E.W.: Selected Writings on Computing: A Personal Perspective, pp. 215–232. Springer-Verlag New York, Inc., New York, NY, USA (1982)

Ebeid N., Hasan M.: On binary signed digit representations of integers. Des. Codes Cryptogr. 42, 43–65 (2007). https://doi.org/10.1007/s10623-006-9014-9.MathSciNetCrossRefMATH

10.

Eğecioğlu, Ö., Koç, Ç.K.: Fast modular exponentiation. Proceedings of 1990 Bilkent International Conference on New Trends in Communication, Control, and Signal Processing 1, 188–194 (1990)

11.

Finch, S.: Mathematical Constants, pp. 148–149. Encyclopedia of Mathematics and its Applications. Cambridge University Press (2003). http://books.google.com/books?id=DL5iVYNoEa0C

12.

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.MathSciNetCrossRefMATH

13.

Koblitz, N.: CM-curves with good cryptographic properties. In: Advances in cryptology—CRYPTO ’91 (Santa Barbara, CA, 1991), Lecture Notes in Comput. Sci., vol. 576, pp. 279–287. Springer, Berlin (1992). https://doi.org/10.1007/3-540-46766-1_22. https://doi.org/10.1007/3-540-46766-1_22

14.

Lehmer, D.H.: On Stern’s diatomic series. Amer. Math. Monthly 36(2), 59–67 (1929). http://www.jstor.org/stable/2299356

15.

Lind D.A.: An extension of Stern’s diatomic series. Duke Math. J. 36(1), 55–60 (1969).https://doi.org/10.1215/S0012-7094-69-03608-4

16.

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.MathSciNetCrossRefMATH

17.

Northshield, S.: Stern’s diatomic sequence 0, 1, 1, 2, 1, 3, 2, 3, 1, 4,.... Amer. Math. Monthly 117(7), 581–598 (2010)

18.

OEIS Foundation Inc.: The On-Line Encyclopedia of Integer Sequences: Sequence A002487. http://oeis.org/A002487 (2020). Accessed 2020-04-15

19.

Reznick, B.: Some binary partition functions. In: Analytic Number Theory, Progress in Mathematics, vol. 85, pp. 451–477. Birkhauser Boston (1990). https://doi.org/10.1007/978-1-4612-3464-7_29.

20.

Shallit, J.: A primer on balanced binary representations. http://cs.uwaterloo.ca/~shallit/Papers/bbr.pdf (1992)

21.

Shannon, C.E.: A symmetrical notation for numbers. Amer. Math. Monthly 57(2), 90–93 (1950). http://www.jstor.org/stable/2304993

22.

Stanley, R.P., Wilf, H.S.: Refining the Stern diatomic sequence. http://www-math.mit.edu/~rstan/papers/stern.pdf (2010)

23.

Stern, M.: Ueber eine zahlentheoretische Funktion. J. Reine Angew. Math. 55, 193–220 (1858). http://eudml.org/doc/147729

24.

Tůma, J., Vábek, J.: On the number of binary signed digit representations of a given weight. Commentationes Mathematicae Universitatis Carolinae 56(3), 287–306 (2015). https://doi.org/10.14712/1213-7243.2015.129

Title: Binary signed-digit integers and the Stern diatomic sequence
Author: Laura Monroe
Publication date: 05-10-2021
Publisher: Springer US
Published in: Designs, Codes and Cryptography / Issue 12/2021
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-021-00903-6

Springer Professional

Binary signed-digit integers and the Stern diatomic sequence

Abstract

Premium Partner

Springer Professional

Abstract

Please log in to get access to your license.

Other articles of this Issue 12/2021

Existence of primitive normal pairs with one prescribed trace over finite fields

An improved degree evaluation method of NFSR-based cryptosystems

Five families of the narrow-sense primitive BCH codes over finite fields

Three classes of balanced vectorial semi-bent functions

Binomial permutations over finite fields with even characteristic

On security properties of all-or-nothing transforms

Premium Partner