Fractran: Difference between revisions
m
→Revised Plan
(→{{header|Fortran}}: Stage two.) |
m (→Revised Plan) |
||
Line 875:
===Revised Plan===
One could introduce a scheme for multi-precision (or "bignum") arithmetic, but there is no need to maintain a unified number N because there are no additions or subtractions, only multiplications and division without remainders. In other words, why not mess about with collections of prime factors? That is, represent N, P, and Q as the list of prime numbers with their powers for each case. To calculate N*P, just add the list of prime number powers for P to that for N, and similarly, for N/Q subtract. At no stage (except perhaps to decorate output or for debugging) need the list be multiplied out to give the unified number and so there is no need for multi-precision multiplies and divides. To determine if N is divisible by Q (that is, if N*fraction = N*P/Q is integral), check only that for the primes listed by Q have powers no greater than the corresponding primes for N.
To facilitate access without searching a list of primes for N, instead its list is represented by an array of powers, NPPOW, with most entries zero. Thus, NPPOW(i) has the power for PRIME(i) in the factorisation of N. But for FP (the factorisation of P) and FQ (for Q) there is a proper list provided by type FACTORED, whereby FP.PLIST(0) is the count of prime factors and <code>FP.PLIST(1:FP.PLIST(0))</code> fingers the prime numbers that are factors, with FP.PPOW(i) having their corresponding powers. Accordingly, to determine if N (as NPPOW) is divisible by one of the fractions FQ, the appropriate elements of NPPOW must be compared to the corresponding powers in FQ.PPOW, and if ALL of the fingered powers in NPPOW are greater than or equal to those in FQ.PPOW, then a hit! Note that the prime number factorisation of one has no elements in its list, and happily, the ALL operation applied for no tests yields ''true'' as desired, because one divides any number. Thus, in the FRACTRAN op-code system, a fraction P/1 is always a match, and no fractions beyond it will ever be considered.
| |||