Dav*_*ary 6 language-agnostic integer biginteger bignum factorial
是否有一些数学"最佳"基础可以加速因子计算？
背景:为了好玩,我正在实施我自己的bignum库.( - :这是我的第一个错误吗？:-).我正在通过打印n阶乘(n!)的精确值(十进制)来试验内部表示和回归测试中使用的各种基数.
我的bignum库表示整数并进行乘法的方式,时间与内部表示n!中"1"位的总数成正比.在我的内部表示中使用基数2,4,8,16,2 ^ 8,2 ^ 30等都给出了与任何特定数字完全相同的"1"位总数.
除非我做了一些错误,任何给定的阶乘(N!)在基地18代表具有比在基地10或或基地16或19基地等等(原则)表示相同的值较少的"1"位,使用基础18会使我的bignum库比使用base 10或某些二进制2 ^ w base或base 19运行得更快.我认为这与n这个事实有关!或者是短或具有更多的"尾随零"或两者时在基部18比底座10打印出来,或或基座16或基座19有一些其他,将工作比基部18甚至更好的基础？换句话说,是否存在代表n的基数!比基数18更少的"1"位？
这不是"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中的数字,或者一些二次幂,或者基数为18,或者其他一些基数.哪一个最好？我可以在内部将这些整数存储为1D数字数组,但需要很长的长度来存储所有数字.有没有合理的方式打印100!十进制没有这样的数组？
如果您只是尝试优化计算阶乘的运行时间,并且更改基数是您正在改变的唯一参数,那么最佳基数可能包含很小的因子.60可能是一个合理的选择.如果你想试验,我会尝试形式的各种基础(2 ^ a)(3 ^ b)(5 ^ c)
提高乘法速度可能是性能的最佳方式.您使用什么算法进行乘法？(学校用书,Karatsuba,Toom-Cook,FFT,...)
还有其他因素需要考虑.如果您经常将数字转换为十进制,那么10的幂将使转换尽可能快.
很多(*)年前,我写了一个base-6浮点库专门解决了重复乘法/除法2和/或3的问题.但除非你试图解决一个特定的问题,我想你会更好通过优化您的算法来提供服务,而不仅仅是尝试优化阶乘.
casevh
(*)我最初说"几年前",直到我记得这个程序在12Mhz 80286上运行了很多天.