6

是否有一些数学“最佳”基础可以加快阶乘计算?

背景:只是为了好玩,我正在实现我自己的 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!十进制没有这样的数组?

4

4 回答 4

5

如果您只是想优化计算阶乘的运行时间,而更改基数是您要更改的唯一参数,那么最佳基数可能包含小因素。60可能是一个合理的选择。如果你想尝试,我会尝试各种形式的基础 (2^a)(3^b)(5^c)

提高乘法的速度可能是最好的表现方式。你用什么算法做乘法?(教科书,Karatsuba,Toom-Cook,FFT,...)

还有其他因素需要考虑。如果您经常将数字转换为十进制,那么以 10 为底的基数将使转换尽可能快。

许多(*)年前,我专门写了一个base-6浮点库来解决重复乘法/除以2和/或3的问题。但是除非你试图解决一个特定的问题,否则我认为你会更好通常通过优化算法来提供服务,而不是仅仅尝试优化阶乘。

案例

(*) 我最初说的是“几年前”,直到我记得程序在 12Mhz 80286 上运行了很多天。

于 2010-06-20T22:09:39.163 回答
2

虽然从纯数学的角度来看,最佳基数是e(并且在四舍五入到最接近的整数 - 3 之后),但从计算机上的 bignum 库的实际角度来看,选择一个机器字长作为数字系统的基数( 2^32 或2^64)。是的,它很大,但是你的 bignum 系统的更高抽象层是阻塞点,机器字的底层计算是快速的部分,所以将尽可能多的计算委托给 CPU 低级指令,同时尽量减少你自己的工作。

不,这不是一个错误。这是一个非常好的学习练习。

于 2010-06-21T15:59:32.187 回答
1

我不会假装我知道任何数学,所以不要把我的答案当作你可能正在寻找的神圣“最佳”。如果我必须尽可能快地进行阶乘,我会尝试一些近似(类似于斯特林近似)或减少乘法的数量,因为乘法是昂贵的操作。如果您表示以 k 为底的数字,则可以在移位的帮助下模拟 k 乘法。如果您选择 2-base,所有乘法的一半将是移位。其他乘法是移位和一位切换。如果您的目标是最小化数字表示中“1”的数量,这取决于您表示的数字。随着基数的增加,您将使用更少的“1”来表示给定的数字,但每个订单都需要更多的位,这意味着更多潜在的“1”。我希望它至少有一点帮助,如果没有,请问,我会尽力回答。

于 2010-06-19T23:49:22.597 回答
1

如果“1”位是指数字,那么我建议以 256 或 65536 为基数。换句话说,出于数学的目的,将每个字节/字设为“数字”。计算机会定期处理这些数字,并为此进行了优化。您的阶乘将很快,其他操作也将如此。

更不用说计算机可以轻松地处理从类似基础到这些基础的大量转换。(无意押韵)

于 2010-06-20T22:49:25.443 回答