forked from unkadoug/contlog
-
Notifications
You must be signed in to change notification settings - Fork 0
A representation for rational numbers based on fixed-width continued logarithms
License
Arboratum-Open/contlog
Folders and files
| Name | Name | Last commit message | Last commit date | |
|---|---|---|---|---|
Repository files navigation
Contlog - representing numbers as continued logarithms Introduction In his notes on continued fraction arithmetic, Gosper introduced continued logarithms as an alternative to continued fractions for representing real numbers. Continued logarithms are based on ones and zeroes, not arbitrary integer values, and are thus better suited to binary representation. In his representation, if s is a string of bits that represents some real number x, then the strings 1s and 0s respresent, respectively, the numbers 2x and 1+1/x. Assume that the empty bit string represents infinity (oo), so that the first few positive integers are expressed as 1: 0 2: 10 3: 1010 4: 110 5: 110110 Define the right-associative ':' operator by x:y = 2**x + (2**x)/y so that the expression of 5 above can be seen as 5 = 2:2:oo = 4+4/(4+1/oo) and more generally, a binary string (1^a)0(1^b)0(1^c)0(1^d)0... represents the number a:b:c:d:... There are small problems with this representaion, but small corrections can address them. First, it's a representation ill suited to fixed width fields. Adding an extra 0 or 1 at the beginning or end of a string changes its value, so it seems that a length must be stored separately, or a special terminating character must be added. It is also not immediately clear which of two given bitstrings represents the larger of two values. Also, numbers less than one are not given a representation. Representation To address those problems, define the contlog representation of a number as follows. An incomplete string of 0's of infinite length, represents oo. If s is an incomplete string that represents the number x, and b is a bit to be prepended to the incomplete string, then bx is an incomplete string that represents the number 2x, if b is the first bit of x, and 1+1/x if b is not the first bit of x. If s is an incomplete string that will have no more bits prepended to it, then the unsigned completed string represents the number x if the first bit of s is 1, and 1/x otherwise. In the unsigned contlog representation, the first few positive integers are 1: 1 2: 11 3: 1101 4: 111 5: 111001 6: 11101 7: 11101101 8: 1111 9: 11110001 and their reciprocals are the twos-complement negations of those representations: 1/1: 1 1/2: 01 1/3: 0011 1/4: 001 1/5: 000111 1/6: 00011 1/7: 00010011 1/8: 0001 1/9: 00001111 More generally, the bitstring (1^a)(0^b)(1^c)(0^d)... represents the number (a-1):(b-1):(c-1):(d-1):... and the bitstring (0^a)(1^b)(0^c)(1^d)... represents the reciprocal of that number. Finally, to get signed numbers, prepend a 0 to the unsigned completed string that represents x, and that string represents x in the signed representation; take its twos-complement for the negative of that value. With 4 bits, and assuming that all the bits after the first four are zero, the numbers that can be represented are 0000: 0/1 0100: 1/1 1000: -1/0 1100: -1/1 0001: 1/4 0101: 3/2 1001: -4/1 1101: -2/3 0010: 1/2 0110: 2/1 1010: -2/1 1110: -1/2 0011: 2/3 0111: 4/1 1011: -3/2 1111: -1/4 If two twos-complement integers i and j satisfy i < j, and those bits are interpreted instead as contlog representations of rational numbers contlog(i) and contlog(j), then necessarily contlog(i) < contlog(j). Extracting ratios from this representation While this representation is great for representing exactly rational numbers with small numerator and denominator in just a few bits, it sacrifices the representation of large numbers, especially ones near powers of two. For example 127=6:0:5:0:4:0:3:0:2:0:1:0:0, so the signed contlog representation of 127 requires 36 bits before the infinite string of zeroes begins. Computing a 32-bit approximation to 127/1 requires rounding; this implementation rounds up or down if the truncated bits are lexicographically more or less than "1000..", and otherwise round toward the value with 0 as its last stored bit. Translating that bit string back to a rational number, leads to the result 6:0:5:0:4:0:3:0:3 = 37722176/297025, which is not likely to be an expected result. To provide a more expected result, this implementation considers a fixed size bit string to represent the interval that includes all the ratios that would be converted to that bit string, and picks the one to represent the interval that has the smallest denominator. For a fixed-size bit string that ends in a zero, that includes the values at the endpoints of the interval, and for the others, it does not. Otherwise, two consecutive bit strings could map to the same ratio. For the case of 127/1, this produces the expect result 127/1. For 1000/999, the result looks like 1000/999, and not 470999/470528. Arithmetic Where Gosper seeks to compute with unbounded continued fractions, this implementation aspires only to fixed-width operands and results. Thus, it is feasible to completely decode one operand into a numerator and denominator before considering the other operand at all, and this implementation does that. Those two values are scaled up, doubling both until one or both of them would overflow if doubled again. The values are used to form a homographic function that is evaluated at the value of the other operand to compute the composition of the two operands. So, for example, to compute x + y, first find that y=n/d, and then form (n + dx) / (d + 0x) and update the four coefficients as the leading bits of x are consumed. When such an update would lead to overflow, scale the coefficents down first, to prevent the overflow. The result can be a value with a zero denominator, when the computed value is too large or small to be approximated in the number of available bits. Test program The 'contlog' program produced from this source code is a simple calculator that uses the contlog representation, and allows both integer ratios and hexadecimal bitstrings to be used to represent operands, and displays results in both forms, and also in a familiar floating point form. Sample usage: $ contlog 4/7 x: 4/7 (26000000) = 0.571428571429 $ contlog 4/7 - 5/9 x: 4/7 (26000000) = 0.571428571429 y: 5/9 (24000000) = 0.555555555556 x-y: 1/63 (01042260) = 0.015873015873 $ contlog 55555555 x: 2178309/1346269 (55555555) = 1.618033988750 $ contlog 2/1 / x: 2/1 (60000000) = 2.000000000000 sqrt(x): 8119/5741 (4e38e38e) = 1.414213551646 x/sqrt(x): 8119/5741 (4e38e38e) = 1.414213551646
About
A representation for rational numbers based on fixed-width continued logarithms
Resources
License
Stars
Watchers
Forks
Releases
No releases published
Packages 0
No packages published
Languages
- C 100.0%