The conventional system of number representation cannot exactly represent most numbers. Fractions that have factors in the denominator that are not in the number system's base have infinite decimal representations (e.g. other than 2 and 5 for base 10). Square roots and other irrational numbers \ have infinite, non-repeating representations.
In the late 1990s I came up with an alternative system that can exactly represent any rational or irrational number as well as most transcendental numbers using only a finite number of bits. This type of representation is based upon the idea of factored representations of integers extended in a logical way to a nearly universal system of describing number structure.
 | |
| Pretty but unrelated |
If each numerical place is assigned a value corresponding with each successively larger prime number, then any square-free integer can be represented in factored form as a binary string with 1s in the spots that are factors and zeros elsewhere. For instance 2*3*5*11 = 330 would be represented [1,1,1,0,1] (smallest factor on the left.) This is equivalent to raising each prime to the power of the corresponding binary entry in the string: [2^1, 3^1, 5^1, 7^0, 11^1]. By extending this to entries in {-1,0,1}, (ternary, “trits”) then rational fractions can be represented so long as both their numerator and denominator have no squared factors. So 2/3 would be represented [1,-1], and 6/7 = [1,1,0,-1]
To allow representation of numbers with squares or higher powers of the prime factors, the same scheme can be applied to each entry in the list of base factors. So if:
6 = 2*3 = [1,1], then
6^6 = 46656 =
[2^(2*3) * 3^(2*3)] =
[[1,1],[1,1]].
To allow representing negative numbers and zero, a leading entry is needed, a “one's place”, so that positive numbers begin with 1, negative numbers with -1, and zero with 0. Applying this leading entry to the exponents allows representing all negative exponents and rational exponents, thus all rational roots of rational numbers. The examples above would all have leading “1”s added, so that 6^6 would become: [1,[1,1,1],[1,1,1]].
-(6^6) = [-1,[1,1,1],[1,1,1]]
6^(-6) = [1,[-1,1,1],[-1,1,1]]
6^(1/6) = [1,[1,-1,-1],[1,-1,-1]]
-(6^(-1/6)) = [-1,[-1,-1,-1],[-1,-1,-1]]
The representation can be applied recursively to allow exponents that themselves have squares, etc.:
4 = [1,[1,1]] , 16= [1,[1,[1,1]]] , 65536 = [1,[1,[1,[1,1]]]] , 2^65536 = [1,[1,[1,[1,[1,1]]]]]
deeply embedded lists are powers of powers of powers .... Very large numbers can be compactly represented.
This scheme also allows representing irrational roots, e.g. 2^(2^(1/2)) = [1,[1,[1,-1]]]. More deeply embedded roots are “more transcendental”.
The representation scheme can be visualized by taking the exponent strings to be at right angles to their parent strings, so that an n-level deep embedding is seen as an n-dimensional tree structure. Square-free numbers are 1-D, numbers with square-free exponents to some factors in the base string are 2-D, numbers with some factors raised to e.g. powers of 4 are 3-D, with factors raised to powers of 16 are 4-D, and higher dimension integers are generally extremely large.
Therefore I call this type of numerical representation “ternary factor tree representation”, TFTR for short.
Addition and subtraction are not possible in this representation without converting back to a conventional representation, performing the operation and then converting back. This works for rational numbers, but for irrational numbers, not so well – for instance, 1 + sqrt(3) is not defined precisely, though of course approximations can be constructed.
Multiplication and division are somewhat easier in this scheme than in conventional representations; just add the exponents for each place in the base string together. This will seldom require a difficult conversion back and forth since exponents are generally small. Exponentiation and roots are even easier, just requiring multiplying the exponents together.
By considering patterns of trits in TFTR, many interesting types of numbers can be specified.
Primorials, (the equivalent of factorials, but multiplying together only prime numbers) are the easiest pattern to specify: [1,1,1,1,1,1, ....]. Considering infinite sequences, there is a unique largest square-free infinite number, the infinite primorial represented by an infinite string of 1s. It would have some curious properties for an infinite number: it would have a decimal representation ending in a single 0 since it is divisible by 10, and the sum of its digits would be an infinite integer divisible by 3, but not 9, since the primorial itself is divisible by 3 but not 9. Yet at the same time the digits would generally be uncomputable since they all depend on infinite factors.
Dividing the infinite primorial by successively larger prime numbers yields an infinite sequence of infinite numbers, each infinitely smaller than the last. (Note that each place value in the infinite primorial can be paired with the same place in the number to which it is identical (except for a single 0 in the spot corresponding to the prime by which it was divided), so Cantor diagonal arguments do not apply in this case.)
The power set of representations of infinite square-free integers, that is, the set of all infinite bit strings would seem to provide a transfinite number of infinite numbers. These would seem to not be totally orderable because the largest factors in each number would nearly always be of varying infinities. The subset of these that have no 0s - no missing factors – above some place-value should still be orderable, as should any that have the same knowable repeating patterns of 1s and 0s above some place-value. (Even patterns with very long cycles, such as from pseudo-random number generators.)
The category of numbers (including finite, infinite, fractions, roots, etc.) representable by computable patterns of factors is the grand arena of number theory. (Or at least as grand as I can now conceive.)
By considering exponents in the one's place, I speculate that complex roots of unity and -1 may be specified, and perhaps quaternions as well. The significance of doing this in the one's places of the prime factors and exponents' prime factors is unclear, but would seem to allow specifying “phases” for each factor at each level of exponents, perhaps analogous to having the branches of the tree at angles other than 90 degrees. There are less confusing areas to explore first.
Another peculiarity of TFTRs is that there are as many representations of zero as there are of the positive or negative numbers. (Any string starting with 0 is equal to zero.) This applies to exponents as well, so there are an infinite number of representations of each prime raised to the 0th power, and so an infinite number of representations of 1. With these exceptions, though, each different pattern of trits represents a unique number.
Compressed representations of TFTRs may be of practical interest, particularly compressing long strings of zeros. One scheme I have considered uses the integer exponent of a zero term in the exponent's parent string to specify a long string of zeros in the parent string. This may conceptually muck up the representation, though, so perhaps applying conventional compression outside the representation is a better way to handle it. Coding could certainly be more efficient using an alphabet of {-1, 0, 1, [, ]}, (requiring three bits per symbol rather than 8 for ASCII) though other options may be even better, for instance: {[-1, 0, [1, ]}, which fits in 2 bits, though it requires using a “]” after each non-zero entry.
I wrote a preliminary version of a function to translate TFTR numbers to decimal. Exponents in the one's place do not work in this version, and irrational numbers are converted to floating-point, which of course loses precision. It is written in the interpreted JVM language Frink, which has some very useful built-in functions for the purpose, especially the nextPrime[n] function, which is blazingly fast, taking about 6s to find a 1024-bit prime. The factor[n] function will also be useful for the conversion from decimal back to TFTR; it is quite fast, factoring the first 10M integers in less than 25s on my machine, and taking only 10s to factor the product of two 50-bit primes and 1000s for two 56-bit primes. I use Frink for nearly all my daily exploratory calculations since it keeps track of all physical units, but it also has unlimited-precision rational number support which makes it quite useful for this TFTR converter.
Frink can do many other things, too, from currency conversions to dimensioned graphics to human language translation. Frink is available free and runs on any device with a recent version of Java. It can also be embedded in web pages, so if you do not want to install it you can go to such a page and use it online.
Working version 1.0 :
//primeArray[n] returns an array of n prime numbers
//starting: [1,2,3,5], of length n + 1, so the nth prime is @n
//define test for positive integers, boolean return
positiveInteger[x] := (x>=1) && ( x % 1 == 0)
primeArray[place is [positiveInteger]] :=
{
ret=[1]
for cnt = 1 to (place-1)
ret@cnt=nextPrime[ret@(cnt-1)] //nextPrime[] is a Frink built-in function
return ret
}
// Ternary Factor Tree Representation to Decimal
// Input must be an array, possibly multidimensional,
// whose elements are either in{-1,0,1} or are arrays whose elements are in{-1,0,1}
// when recursion bottoms out (leaf nodes). THIS IS NOT CHECKED!
// Arrays starting with -1 are negative. Later negative elements are in denominator.
// Elements which are themselves arrays represent exponents, whether positive, negative
// integer or rational. Deeper levels of arrays can specify irrational exponents, super-exponents etc.
TFTRtoDec[x1] :=
{
x1 = toArray[x1] // cast to array needed to allow recursion since input=array, output=number
ret=[x1@0] //first element of input (“one's place”) acts as sign or zero trit
if length[x1] <> 1
{
cnt = 0
b = primeArray[length[x1]] // array of first x1 prime numbers, b@0=1
while cnt < length[x1]
//raise each prime to the power of the corresponding input array's element
{
ret@(cnt+1) = b@(cnt)^TFTRtoDec[x1@(cnt)] //recursion
cnt = cnt + 1
}
}
return product[ret] //return product of 1-D array elements, which is a number, not array
}
No comments:
Post a Comment