I'm trying to find am means of dividing two numbers in factoradic base. So far goolging seems to turn up nothing at all. Is there a better way of doing this than long-division? I'm hoping for something efficient to compute. As an example, I'm looking to calculate $(a 4! + b 3! + c 2! + d)\over(e 4! + f 3! + g 2! + h)$.
In reality, though, these numbers will likely contain components upto $500!$ so multiplying through and doing the division in a standard base would not be feasible.
The use of factoradic base here is due to a close link with permutations: the calculation is being used to show progress on an implementation of the Ullman algorithm for subgraph isomorphism. As such, I need to be able to calculate $x!$ and continually subtract $y! \over z!$ from it. Thus, Factoradic base is quite attractive however, I am open to alternatives to this if anyone believes I'm progressing down a misguided route.
Thanks in advance.
well 4*4! + a*3! + b *2! + c*1! / 2*4! is 2 with remainder a*3! + b *2! + c*1!
3*3! + 2*2! + 1*1! = 1*4! -1 ie 1*n! > any factorial number system number made using anything < n. As for denominators which are not just x*n!, I don't have a good answer. In your example a/e is bounded between 0/4 to 4/1 assuming e must be positive. You might rewrite the problem as (a+(x/4!))*4!/(e+(y/4!))*4! where x = b*3! + c*2! + d and x/4! <= (4!-1)/4! <1 and y = f*3! + g*2! + h and y/4! <= (4!-1)/4! <1. This reduces the problem to (a+(x/4!))/(e+(y/4!)). Your actual problem is probably more like cnn! + cn-1(n-1)!.../cmm! + cm-1(m-1)!... where n/m might be > or < or = 1. Try computing the denominator as a single coefficient times a single factorial and using that to compute the division for each term then sum them together. The factorial numbering system can represent fractions as well in the form of a/2! + b/3! + c/4! .. where the coefficients are always < the n in n! for each place i.e a is at most 1 b at most 2 c at most 3 I hope this helps.