Factoradic Operations

Question

Recently I have been creating a program that uses Wilson's theorem to solve for prime numbers, but the main disadvantage of that system is that most computers have the 64 long limit, which comes out to be about 2^63 at max (I think). I then decided to try to make this a number type for my programs, since it could serve useful in the future as well.

I have been using a factoradic system in the following format (since the typical format includes a redundant.

$6!$ $5!$ $4!$ $3!$ $2!$ $1!$ etc... (no decimals, fractions, nor negatives) And each place has a maximum value equal to its place (ie 1 - 1, 2 - 2, 3 - 3 etc...)

What I want to know is what are the most efficient methods for adding, subtracting, multiplying, performing modulo and dividing factoradices(I have figures out the first 3, but not the 2 latter, still, I want to know if there are more efficient methods to do so)

I already know that this is not the most efficient method to do this, but I want to pursue this concept out of curiosity

An answer to any of the operations would be appreciated since it would help my program a lot, thank you!

Answer 1

I don't think this is going to be cured by number representation. Any way you slice it, numbers on the order of $n!$ are really really big and will require huge amounts of memory to store and huge amounts of time to process. It would make more sense to try to compute $(n-1)! \bmod n$ without first constructing $(n-1)!$, by doing all your multiplications mod $n$. But this will still require $n-2$ multiplications mod $n$, which is way too much to be useful.

Answer 2

Consider 4:3:2:1 being the same as 5! -1 = 119 = 4*4! +3*3!+2*2!+1*1! 
so 
4:3:2:1
+     1
_______
1:0:0:0:0

To do the addition is 
1+1 = 0 with carry 1 because 1 is the max coefficient for 1! in factoradic
2+1 = 0 with carry 1 because 2 is the max coefficient for 2! in factoradic
3+1 = 0 with carry 1 because 3 is the max coefficient for 3! in factoradic
4+1 = 0 with carry 1 because 4 is the max coefficient for 4! in factoradic
0+1 = 1 for the 5! place.


   a:b:c:d
 + e:f:g:h
__________

d+h = any value from 0 to 1 with carry 1 when d=h=1
c+g = any value from 0 to 2 with carry 1 when d=h=1 and c=g=2
b+f = any value from 0 to 3 with carry 1 when d=h=1 and c=g=2 b=f=3
a+ e = any value from 0 to 4 with carry 1 when d=h=1 and c=g=2 b=f=3 a=e=4
You would have to program this to work the same way you do it by hand.
Multiplication could be done as
a:b:c * d:e:f = (a*3! + b*2!+ c*1!)*(d*3! + e*2!+ f*1!)=
d*3!*(a*3! + b*2!+ c*1!) + e*2!*(a*3! + b*2!+ c*1!)+ f*1!*(a*3! + b*2!+ c*1!) = 
d*3!*a*3! + d*3!*b*2! +d*3!*c*1! +e*2!*a*3!+e*2!*b*2!+e*2!*c*1!+f*1!*a*3!+f*1!*b*2!+f*1!*c*1!=

d*3!*a*3! 
+ d*3!*b*2! + e*2!*a*3! 
+ d*3!*c*1! + f*1!*a*3!
+ e*2!*b*2!
+ e*2!*c*1! + f*1!*b*2!
+ f*1!*c*1!
=

(d*a)*3!*3!     + (d*b + e*a)*3!*2!   + (e*b)*2!*2! + (e*c+f*b)*2!*1! + (f*c)*1!*1! = 
(d*a)*(1:2:0:0) + (d*b + e*a)*(2:0:0) + (e*b)*(2:0) + (e*c+f*b)*(1:0) + (f*c)


given the maximum for a and d is 3
the maximum for b and e is 2 and
the maximum for c and f is 1

There are no multiplication tables for factoradic number. Place shifting in order to multiply by the base does not work for factoradic.
Multiplication must be done by repeated addition in factoradic , but the algebraic expansion should help cut down the number of operations