SHF:Small:Arithmetic Algorithms and Applications of Hereditarily Binary Numbers

University Of North Texas, Denton TX

Investigators

Abstract

Number representations have evolved from the unary representation where one scratch on the wall represented a unit, to the base-n number system, with the remarkable benefit of a logarithmic representation size. Over the last 1000 years, this representation has proved to be unusually resilient, partly because all practical computations could be performed with reasonable efficiency within the notation. Still, one might ask if radically different numbering systems can offer similar services. And one step further one might want to ask if there are number systems that can accommodate significantly larger numbers while still providing comparably efficient computations with the familiar ones. This project has several practical uses involving efficient computations with very large numbers which is important for fields like number theory and cryptography. The project studies algorithms working with such a numbering system: hereditarily binary numbers. It involves computing with trees obtained by recursively compressing sequences of zeros and ones occurring in the binary representation of a number. With them, computations with giant numbers, including towers of exponents and all record holding prime numbers become tractable. The project includes work on compact representation and computation with sets and boolean logic, study of connections to a family of combinatorial objects, advanced number-theoretical algorithms as well as an open source software library implementing computations with hereditarily binary numbers and their applications.