Fractran: Difference between revisions

Line 1,019:

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 the primes listed by Q have powers no greater than those of the corresponding primes for N.

To facilitate access without searching the 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, and for N = 2, NPPOW(1) = 1 with all other elements zero. But for FP (the factorisation of P) and FQ (for Q) there is a proper list provided via 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. Thus, FP.PLIST(2) has the index of the second prime factor of P (should it have so many), which is PRIME(FP.PLIST(2)), and its power is FP.PPOW(2). Accordingly, to determine if N (as NPPOW) is divisible by one of the fractions FQ, the appropriate elements of NPPOW (that give its powers) 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.

To facilitate access without searching the 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, and for N = 2, NPPOW(1) = 1 with all other elements zero. But for FP (the factorisation of P) and FQ (for Q) there is a proper list provided via 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. Thus, FP.PLIST(2) has the index of the second prime factor of P (should it have so many), which is PRIME(FP.PLIST(2)), and its power is FP.PPOW(2). Accordingly, to determine if N (as NPPOW) is divisible by one of the fractions FQ, the appropriate elements of NPPOW (that give its powers) must be compared to the corresponding powers in FQ.PPOW, and if ALL of the powers in NPPOW fingered by FQ.PLIST 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.

As a part of the preparation, for each fraction the greatest common divisor is divided out to remove the possibility that converting the test ''N times fraction'' being integral via ''fraction = P/Q'' to ''Q divides N'' will behave differently. For example, N*6/3 will always be integral, but N may not be divisible by three. Reducing 6/3 to 2/1 however will work as will reducing 55/25 to 11/5. The example contains no such occasions, but the possibility nags.