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

SHF：小：遗传二进制数的算术算法和应用

• 批准号: 1423324
• 负责人: Paul Tarau
• 金额: $ 25.32万
• 依托单位: University of North Texas
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-09-01 至 2019-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1423324&HistoricalAwards=false
• 关键词: SHF; Small; Arithmetic; Algorithms; Applications

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.

数字表示法已经从一元表示法发展到以n为底的数字系统，其中一个划痕在墙上代表一个单位，具有对数表示大小的显着好处。在过去的1000年里，这种表示法被证明是非常有弹性的，部分原因是所有的实际计算都可以在这种表示法中以合理的效率进行。尽管如此，人们可能会问，完全不同的编号系统是否可以提供类似的服务。更进一步，人们可能会问，是否有数字系统可以容纳更大的数字，同时仍然提供与熟悉的数字相同的高效计算。这个项目有几个实际用途，涉及非常大的数字的有效计算，这对数论和密码学等领域很重要。该项目研究与这样的编号系统：遗传二进制数工作的算法。它涉及到计算与树通过递归压缩序列的零和一发生在二进制表示的一个数字。有了它们，计算巨大的数字，包括指数塔和所有记录保持素数变得易于处理。该项目包括紧凑表示和集合和布尔逻辑计算，研究与组合对象家族的连接，高级数论算法以及实现遗传二进制数计算及其应用的开源软件库。