是否有一些数学“最佳”基础可以加快阶乘计算?
背景:只是为了好玩,我正在实现我自己的 bignum 库。(-:这是我的第一个错误吗?:-)。我正在试验内部表示和回归测试中使用的各种基础,方法是打印出 n 阶乘(n!)的精确值(十进制)。
我的 bignum 库表示整数并进行乘法的方式,时间与内部表示 n! 中“1”位的总数成正比。在我的内部表示中使用基数 2、4、8、16、2^8、2^30 等,对于任何特定数字,我都会给出完全相同的“1”位总数。
除非我犯了一些错误,否则以 18 为基数表示的任何给定阶乘(n!)的“1”位少于以 10 为基数或以 16 为基数或以 19 为基数表示的相同值。因此(原则上)使用基数18 将使我的 bignum 库比使用基数 10 或一些二进制 2^w 基数或基数 19 运行得更快。我认为这与 n! 以 18 为基数打印时比以 10 为基数或以 16 为基数或以 19 为基数打印时,要么更短,要么有更多的“尾随零”或两者兼有。还有其他一些比以 18 为基数更好的基础吗?换句话说,是否有一个表示 n 的基数!“1”位比基数 18 还要少?
这不是“什么是 bignum 库和素数测试算法的方便基础?”的重复。因为我怀疑“处理已知为大因子的整数的最佳基数,有很多 2 和 3 的因子”不同于“处理没有任何小因子且可能的整数的最佳基数”主要”。(-:加速阶乘计算——也许以牺牲其他类型的计算为代价——我的第二个错误?:-)
编辑:例如:
(decimal) 16! ==
(decimal ) == 20,922,789,888,000 // uses decimal 14 "1" bits
(dozenal ) == 2,41A,B88,000,000 // uses decimal 10 "1" bits
(hexadecimal) == 130,777,758,000 // uses decimal 18 "1" bits
(octadecimal) == 5F,8B5,024,000 // uses decimal 14 "1" bits
(我或多或少地将数字存储在右侧,没有逗号,加上一些元数据开销)。(虽然有人可能会认为“随着基数的增加,您将使用更少的“1”位来表示给定的数字”,或者“随着基数的增加,您将使用更少的非零数字来表示给定的数字”,以上示例表明这并不总是正确的。)
我将每个数字存储为一个小整数(“int”或“long int”或“byte”)。有没有其他合理的方式来存储数字?我很确定我的计算机以二进制形式存储这些整数——每个“1”、“2”、“4”、“8”和“G”数字使用一个“1”位;每个“3”、“5”、“6”、“9”和“A”数字使用两个“1”位;每个“7”和“B”位使用三个“1”位;每个“F”位使用四个“1”位,依此类推。
该值的十进制和十八进制表示(16!)都需要 14 个“1”位。所以我在之前的计算中犯了一个错误:对于每一个n,代表n!以八进制表示的“1”位并不总是比以十进制表示相同的值少。但是问题仍然存在:是否还有其他一些“最佳”基数需要最少的 1 位来存储大阶乘?
有人问:“你如何存储这些数字?” 好吧,这正是我的问题——存储 n 形式的数字的最佳方式是什么!? 我可以在内部使用以 10 为基数的数字,或以 2 的幂为基数,或以 18 为基数,或以其他一些为基数。哪个最好?我可以在内部将这些整数存储为一维数字数组,但长度需要很长才能存储所有数字。有什么合理的方法可以打印出100!十进制没有这样的数组?