Is there is some mathematical "optimum" base that would speed up factorial calculation?
Background: Just for fun, I'm implementing my own bignum library. (-: Is this my first mistake? :-). I'm experimenting with various bases used in the internal representation and regression testing by printing out exact values (in decimal) for n factorial (n!).
The way my bignum library represents integers and does multiplication, the time is proportional to the total number of "1" bits in the internal representation n!. Using a base 2, 4, 8, 16, 2^8, 2^30, or etc. in my internal representation all give me exactly the same total number of "1" bits for any particular number.
Unless I've made some mistake, any given factorial (n!) represented in base 18 has fewer "1" bits than the same value represented in base 10 or or base 16 or base 19. And so (in principle), using base 18 would make my bignum library run faster than using base 10 or some binary 2^w base or base 19. I think this has something to do with the fact that n! is either shorter or has more "trailing zeros" or both when printed out in base 18 than in base 10 or or base 16 or base 19. Is there some other base that would work even better than base 18? In other words, Is there a base that represents n! with even fewer "1" bits than base 18?
This is not a dup of "What is a convenient base for a bignum library & primality testing algorithm?" because I suspect "the optimum base for working with integers that are known to be large factorials, with lots of factors of 2 and 3" is different than "the optimum base for working with integers that don't have any small factors and are possibly prime". (-: Is speeding up factorial calculations -- perhaps at the expense of other kinds of calculations -- my second mistake? :-)
edit: For example:
(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
(I'm more-or-less storing the digits on the right, without the commas, plus some metadata overhead). (While one might think that "As you increase the base you will use fewer "1" bits to represent a given number", or ""As you increase the base you will use fewer nonzero digits to represent a given number", the above example shows that is not always true.)
I'm storing each digit as a small integer ("int" or "long int" or "byte"). Is there any other reasonable way to store digits? I'm pretty sure my computer stores those integers in binary -- each "1", "2", "4", "8", and "G" digit use one "1" bit; each "3", "5", "6", "9", and "A" digit use two "1" bits; each "7" and "B" digit use three "1" bits; each "F" digit uses four "1" bits, etc.
Both the decimal and the octadecimal representation of this value (16!) require 14 "1" bits. So I made a mistake in my earlier calculation: For every n, representing n! in octadecimal doesn't always have fewer "1" bits than representing the same value in decimal. But the question still stands: is there some other "optimum" base that requires the fewest number of 1 bits for storing large factorials?
Someone asks: "How do you store those numbers?" Well, that's exactly my question -- what is the best way of storing numbers of the form n! ? I could internally use digits in base 10, or some power-of-two base, or base 18, or some other base. Which one is best? I could store these integers internally as a 1D array of digits, with a length however long is needed to store all the digits. Is there any reasonable way of printing out 100! in decimal without such an array?