Published in Volume XXIV, Issue 2, 2014, pages 287-323, doi: 10.7561/SACS.2014.2.287

Authors: P. Tarau

Abstract

We study arithmetic properties of a new tree-based canonical num- ber representation, recursively run-length compressed natural numbers, defined by applying recursively a run-length encoding of their binary digits.

We design arithmetic and boolean operations with recursively run- length compressed natural numbers that work a block of digits at a time and are limited only by the representation complexity of their operands, rather than their bitsizes.

As a result, operations on very large numbers exhibiting a regular structure become tractable.

In addition, we ensure that the average complexity of our operations is still within constant factors of the usual arithmetic operations on binary numbers.

Arithmetic operations on our recursively run-length compressed are specified as pattern-directed recursive equations made executable by using a purely declarative subset of the functional language Haskell.

Full Text (PDF)

References

[1] J. W. Bruce. A Really Trivial Proof of the Lucas-Lehmer Test. The American Mathematical Monthly, 100(4):370–371, 1993. http://dx.doi.org/10.2307/2324959.

[2] John H. Conway. On Numbers and Games. AK Peters, Ltd., 2nd edition, 2000.

[3] R. Goodstein. On the restricted ordinal theorem. Journal of Symbolic Logic, 9(02):33–41, 1944. http://dx.doi.org/10.2307/2268019 .

[4] Norbert Hungerbühler. The Isomorphism Problem for Catalan Families. J. Combin. Inform. System Sci, 20:129–139, 1995.

[5] Oleg Kiselyov, William E. Byrd, Daniel P. Friedman, and Chung- chieh Shan. Pure, Declarative, and Constructive Arithmetic Relations (Declarative Pearl). In Jacques Garrigue and Manuel V. Hermenegildo, editors, Proceedings of the 9th International Symposium on Functional and Logic Programming (FLOPS 2008), volume 4989 of Lecture Notes in Computer Science, pages 64–80. Springer, 2008. http://dx.doi.org/10.1007/978-3-540-78969-7_7 .

[6] Donald E. Knuth. Mathematics and Computer Science: Coping with Finiteness. Science, 194c;4271):1235 –1242, 1976. http://dx.doi.org/10.1126/science.194.4271.1235 .

[7] Donald E. Knuth. TCALC program, December 1994. http://www-cs-faculty.stanford.edu/~uno/programs/tcalc.w.gz .

[8] Donald E. Knuth. The Art of Computer Programming, Volume 4, Fascicle 4: Generating All Trees–History of Combinatorial Generation (Art of Computer Programming). Addison-Wesley Professional, 2006.

[9] Donald E. Knuth. The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise Tricks & Techniques; Binary Decision Diagrams. Addison-Wesley Professional, 2009.

[10] Donald L. Kreher and D.R. Stinson. Combinatorial Algorithms: Generation, Enumeration, and Search. The CRC Press Series on Discrete Mathematics and its Applications. CRC Press, 1999.

[11] Ming Li and Paul Vit´anyi. An introduction to Kolmogorov complexity and its applications. Springer-Verlag New York, Inc., New York, NY, USA, 1993.

[12] J. Liebehenschel. Ranking and unranking of a generalized Dyck language and the application to the generation of random trees. Séminaire Lotharingien de Combinatoire, 43:B43d, 19 p.–B43d, 19 p., 1999. Available from: http://eudml.org/doc/120437 .

[13] Conrado Martìnez and Xavier Molinero. Generic algorithms for the generation of combinatorial objects. In Branislav Rovan and Peter Vojtás, editors, Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science (MFCS 2003), volume 2747 of Lecture Notes in Computer Science, pages 572–581. Springer, 2003. http://dx.doi.org/10.1007/978-3-540-45138-9_51.

[14] Arto Salomaa. Formal Languages. Academic Press, New York, 1973.

[15] R P Stanley. Enumerative Combinatorics. Wadsworth Publ. Co., Belmont, CA, USA, 1986.

[16] Paul Tarau. Declarative modeling of finite mathematics. In Temur Kutsia, Wolfgang Schreiner, and Maribel Fernández, editors, Proceedings of the 12th International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP 2010), pages 131–142. ACM, 2010. http://dx.doi.org/10.1145/1836089.1836107.

[17] Paul Tarau. Computing with Catalan Families. In Adrian Horia Dediu, Carlos Martìn-Vide, José Luis Sierra-Rodríguez, and Bianca Truthe, editors, Proceedings of the 8th International Conference on Language and Automata Theory and Applications (LATA 2014), volume 8370 of Lecture Notes in Computer Science, pages 565–575. Springer, 2014. http://dx.doi.org/10.1007/978-3-319-04921-2_46 .

[18] Paul Tarau. The Arithmetic of Recursively Run-Length Compressed Natural Numbers. In Gabriel Ciobanu and Dominique Méry, editors, Proceedings of the 11th International Colloquium on Theoretical Aspects of Computing (ICTAC 2014), volume 8687 of Lecture Notes in Computer Science, pages 406–423. Springer, 2014. http://dx.doi.org/10.1007/978-3-319-10882-7_24 .

[19] Paul Tarau and Bill P. Buckles. Arithmetic algorithms for hereditarily binary natural numbers. In Yookun Cho, Sung Y. Shin, Sang-Wook Kim, Chih-Cheng Hung, and Jiman Hong, editors, Proceedings of the Symposium on Applied Computing (SAC 2014), pages 1593–1600. ACM, 2014. http://dx.doi.org/10.1145/2554850.2555040 .

[20] Paul Tarau and David Haraburda. On computing with types. In Sascha Ossowski and Paola Lecca, editors, Proceedings of the ACM Symposium on Applied Computing (SAC 2012), pages 1889–1896. ACM, 2012. http://dx.doi.org/10.1145/2245276.2232087 .

[21] Paul Tarau and Brenda Luderman. Boolean evaluation with a pairing and unpairing function. In Andrei Voronkov, Viorel Negru, Tetsuo Ida, Tudor Jebelean, Dana Petcu, Stephen Watt, and Daniela Zaharie, editors, Proceedings of the 14th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC 2012), pages 384–390. IEEE Computer Society. http://dx.doi.org/10.1109/SYNASC.2012.20 .

[22] Jean Vuillemin. Efficient data structure and algorithms for sparse integers, sets and predicates. In Javier D. Bruguera, Marius Cornea, Debjit Das Sarma, and John Harrison, editors, Proceedings of the 19th IEEE Symposium on Computer Arithmetic (ARITH 2009), pages 7–14. IEEE Computer Society, 2009. http://dx.doi.org/10.1109/ARITH.2009.25 .

Bibtex

@article{sacscuza:tarau2014aaboorrcnn,
  title={Arithmetic and Boolean Operations on Recursively Run-Length Compressed Natural Numbers},
  author={P. Tarau},
  journal={Scientific Annals of Computer Science},
  volume={24},
  number={2},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  year={2014},
  pages={287--323},
  doi={10.7561/SACS.2014.2.287},
  publisher={``A.I. Cuza'' University Press}
}