Author: LeRoy N. Eide Created: 03-Apr-2008 Modified: 12-Jul-2008 Charset: US-ASCII; Displays best with a mono-spaced font ; Lines no longer than 79 characters The following is a somewhat brief description of a representation scheme for rational numbers -- including some discussion about addition and subtraction of numbers so represented. Most of this is derived from personal thoughts and notes developed over the past few years. =============================================================================== Consider the bi-directionally infinite polynomial in b ... + d[2]*b∧(2) + d[1]*b∧(1) + d[0]*b∧(0) + d[-1]*b∧(-1) + ... where: + * ∧ mean respectively addition, multiplication, and exponentiation; - is used conventionally as a negation sign (and also subtraction); ... (ellipsis) is used conventionally for (possibly) omitted material and where "x...y" means that "y differs from x"; .. (short ellipsis) is used for possibly omitted material and where "x..y" means that "y may be identical to x"; d[i] means "d sub i for some integer i", i.e. the coefficient of b∧(i), and each d[i] is a member of an ordered set of "digits" of cardinality b, one of which is chosen to represent the value zero, e.g. {..,0,..}, implying that b > 0 (a non-empty set) but in practice it is assumed that b > 1. The polynomial above is generally given as the interpretation of a "number" as typically written, e.g. 123.95 where b is assumed to be ten and d's are chosen from the ordered set {0,1,2,3,4,5,6,7,8,9}, i.e. d[2]=1, d[1]=2, d[0]=3, d[-1]=9, d[-2]=5. The zero digit is conventionally represented by the character '0'; other digits in this ordered set are also assumed to represent integer values descending (to the left) or ascending (to the right) in steps of one. Also, the (radix) point is conventionally placed between the d[0] and d[-1] digits (although it should arguably be placed beneath the d[0] digit). And zeros are conventionally thought of (but generally unwritten) as extending infinitely on both sides of the written number. So much for convention. =============================================================================== Euler's Claim: ------------- S(x) = ... + x∧(3) + x∧(2) + x∧(1) + x∧(0) + x∧(-1) + x∧(-2) + x∧(-3) + ... or SUM(x∧i) over all integers i is identically zero for all x. At first blush this seems preposterous, but there are some plausible reasons to suspect the (computational) truth to this claim. Without expounding much, simply consider the implications of: x*S(x) - S(x) = 0 The Author accepts Leonhard Euler's claim in the discussion that follows. =============================================================================== The Notation used herein is described below. Be patient -- it starts out looking rather ugly but becomes increasingly beautiful (and useful) after a little development ... ------------------------------------------------------------------------------- The Digits: ---------- An ordered set of digits (symbols) are separated by commas and enclosed in curly braces, e.g. {0,1,2,3,4,5,6,7,8,9} also {0,...,9} or {-,0,+} but if all of the digits are single characters, the commas may be omitted, e.g. {0123456789} also {0...9} or {-0+} An ellipsis is never used if the omitted content is not obvious from context. If it is unclear which digit represents zero, that digit is enclosed in parentheses (which may also act as digit separators if commas would otherwise be needed), e.g. {M(Z)P} or {M,(Z),P} but the use of commas is encouraged if there are any multi-character digits since {MINUS,(ZERO),PLUS} would be ambiguous without the commas. The primary consequence of designating some digit to be the zero is that the location of the zero digit entirely determines the characteristics of the addition and subtraction (and multiplication) tables. The set of digits, if specified, is always mentioned external to (and usually following) the number being represented, e.g. 123.95 {0123456789} If the set of digits is conventional or obvious from context, the set of digits won't be mentioned at all. Note that digits may be represented by "non-digit" symbols but the use of any of the following characters as digits should (and will) be avoided: { } [ ] ( ) < > \ | / : , . All of these characters except ':' are used in the rational number representation described herein; ':' is used notationally in the computation apparatus (described below). The characters + - 0 = # are also used in the computation apparatus but in a manner that causes no conflict with their simultaneous use as digits. Additionally, the character '~' is used to indicate a complement but, again, this usage causes no conflict with its use as a digit. The characters '+', '-', and '0' are used for additive and subtractive carries regardless of base; think of these as "positive one", "negative one", and "zero" respectively. Of special note is the use of '=' for double-minus and '#' for double-plus digits (except where pressed into service for "equality" and "inequality"). The digits '0' through '9', the point '.', and also the characters [ ] ( ) < > \ | / * ∧ + - = are used mathematically in conventional ways; these uses will be clear from context (or with an explanatory note if needed). An attempt is made to distinguish symbols from values by enclosing symbols in single quotes (e.g. '0') and spelling out values (e.g. zero). But since everything is symbolic at some level, the reader will need to resolve many symbol vs. value conflicts from context. ------------------------------------------------------------------------------- The Base: -------- If needed, the base b may be noted in square brackets where the base itself (possibly signed) is written in conventional base ten, for example [10] or [3]. Otherwise, the base may be inferred from the cardinality of the specified set of digits (if present) or from context. The base, if specified, is always mentioned external to (and usually following) the number being represented, e.g. 123.95 [10] ------------------------------------------------------------------------------- The Number and Its Infinite Extensions: -------------------------------------- Two bars delimit what is generally considered the number proper. If powers of the base increase to the left, \'s are used: \123.95\ If powers of the base increase to the right, /'s are used: /59.321/ The intended mnemonics are: \ rises to the left, / rises to the right. In either case, the infinite sequence of zeros to both the left and right are also always indicated with angle brackets as <0\123.95\0> or <0/59.321/0> where the point appears between the digits that are the coefficients of the b∧(0) and b∧(-1) terms of the representative polynomial in b. If the digits of the number are multi-character, commas are used to separate the digits one from another (the point, if present, as well as \ or / may also act as digit separators), e.g. <_\I,II,III.IX,V\_> [10] {(_),I,II,III,IV,V,VI,VII,VIII,IX} ------------------------------------------------------------------------------- The Point and Scale Factor: -------------------------- Note that the (radix) point cannot appear outside of the enclosing bars! If the point is omitted, it is assumed to be nestled in the (inside) acute corner of one of the bars, e.g. <0\42\0> means <0\42.\0> and <0/24/0> means <0/.24/0> both of which represent the answer to life, the universe, and everything! As previously mentioned, it would be preferable to designate the location of the point by, well, just "pointing" at the digit that is the coefficient of b∧(0) -- something like <0\12395\0> ∧ possibly with an integer "scale factor" (in conventional base ten) placed below, e.g. <0\12395\0> ∧ -2 All of which gets rather notationally messy. As a compromise (and to avoid multi-line notation), the point may be replaced by a (possibly signed) scale factor wrapped in round brackets (i.e. parentheses), e.g. <0\123(0)95\0> or <0\12395(-2)\0> Note that '.' is simply shorthand for '(0)'. Think of '()' as a "really big dot" with a (base ten) integer written inside of it. This "dot" may be moved either right or left as needed, its contained integer increasing if moving "upward" (toward higher powers of the base) or decreasing if moving "downward" (toward lower powers of the base) -- just think of "upward" as "left" for \\ or "right" for //, else "downward". All of this is, of course, nothing more than a sort of embedded scientific notation. In any case, the point (or the really big dot with enclosed scale factor) must always remain between the bars. ------------------------------------------------------------------------------- The Bars: -------- The \\ and // bar notations are themselves without much grace. If one conventionally (and always) writes numbers only in one direction or the other, then it's cleaner (and clearer) to use vertical bars instead. This usage will be adopted from here on, using || for \\ throughout unless some non-obvious distinction needs to be drawn. <0|123.95|0> means <0\123.95\0> unless otherwise noted. Note that Arabic actually writes its numbers low-order digit first -- but since those numbers are written right-to-left, they appear to be the "same" as ours. Historically, when the West adopted the Arabic way of writing numbers, it didn't correct for the direction in which they were written ... it seems to have been a sufficient accomplishment that the concept of zero was finally accepted (perhaps for no other purpose than as a placeholder for a "missing digit"). We have by now generally accepted zero as an actual digit, but a lot more acceptance is going to be needed in much of what follows! ------------------------------------------------------------------------------- The Replication Units: --------------------- The Right Replication (or Repetition) Unit (hereinafter the RRU) indicates the repeating sequence of digits that go ever onward for decreasing powers of the base. Examples: <0|0|0> means 0.0000... or more simply |0> means 0000... <0|0|3> means 0.3333... |3> means 3333... <0|0|14> means 0.1414... |14> means 1414... The following are allowed for an RRU: a) Internal replication -- |14> may be rewritten as |1414> or |141414> or ... b) Internal contraction -- |829829> may be rewritten as |829> c) External emission -- |567> may be rewritten as 5|675> or 56|756> or ... d) External absorption -- 12|312> may be rewritten as 1|231> or |123> In (c) and (d) above, care must be taken to explicitly fix the point preceding the bar before un-rolling and/or re-rolling the infinite spool of repeating digits across the bar; the point cannot simply be assumed to immediately precede the bar nor can the point be absorbed into the spool of digits. If necessary, the point can always be converted into a scale factor and then moved as needed (while appropriately adjusting the scale factor, of course). In (d) above, a digit can be absorbed only if it could have been previously emitted. Also note that both emission and absorption appropriately rotate the RRU contents (but do not otherwise permute it). All of this is, of course, obvious after some brief thought. The Left Replication (or Repetition) Unit (hereinafter the LRU) indicates the repeating sequence of digits that go ever onward for increasing powers of the base; items (a) through (d) apply to an LRU as well and with similar comments and caveats. But, you say, "Isn't just '<0|' the only LRU?" I say, "Well, no ... but wait until we cover a few other matters!" =============================================================================== Complements: ----------- The complement of a number is simply that number with each of its digits replaced by its complementary digit (the point is unaffected). Each digit in the ordered set of digits has an index into that set (which is not necessarily the same as its value); its complement is the digit with the same index but counting from the other end of that same ordered set. For an odd base, one of the digits (the central one) will be its own complement (self-complementary). Examples: Base ten {0123456789} complements {9876543210} -- the so-called 9's complement Base two {01} complements {10} -- the so-called 1's complement Balanced ternary {-0+} complements {+0-} Skewed four {=-0+} complements {+0-=} The symbol '~' is often used as a prefix (operator) to indicate a complement and may be so used here: ~<0|123|45> [10] just means <9|876|54> [10] The astute reader will notice that the complementation of a number involves all of its digits -- not merely the digits between the bars! Note that for any base the sum of a digit and its complement is a constant whose value can be represented by some single digit (i.e. this sum will never produce a non-zero carry). It is this characteristic that ultimately permits us to identify the complement of a number with the negative of that number. Complements provide intrinsically-signed numbers. Consider a number N of the form <l|npm|r> where l is the LRU contents, n is the so-called integer part of the number, p is the point (or scale factor), m is the so-called fractional part (mantissa) of the number, and r is the RRU contents. If n is absorbed by l and m by r, then <l|p|r> may be written as <l|r> provided that the scale factor is zero, e.g. <0|1> is simply a convenient shorthand for <0|.|1> In this compact notation a single bar separates the digits of the number into those that are coefficients of the negative powers of the base and those that are coefficients of the non-negative powers (which includes the so-called "units" digit). The determination as to whether N < 0 or N = 0 or N > 0 can be made without resorting to any extrinsic sign convention; signs are intrinsic for any base -- stay tuned! If N and its complement were added, the result would be <k|kpk|k> for some constant k (where each k here may actually be a sequence of k's). We will see that numbers of this form are (computationally) merely variants of zero -- but first we must learn how to add and subtract! ------------------------------------------------------------------------------- Negative Numbers: ---------------- Most people are unaccustomed to dealing with numbers in a base other than ten and with negative numbers in general. Negative numbers are for most a concept without substance since nowhere in elementary or secondary schools are negative numbers written with intrinsic sign -- all numeric signs are presented as extrinsic and not as part of a number itself. This requires a separate computational process to manipulate these extrinsic signs, leading to the notion that negative numbers are somehow less "real" than positive (or unsigned) numbers. This is indeed unfortunate. For those who dabble with balanced ternary (or other balanced or skewed systems), the notion of an intrinsic sign is far more concrete and clear. But even many computer programmers cannot see the typical computer representation of integers as binary with intrinsic sign for what it is, preferring instead to think of a "sign bit" followed by an unsigned base two integer that is complemented for some magical and obscure reason. The computation apparatus described and used herein handles numbers with intrinsic sign for all bases. Extrinsic signs are avoided wherever possible. =============================================================================== A variety of operations are possible involving rational numbers represented as described above. These operations can be performed almost entirely symbolically, requiring no more actual numerical computation than the ability to add or subtract (or multiply) single digits (with a possible single digit carried in and/or out). Even these single-digit operations can be accomplished symbolically by the arithmetically impaired (or by a computer program) through the use of addition or subtraction (or multiplication) tables. It is interesting to note that during the European Middle Ages the expected mental computation abilities of the average householder or merchant was the addition or subtraction of single digits no greater than five with a possible single "memory location" (a free hand) to "hold" a single-digit intermediate result -- everything else was done symbolically by moving counters (often pebbles or small shells -- the "calculi") around a counting board (hence "calculation"). In most cases, the "calculator" had no sense (nor needed any) of the actual numbers being operated on nor of the final numerical result. Counters were "added to" or "taken from" the board, the final collection of counters was normalized to a standard representation (again using simple but possibly opaque rules), and the result was the "answer". Multiplication was essentially higher mathematics requiring two counting boards; division required an advanced mathematical education. [Citation needed here] Similarly, in what follows, no more mental computation is required than the ability to add or subtract (or multiply) single digits in whatever number base is being considered (with a possible single digit carried in and/or out). The computation apparatus is designed to keep track of carries (no free hand required!). And referring to some prepared tables for sums or differences (or products) is not considered cheating. ------------------------------------------------------------------------------- Addition: -------- As we all learned in elementary school, adding two unsigned (decimal) numbers requires that a) the (decimal) points "line up" b) zeros are assumed to the right (but no further than needed) c) zeros are assumed to the left (but no further than needed) and then addition proceeds, starting at the rightmost column of digits, by adding each column and propagating any carry (either zero or one) to the column immediately to the left; continue until done. But we all had rather simplistic views of what "rightmost" and "done" actually meant. And subtraction had its own set of arcane rules and restrictions ... The more general procedure requires that a) the points "line up" (meaning that the scale factors are equal and are positioned one above the other) -- move the "dot"s as needed to adjust the scale factors; b) the bars "line up" -- emit from each RU as needed; c) the angle brackets of the RUs "line up" (meaning that the LRUs are of equal length and the RRUs are of equal length) -- replicate RUs to achieve least-common-multiple lengths and then addition proceeds, starting at the rightmost column of digits, by adding each column and propagating any carry (negative one, zero, or positive one) to the column immediately to the left; continue until done -- but with the caveat that what is carried into an RU must also be carried out (like the Wilderness Rule "Carry out what you carried in!"). That the magnitude of each carry is either zero or one, regardless of base (balanced, skewed, or otherwise), is left as an exercise for the reader -- but the proof is not difficult. Here's an example of a base ten addition problem: <0|123.95|0> rewrite <0|123.95|0> + <0|4|3> + <0|004.33|3> by emission ------------ =0 + =0 -- carries <0|128.28|3> Note that '+' and '-' are used to indicate non-zero carries and that all zero carries are omitted here except for the carry-in for each RU sum. Additionally, if the carry-out for an RU differs from its carry-in, then a '#' is used to mark this difference (here meaning inequality); otherwise an '=' is used (both '#' and '=' here are notational devices and are only placed above non-digits). If the carry-out for the RRU sum is non-zero, then the initially assumed carry-in of zero was incorrect; in this case, the addition is aborted and then restarted assuming the correct initial carry-in for the RRU sum (or one might cheat and simply add the carry-out back into the RRU, thereby correcting the initial incorrect assumption -- but only if the initially assumed carry-in was zero!). But what if the carry-out of the LRU of the sum differs from its carry-in? We can't just "correct" the carry-in (that carry was computationally generated!) but we can extend the LRUs and have another go at it. Here's an example: <0|92|34> rewrite <0|92.3|43> by emission + <0|8.6|1> + <0|08.6|11> by emission and replication ----------- =0#+ + = 0 -- carries <0:1:00.9|54> rewrite <0|100.9|54> Here a broken bar ':' is used as a tentative bar for the LRU of the sum until the LRU carry-out equals its carry-in. The leftmost broken bar is then retained as a full bar, the other broken bars being removed. The broken bar ':' may need to be used up to three times (that no more than three are ever required is left as an exercise for the reader -- ponder the possible carries). All summed LRUs should be computed in this manner. The requirement that the bars and angle brackets of the addend and augment all line up before the addition can proceed insures that the RUs of the sum are computed correctly and be the same length as the RUs above them. After the sum is computed, it might be possible to simplify its RUs by contraction. Similar comments apply to the subtrahend, minuend, and the difference of subtraction. ------------------------------------------------------------------------------- Subtraction: ----------- Subtraction is similar to addition but with digit differences rather than sums and negative carries (or so-called borrows). Recall that carries are always additive for both addition and subtraction. Here's a base ten example: <0|92|34> rewrite <0|92.3|43> by emission - <0|8.6|1> - <0|08.6|11> by emission and replication ----------- =0 -- = 0 -- carries <0:83.7|32> rewrite <0|83.7|32> It is tempting to think of subtraction as merely the addition of a complement: <0|92|34> rewrite <0|92.3|43> by emission +~<0|8.6|1> + <9|91.3|88> by emission and replication ----------- +#+0 -- carries |31> -- abort (wrong carry-out)! =+ +=++ -- carries <0:83.7|32> rewrite <0|83.7|32> Although the addition of a complement will always produce the correct subtractive result, the form of that result may be different from that which straight subtraction would yield. Here is a standard base three example to illustrate this point: <0|10|2> rewrite <0|10|2> - <0|1|2> - <0|01|2> by emission -------- =0 - =0 -- carries <0:02|0> rewrite <0|2|0> by absorption But adding the complement of <0|1|2> yields: <0|10|2> rewrite <0|10|2> + ~<0|1|2> + <2|21|0> by emission -------- =1 =0 -- carries <0:01|2> rewrite <0|1|2> by absorption Both results are correct but differ in form, namely both are equivalent eventual representations of two. =============================================================================== Equivalent Eventual Representations: ----------------------------------- Some numbers have more than one conventional form but they are computationally (and mathematically) equivalent. For example: 1.000... or <0|1|0> [10] 0.999... or <0|0|9> [10] Such forms are characterized by the fact that their RRUs will accept more than one assumed initial carry-in which they will then generate as the carry-out. This is equivalent to adding zero (<0|0|0>) to a number but assuming either '+' or '-' as the initial carry-in instead of '0'. <0|1|0> will accept either '0' or '-' (the latter generating <0|0|9>) <0|0|9> will accept either '0' or '+' (the latter generating <0|1|0>) The term "eventual" is usually applied only to a number represented with a non-zero RRU (and an LRU of either <0| or ~<0|) that is equivalent to another representation with an RRU of |0>, not to a number represented with an RRU of |0>. Conventionally, an RRU of |0> is thought of as simply terminating the representation rather than repeating and leading to some "eventuality"; unconventionally, |0> is no less an RRU than, say, |9> and both are treated similarly herein. In any case, there are equivalent (and eventual) representations having nothing to do with zero. Such equivalent eventual forms are not problematic. =============================================================================== A Plethora of Zeros: -------------------- It is obvious that <0|0|0> is computationally zero; it yields itself when added to itself. But so does <9|9|9> [10] -- a simple exercise. In fact any number consisting of a single digit throughout is computationally zero. Recall Euler's claim mentioned at the beginning -- this simply states that <1|1|1> is zero for any base whatsoever! This is one of the consequences of the statement (also aforementioned) of b*S(b) - S(b) = 0 for any base b. Since all numbers consisting solely of a single digit are merely some multiple of <1|1|1> then all of these must be computationally zero as well. And so are numbers that consist solely of some repeating sequence of digits, such as <824|824|824> since (b∧3)*S(b) - S(b) = 0 for any base b and similarly for (b∧n)*S(b) - S(b) = 0 for any n. As a notational convenience, a number like <0|0.0|0> which can be written as <0|.|0> by absorption may also be written as <0|0> by convention (as aforementioned) or even more compactly as just <0> by convention (established here). The same may be done for any zero, e.g. <824|824|824> written compactly as <824> which may also be written as <248> or even <482> Due care must be taken when expanding a compact zero (such as <824>) into a full form with double bars which ultimately needs to represent a bi-directionally infinite repeating sequence of digits (such as ...824...). Note that "bi-directionally infinite" means that the number extends infinitely to both the left and right, not that the number is infinite! The following are possible and correct expansions of <824>: <824|824> <824|8|248> <824|82|482> <248|24|824> <482|4824|824> The novice might wish to always expand a compact zero into a full form where each RU contains the compact zero and the digit sequence between the bars is some number of replications (possibly none) of the compact zero. The resulting representation can then be modified by various absorptions into or emissions out of the RUs as well as replication within either RU. Facility in writing appropriate zeros in full form comes with practice and a little bit of attention. Consider the balanced ternary representation <0|+-+|+0> {-0+} or seven and three eighths. Here are three full form zeros that match one of the components of this balanced ternary number (this skill will be useful in much of what follows): <0|000|00> <+-|+-+|-+> <0+|0+0|+0> Since all of these representations are computationally zero, the point (or scale factor) may be placed arbitrarily anywhere between the bars. But how can there be so many zeros? Isn't there really just one zero? This is something like the particle zoo of 20th-century physics which settled down only after the appropriate viewpoint was finally achieved. ------------------------------------------------------------------------------- A Plethora of Numbers: --------------------- Given any "simple" number like <0|1|0> (namely one), we can create a vast quantity of computationally equivalent forms by adding appropriate zeros to it, yielding things like <1|2|1> <8|9|8> <423|424|423> or <234|24|423> or <342|4|423> by absorption. Now wait a minute! What's really going on here? =============================================================================== The Background (or Philosophy): ------------------------------ First, think of what we really do when we write a (conventional) number. We assume a bi-directionally infinite blank slate (really filled with '0's) and a "point" (to indicate a known "units" position) upon which we will lay some "digits" in appropriate positions, making these digits differ from the blank background. We compute the value of our work (our number) by measuring the difference each digit has from the original blank (or '0') background. We are constrained in the amount of variation we can make at any position by the base of our number system -- the value at each position must be representable by one (and only one) of the digits from our ordered set of digits (this insures that the number that we want to write on our slate has a unique representation -- except for the possible eventual but equivalent representations described above). This is what the Author believes was the true insight of those who long ago discovered that zero was as much a digit as any other -- perhaps a "place holder" but a digit nonetheless. But suppose that the background on our slate consists of '1's rather than '0's -- it's still flat but everything is elevated a bit. In order to make a difference of one we need to write a '2', for a difference of two we write a '3', ..., for eight a '9' -- but (assuming base ten) how do we make a difference of nine? We must write a '2' in the next digit position on the slate (making a difference of one there, that is to say a difference of ten here) and then write a '0' in the current position (making its value be one less than the background of '1'); combined, the resulting difference from the background is nine. All of this remains true for background terrain that is hilly rather than flat -- it's the variance from the expected background, not the actual elevation, that determines the value of the number represented. The only real constraint is that the elevation (i.e. the value) at each location be representable (and represented) by one of the digits from our ordered set of digits. There are an infinite number of backgrounds -- that's why there are an infinite number of zeros (they each just follow and do not deviate from their respective backgrounds). That's the view from the outside; from the inside, there is just one zero -- the current background. So what determines the background? Well, it's just the contents of the LRU. The LRU specifies the expected terrain (the local zero); the rest of the number specifies the deviations from the expectations. And it's the first deviation (going from left to right in our conventional representation) that determines the sign of the entire number -- if the elevation is higher than expected, the number is positive; if lower than expected, the number is negative. This is the intrinsic sign. That's why <824|6|248> [10] represents negative two -- the expected digit is not '6' but '8'. If the function of being zero is assigned to the first digit in the ordered set of digits, it is not possible to represent a negative number with a background (LRU) entirely of zero digits since a descent from the background is necessary in order to form a negative number. Similarly, if the function of being zero is assigned to the last digit in the ordered set of digits, it is not possible to represent a positive number with a background entirely of zero digits since an ascent from the background is necessary in order to form a positive number. Such numbers can be represented, however, by choosing another background -- and there is an infinite collection of backgrounds to choose from. Assigning the function of being zero to an intermediate digit in the ordered set of digits permits the representation of both positive and negative numbers all with a background consisting entirely of zero digits (although another background could be chosen if desired). One way of thinking about a background in a number representation is by analogy to a carrier wave with amplitude modulation -- but with the restriction that the amplitude is constrained by both upper and lower bounds. =============================================================================== Real Subtraction vs. the Addition of a Complement: ------------------------------------------------- To say that subtraction is merely the addition of a complement is not strictly true. Complementing a number complements its background along with everything else; adding this number to another produces a sum with a "mixed" background which then conveniently more-or-less goes away in balanced systems as well as in systems where zero is an extremal (the first or last) digit in the ordered set of digits. In balanced systems the addition of a complemented zero background by itself produces no carries during the addition of the two backgrounds (producing an unchanged background); in the others a carry is (or can) be produced which ripples from the far right of the RRU and carries all the way to the far left of the LRU (flipping the background back to zero). It is seductive to think of subtraction as being the same as the addition of a complement -- but it's not, as is well illustrated by considering skewed systems. Subtraction differs from the addition of a complement in that the resulting backgrounds differ by <0> - ~<0>. Consider four and two thirds less two thirds in the skewed system {-0+#}: Doing "real" subtraction yields the following: <0|+0|#> rewrite <0|+0|#> - <0|#> - <0|00|#> by convention and emission -------- =0 =0 -- carries <0:+0|0> rewrite <0|+0|0> or four. Adding the complement of two thirds: <0|+0|#> rewrite <0|+0|#> + ~<0|#> + <+|++|-> by convention and emission -------- =0 =0 -- carries <+:#+|+> rewrite <+|#+|+> which is still four but with a background biased by <+>. =============================================================================== Adjusting the LRU (or the Background): ------------------------------------- Subtracting the background (the LRU) will clear the background if at all possible. Here are two base ten examples: <47|52|47> [10] or positive five - <47|47|47> [10] ---------- = 0 - = 0 <00:05|00> or <0|5|0> by contraction and absorption. <42|00|42> [10] or negative forty-two - <42|42|42> [10] ---------- =-- - = 0 <99:58|00> or <9|58|0> by contraction or ~<0|41|9> or ~<0|42|0> (see "Adjusting the RRU" below). If the background cannot be cleared by this process, the LRU will become a single digit (the complement of '0') if '0' is either the first digit (and the number is negative) or the last digit (and the number is positive) in the ordered set of digits of the system being considered, e.g. {012} or {=-0} respectively. This won't happen in a system where the '0' digit is not extremal, e.g. {-0+} -- in these systems the background can always be leveled to zero. That is, background clearing always works if the system's '0' digit is not extremal since in such a system it is always possible to represent both positive and negative numbers against a background (LRU) of zero. In balanced or skewed systems, background clearing by subtraction is always possible because there is wiggle room both up from zero (for positive numbers) and down from zero (for negative numbers). But for extremal systems where zero is at one end of the ordered set of digits, there is wiggle room in only one direction. If the the background cannot be cleared by subtracting it from the number, then the background will simply end up as a single digit, namely the complement of the zero digit. If the '0' digit is extremal there are two cases: a) Negative numbers cannot be represented against a background of zero (as for {012} and the like); b) Positive numbers cannot be represented against a background of zero (as for {=-0} and the like). In either of these cases, though, subtracting the background will cause it to become a single extremal digit. Here are two more examples using the system {=-0}: Can the background be removed from <-|0|-> or <=|-|=> (both are one)? <-|0|-> {=-0} rewrite <-|0|-> - <-> - <-|-|-> ------- =+ =0 -- carries <=|=|0> or equivalently <=|-|=> <=|-|=> {=-0} rewrite <=|-|=> - <=> - <=|=|=> ------- =+ =0 -- carries <=|=|0> or equivalently <=|-|=> Since our number is positive but there's no wiggle room above zero, any attempt to clear the background simply yields the single-digit background <=> or ~<0>. The LRUs of numbers do not need to be adjusted before either adding or subtracting them; sums and differences of backgrounds simply result in other backgrounds that properly support the sum or difference. Here's an extended example of the addition of two numbers with different (and patently obscure) backgrounds. First, a bit of review of balanced ternary's, well, "bits": -1/2: <0|--> or <0|-> -3/8: <0|-0> -1/4: <0|-+> -1/8: <0|0-> 0: <0|00> or <0|0> or <0> +1/8: <0|0+> +1/4: <0|+-> +3/8: <0|+0> +1/2: <0|++> or <0|+> Now, consider the addition problem 2.625 1.25 ----- 3.875 but do it in balanced ternary {-0+} with weird backgrounds. Here goes: <0|2.625|0> [10] or <0|+0|-0> {-0+} three less three eighths (or two and five eighths) rewrite <00|+0|-0> by emission + <0-|0-|0-> add a background of <0-> ---------- = 0 = 0 -- carries <0-:+-|--> rewrite <0-|+-|--> or <0-|+-|-> by contraction or <0-|0+|+> by equivalence or <-0|+|+> by absorption or just two and five eighths. <0|1.25|0> [10] or <0|+|+-> {-0+} one and a fourth rewrite <00|0+|+-> by emission and replication + <+-|+-|+-> add a background of <+-> ---------- +#+0 -- carries |0+> -- abort (wrong carry-out)! = 0 += + -- carries <+-:++|--> rewrite <+-|++|--> or <-+|+|--> by absorption or <-+|+|-> by contraction or <-+|0|+> by equivalence or just one and a fourth. Finally, the balanced ternary addition problem: <-0|+|+> {-0+} two and five eighths + <-+|0|+> {-0+} one and a fourth -------- +#0 -- carries |-> -- abort (wrong carry-out)! = -# 0#++ +=+ -- carries <+0:++:--:-|0> rewrite <+0|++---|0> {-0+} or <0+|+---|0> by absorption or three and seven eighths -- oh, really? Let's clear this new background: <0+|+---|0> rewrite <0+|+---|00> by replication - <0+> - <0+|0+0+|0+> by emission ----------- = 0 --- = 0 -- carries <00:00++|0-> rewrite <00|00++|0-> or <0|00++|0-> by contraction or <0|++|0-> by absorption or four less an eighth which is just three and seven eighths! ------------------------------------------------------------------------------- Adjusting the RRU: ----------------- For any given system, one (and only one) of the following applies (where 0 means the digit assigned the function of being zero and ~0 means the complement of that digit): a) 0 < ~0 as in {012} where '0' precedes '2' or {-0+#} where '0' precedes '+' b) 0 = ~0 as in {-0+} where '0' equals '0' or {=-0+#} where '0' equals '0' c) 0 > ~0 as in {=-0} where '0' follows '=' or {=-0+} where '0' follows '-' In case (a) if the RRU consists of a single digit that is the complement of '0' and that digit is extremal, then the RRU can be reduced to zero by adding <0> with an initial carry of '+'; this can occur for {012} but never for {-0+#}. In case (b) no single digit can be both the complement of '0' and extremal (well, maybe base one {0} but that's not very interesting!). In case (c) if the RRU consists of a single digit that is the complement of '0' and that digit is extremal, then the RRU can be reduced to zero by adding <0> with an initial carry of '-'; this can occur for {=-0} but never for {=-0+}. In order for a non-zero RRU to be part of an equivalent eventual representation, it must consist of a single extremal digit; in order for it to be convertible to an RRU of zero, then '0' must be the other extremal digit. There are, of course, other pairs of equivalent eventual representations that do not involve the '0' digit; they always do, however, involve the extremal digits of the system being considered: <0|0|+> {-0+} or one half, <0|+|-> {-0+} also one half. Converting a representation to an equivalent eventual representation might not set the RRU to zero but it does not affect the LRU; arbitrarily setting the RRU to zero, however, by subtracting the RRU from the number generally does alter the LRU. Requiring that both the LRU and RRU be simultaneously zero is to live in a world of integers only; requiring that the LRU and RRU be the same is simply living in a different world of integers. =============================================================================== [Material needed here] ------------------------------------------------------------------------------- Base Zero: --------- Here the ordered set of digits is empty, namely {} -- there's nothing to designate as the zero digit. Forget I even mentioned it ... ------------------------------------------------------------------------------- Base One: --------- Again, uninteresting. At least there is a digit in {0} to designate as the zero digit, namely '0' -- but there are no numbers that we can represent other than zero itself, namely <0> (i.e., there is no way to make a difference from the one-and-only background). ------------------------------------------------------------------------------- Negative Bases: -------------- If the base b is negative, then all even powers of the base are positive so we can consider this as a "normal" number in base b∧(2). Consider base negative two [-2] {01} as an example. In this so-called nega-binary system, each even power of the base makes a positive (or zero) contribution to the value of the number while each odd power of the base makes a negative (or zero) contribution. A brief examination will show that nega-binary numbers have unique (but allowing for eventual) representations. The digits here can be considered in pairs as the skewed base four system [+4] {=-0+}: [-2] [+4] ----- ---- 0: 00000 0000 1: 00001 000+ 2: 00110 00+= 3: 00111 00+- 4: 00100 00+0 5: 00101 00++ 6: 11010 0+== 7: 11011 0+=- 8: 11000 0+=0 9: 11001 0+=+ 10: 11110 0+-= 11: 11111 0+-- 12: 11100 0+-0 13: 11101 0+-+ 14: 10010 0+0= 15: 10011 0+0- 16: 10000 0+00 ... ... and so on. Since a negative base b can be "normally" represented as base b∧(2), it is only required that |b| > 1. Consequently, negative bases may be disposed of as a mere curiosity. ------------------------------------------------------------------------------- Reciprocal Bases: ---------------- A number represented in a base that is a reciprocal of an integer b > 1 seems only to be the base b number in the opposite direction (with due attention being paid to negating the scale factor and adding one since the directions of increasing/decreasing powers of the base are now swapped and the point needs to be moved to the other side of the digit to which it is adjacent). Lacking this interpretation, it is difficult to make sense of the cardinality of any ordered set of digits as relating to the base. <0\+(2)\-> [1/3] {-0+} or <0\+--.\-> [1/3] {-0+} should likely be interpreted as <0/+(-2)/-> [3] {-0+} or <0/+--./-> [3] {-0+} or, reversing the directionality of the representation, as <-\(-2)+\0> [3] {-0+} or <-\.--+\0> [3] {-0+} or just <-|(-2)+|0> [3] {-0+} in the more conventional "upright bar" notation. If one could make some other coherent sense of reciprocal bases, it might then be possible to make coherent sense of fractional bases in general. Short of that, the Author is inclined to disregard all non-integral bases as lacking even a modicum of curiosity. On the other hand, just thinking about reciprocal bases makes clearer some things that might otherwise remain rather opaque. In particular, ponder the power series generator: 1/(1-x) = P(x) = 1 + x∧(1) + x∧(2) + x∧(3) + x∧(4) + ... This is generally considered only when 0 < x < 1 for which P(x) converges, e.g. P(1/3) = 1.5 but, when squinted at in just the right way, one notices that P(1/3) = <0/1/1> [1/3] {012} or <0/.1/1> [1/3] by assumed point <0/(0)1/1> [1/3] by definition of "dot" <0\(+1)1\1> [3] by interpretation above <0\1(0)\1> [3] by moving the "dot" <0\1.\1> [3] by definition of "dot" <0\1\1> [3] by assuming the point or <0|1|1> [3] {012} in conventional "upright bar" notation which is one and a half. If x > 1 then P(x) diverges, say for x = 3 -- or does it? Clearly the generator has a well-defined (negative) value for P(3), so squinting again in just the right way, one can see that P(3) = <0/1> [3] {012} or <1\0> [3] by reversal of the bars or <1|0> [3] {012} in conventional "upright bar" notation which is negative one half (as we have seen before) -- exactly what the generator evaluates to. It's an easy exercise to show that P(b) + P(1/b) = <0|1|0> [b] for any base b > 0. =============================================================================== There's Only One Base b (for any b): ----------------------------------- For b zero, one, negative, or a unit fraction, these are all described (and dismissed) above. For any integral base b > 1 there are b different systems (one for each choice of the digit to function as the zero), each with its own addition table. Or are there? Consider the three possible base three systems: {012} -- standard ternary (sometimes {0+#} if using plus and double-plus); {-0+} -- balanced ternary; and {=-0} -- inverted ternary (using double-minus and minus) and also a generic base three system: {xyz} -- this could be any of the three systems above ... What can one say about a number represented in this generic {xyz} system? Consider: <x|yzz|y> {xyz} First, the number is positive since the first digit to deviate from the background <x> is y, which is ordered after x in {xyz} and thus x < y, so we have intrinsic (positive) sign. Second, the value of the number is determined solely by the deviations of the digits from the expected background; let us compute: up one in the 3∧(2) position -- counts for +9; up two in the 3∧(1) position -- counts for +6; up two in the 3∧(0) position -- counts for +2; then up one all the way out from the implied point -- counts for +0.5; for a total of +17.5 -- seventeen and a half. For reference, here are the addition tables for the three possible {xyz} systems (where the left-most character in each sum pair is the carry -- always represented as one of '0', '+', or '-'): {012} {-0+} {=-0} 0 1 2 - 0 + = - 0 ------------ ------------ ------------ 0 | 00 01 02 - | -+ 0- 00 = | -- -0 0= 1 | 01 02 +0 0 | 0- 00 0+ - | -0 0= 0- 2 | 02 +0 +1 + | 00 0+ +- 0 | 0= 0- 00 and the corresponding subtraction tables (where the left-most character in each difference pair is the carry): 0 1 2 - 0 + = - 0 ------------ ------------ ------------ 0 | 00 -1 -2 - | 00 0- -+ = | 00 0- 0= 1 | 01 00 -1 0 | 0+ 00 0- - | += 00 0- 2 | 02 01 00 + | +- 0+ 00 0 | +- += 00 If {xyz} is really {(x)yz}, meaning {012}, this is normally just written as: <0|122|1> or <0|+##|+> {0+#} if using plus and double-plus which is seventeen and a half in {012}. Now suppose that {xyz} is really {x(y)z}, meaning {-0+}. Then we have: <-|0++|0> - <-|---|-> adjust the background by subtracting <-> ----------- =0#+ ++ =0 -- carries <0:+:-0-|+> rewrite <0|+-0-|+> {-0+} which is recognizably seventeen and a half in {-0+}. <-|0++|0> Or with a different initial carry (+ rather than 0) ... - <-|---|-> ----------- =0#+ +++=+ -- carries <0:+:-00|-> rewrite <0|+-00|-> {-0+} But suppose that {xyz} is really {xy(z)}, meaning {=-0}. Then we have: <=|-00|-> - <=|===|=> adjust background by subtracting <=> --------- +#0 -- carries |0> -- abort (wrong carry-out)! =+ +++=+ -- carries <=:-00|-> rewrite <=|-00|-> ... no change -- but not surprising since subtracting <=> is similar to adding ~<=> which is just <0>. Perhaps one could try subtracting <-> instead ... <=|-00|-> - <-|---|-> ----------- =0#+ ++ =0 -- carries <-:0:=-=|0> rewrite <-|0=-=|0> {=-0} Compare this pattern with <0|+-0-|+> {-0+} from above. <=|-00|-> Or with a different initial carry (+ rather than 0) ... - <-|---|-> ----------- =0#+ +++=+ -- carries <-:0:=--|=> rewrite <-|0=--|=> {=-0} Compare this pattern with <0|+-00|-> {-0+} from above. And certainly subtracting <0> won't help either ... <=|-00|-> - <0|000|0> --------- =0 =0 -- carries <=:-00|-> rewrite <=|-00|-> ... no change (not surprising). We can't make the background <0> since in this system '0' is the topmost digit and there is no "up" from '0' to represent a positive number. Nonetheless, <=|-00|-> {=-0} is seventeen and a half. This behavior is not restricted to representations having a single-digit background. Being somewhat more adventurous, consider the following: <xy|zz|y> {xyz} If {xyz} is really {(x)yz}, meaning <01|22|1> {012}, then: <01|22|11> by replication - <01|01|01> adjust background by subtracting <01> ---------- = 0 = 0 -- carries <00:21|10> rewrite <00|21|10> or <0|21|10> by contraction which is recognizably seven and three eighths in {012}. If {xyz} is really {x(y)z}, meaning <-0|++|0> {-0+}, then: <-0|++|00> by replication - <-0|-0|-0> adjust background by subtracting <-0> ------------- = 0# + = 0 -- carries <00:0+:-+|+0> rewrite <00|0+-+|+0> or <0|0+-+|+0> by contraction or <0|+-+|+0> by absorption which is recognizably seven and three eighths in {-0+}. If {xyz} is really {xy(z)}, meaning <=-|00|-> {=-0}, then: <=-|00|--> by replication - <=-|=-|=-> adjust background by subtracting <=-> ---------- +# 0 -- carries |=0> -- abort (wrong carry-out)! =++ ++=++ -- carries <==:0-|-=> rewrite <==|0-|-=> or <=|0-|-=> by contraction which is still seven and three eighths in {=-0} even though the best that can be accomplished, again, is to reduce the background to <=> (i.e. ~<0>). The Author suspects, however, that "<=|0-|-=>" would not be a proper response to the haberdasher's question, "Sir, what is your hat size?". [Suggested pronunciation: "LES-iz bar-NUL-neg bar-NEG-iz MOR"] A consequence of all this is that whether a base b number is represented in the system {0,...,b-1} or {-1,0,..,b-2} or ... or {2-b,..,0,1} or {1-b,...,0} is completely irrelevant; the representation encodes the value of the number regardless of which digit is assigned the function of being zero. But it's not necessary to actually change the symbols for the digits in the representation when moving from one base b system to another. All that is needed is to designate (perhaps arbitrarily) some digit to be the zero digit which then entirely determines the properties of the addition and subtraction tables. How can this be? Remember that the background (the LRU) permeates the entire number representation and the value of that number is determined solely by the variances from that background. Adding two numbers simply sums the variances as well as the backgrounds themselves, producing summed variances against a summed background. And one may (arbitrarily) interpret that sum in a base b system other than the system that was used to produce that sum. The choice of a base b system applies to both the addend and augment (or subtrahend and minuend) and determines the addition (or subtraction) table to be used. Choosing different base b systems to sum two base b numbers will produce different backgrounds, but these "different" sums will always represent the same base b number. Here again are the addition tables for the three possible {xyz} systems but in a more abstract form (where the left-most character in each sum pair is the carry): {(x)yz} {x(y)z} {xy(z)} x y z x y z x y z ------------ ------------ ------------ x | 0x 0y 0z x | -z 0x 0y x | -y -z 0x y | 0y 0z +x y | 0x 0y 0z y | -z 0x 0y z | 0z +x +y z | 0y 0z +x z | 0x 0y 0z and the corresponding subtraction tables (where the left-most character in each difference pair is the carry): x y z x y z x y z ------------ ------------ ------------ x | 0x -z -y x | 0y 0x -z x | 0z 0y 0x y | 0y 0x -z y | 0z 0y 0x y | +x 0z 0y z | 0z 0y 0x z | +x 0z 0y z | +y +x 0z =============================================================================== Symbols vs. Values: ------------------ [forthcoming commentary] =============================================================================== Normalization: ------------- Some representations of a number are more easily comprehended than others even though all of them are equally valid for purposes of computation. The normalization of a representation simply produces a form that is as conventional and compact as possible. Converting from one form of base b to another form of base b is simply a matter of reassigning the function of being zero to a different digit in the ordered set of digits (and using different addition and subtraction tables, of course); consequently, without loss of generality, the first digit from the ordered set of digits may always be assigned the function of being zero -- later converting to another form of base b if required. Note that these so-called conversions do not require any modification of a number's representation (it remains unchanged); relabeling the digits is permitted, of course, but this does not change the relationship of one digit to another in the representation. Conversion is simply a matter of arbitrarily declaring one of the digits in the system to be the zero digit. In much of what now follows, it is convenient (and clearer) to make the simplifying assumption that a base b system is just {0,1,..,b-1}. Once a digit has been chosen to function as the zero in the system, the LRU (i.e. the background) can be adjusted and contracted to a single zero digit (or its complement). The RRU can then be contracted and possibly adjusted (if it's an eventual form) to match the LRU. Finally, each RU should absorb as much as possible (this may require the introduction and adjustment of a scale factor between the bars). If no digits remain between the bars and the scale factor is zero (or just the point), the bars (and point) may be replaced by a single bar. If the LRU is the complement of the zero digit, one may complement the entire representation and prefix a '~' character for display purposes. [Examples needed here] =============================================================================== Reciprocals: ----------- [forthcoming -- soon] =============================================================================== Multiplication: -------------- While addition is the sum of two bi-directionally infinite numbers, multiplication is essentially the infinite summation of such numbers, each being a single-digit multiple of the multiplicand with an appropriate scale factor. With a little work, multiplication can be reduced to the sum of just four bi-directionally infinite numbers, each being formed from products of finite extent. [forthcoming -- soon] =============================================================================== Division: -------- [forthcoming -- eventually] =============================================================================== Just-In-Time-Subtraction (JITS) Revisited: ----------------------------------------- Halving a (balanced) ternary integer N by doing a single subtraction -- conceptually this is computing M = 3*M - 2*M where 2*M = N If N is actually divisible by two (i.e. even), the procedure yields the correct result. Does it also yield the correct result if N is odd? Let N = 7, i.e. <0|+-+|0> {-0+}; the JITS procedure yields <-|-0-|0> which can be rewritten as <-|0-|0>. By subtracting a convenient zero, say <->, one can readjust the background of this result: <-|0-|0> - <-|--|-> -------- =0 =0 -- carries <0|+0|+> which is recognizable as three and a half. So, yes, the JITS procedure also produces the correct result if N is odd -- one merely needs to adjust the background of the result to get it to zero elevation in order to more clearly see the result. =============================================================================== What's the REAL Difference Between 1's- and 2's-Complement Arithmetic: --------------------------------------------------------------------- Modern computing hardware generally represents integers as binary with intrinsic sign, abandoning attempts to represent integers as (extrinsic) sign and magnitude. So positive integers are represented as <0|n|0> [2] where the LRU is explicitly represented as a high-order bit, the RRU is implicitly assumed, and n (the number) is represented by a fixed-length string of binary digits (bits) typically of length word-size less one. Negative integers are simply the complements of corresponding positive integers which complements the LRU background (the so-called "sign" bit) without altering the bit-length of n. But what is done with the RRU? For 1's-complement hardware, the RRU is simply left unchanged (i.e. the background is assumed to extend both left and right). But 2's-complement hardware always assumes that the RRU is |0> independent of the background; consequently, an RRU carry-in of '+' is arbitrarily assumed for any complement and will convert the |1> (the complemented |0>) back to |0> carrying out a '+' across the bar. Unfortunately, if all the bits between the bars are also one, the carry continues across the other bar and finally carries out of the LRU as well. No carry-in/carry-out rules are violated, but <1|1|1> will always get converted to <0|0|0> (this is either good or bad, depending on one's computational point of view). Such hardware usually implements a "logical" complement in addition to an "arithmetic" complement, as well as a number of other "logical" operations that function rather like their 1's-complement "arithmetic" counterparts. The Author remains computationally agnostic on this point. =============================================================================== Credits: ------- The Author's co-worker and office mate, John Halleck, deserves much credit for being a sounding board for bizarre ideas over many of these past years. He has also been a persistent prod to the Author to document some of these ideas in order to Make the Intuitively Obvious Understandable. The "Just-in-Time Subtraction" procedure divides a base-b number by b-1. The name was coined by Dylan Pocock, another of the Author's co-workers. To John Scholes I owe thanks for taking an interest in the JITS procedure and doggedly searching out its source -- and then taking an interest in the ideas (with clarifications) that led to such a scheme in the first place. ------------------------------------------------------------------------------- Comments: -------- The JITS procedure actually generates a complete and accurate division by b-1 without remainder -- provided that one properly handles bi-directionally infinite strings of digits (in some base b) as representations of rational numbers. In such a world there are multiple but equivalent representations of every rational number (both positive and negative), all of which are amenable to even simple pencil-and-paper calculation. The JITS procedure always generates a rational result without remainder but possibly in one of those equivalent representations. Concerning balanced ternary, one will undoubtedly notice that a simple test for evenness (and therefore integral divisibility by two) is just to sum the non-zero digits of the number (assuming RUs of zero), iteratively as needed ("casting out signs" is like "casting out nines" in base ten). Pre-rounding/truncating the number to induce evenness would eliminate the need for a post-adjustment of any non-integral division by two. It has been pointed out that the phrase "Replication (or Repetition) Unit" is somewhat ponderous; the terminology "Repetition Sequence" has been suggested as a possibly more appropriate replacement. The two terms "Replication" and "Unit" got into this fine mess during some of the Author's original doodling regarding representations of rational numbers; these terms have simply survived, but are mostly replaced by the somewhat semantically empty moniker "RU". The Author remains open to further suggestions. I originally thought of a continual carry to the left as somehow disappearing over the horizon ("To Infinity and Beyond!") so as to be out-of-sight and out-of-mind. And I always wanted to avoid invoking any notion of "end-around" carries in all contexts -- a notion that seemed to be expedient in many cases but which I felt obscured a more fundamental understanding of what was going on. All of this eventually got reduced to the "carry out what you carry in" maxim. An end-around carry, in any case, is merely a convenient fiction -- RU carries always originate at the low-order end, propagate through the RU, and then carry out of the high-order end (there's no "around" around here). If the carry-out differs from the carry-in, then the initially assumed carry-in is incorrect and the computation must be redone using the correct initial carry (which one can't actually know until the carry-out is known). I toyed with the idea of placing the initial (low-order) carry over the final delimiter of an RU but decided in the end (pun intended) that it really belongs in line with the (low-order) digit to which it applies. Similarly, the carry-out skips the leading non-digit punctuation and lines up with the digit to which it applies (the '=' or '#' being placed over the leading punctuation to indicate whether the carry-out equaled the carry-in or not). Additionally, I have come to think of the background and its reduction to a sea of '0's as being akin to the particle physicist's trick of renormalization to get rid of those "damned infinities" (as Richard Feynman referred to them). And if we cannot computationally reduce the background to zero but only to the complement of zero, then we are no worse off than computer scientists who do this all the time with their "high-order sign bit(s)". ------------------------------------------------------------------------------- Connections: ----------- I originally came to the problem of the continual carries (actually borrows) while working on the JITS procedure. But this ultimately seemed no more bizarre than the continual carries (of zero) that fundamentally happen for every addition/subtraction operation -- carries that as school children we were taught to ignore (if they were ever mentioned at all), but they are there nonetheless. The JITS procedure was trying to tell me something -- it certainly wasn't just random noise heading over the far horizon! And if it meant anything at all, it had to be a representation of the remainder, or something like that ... And the JITS procedure itself was only a consequence of considering what is often called the "Hailstone Problem": pick n > 0 and odd, multiply by three, add one, cast out all factors of two, cook 'til (d)one. It seemed obvious that patterns of numbers might be usefully investigated in base three in order to gain some insights -- but that division by two was just plain nasty! Hence JITS. The idea for JITS initially sprang from remembering an old (base ten) addition puzzle: SEND + MORE ----- MONEY The idea for the RU notation was unashamedly swiped from quantum mechanics (the "bra" and "ket" notation) where it is used for an entirely different purpose. The Middle Ages counting board (essentially a marked table top or "board") was a common piece of household furniture. Even after losing its markings, it is still commonly known as a "counter". A portable set of markings on a "checkered" cloth was popular with tax collectors who worked for the "exchequer". The word "xyzzy" comes from an early interactive fantasy role playing game called Adventure (written in Fortran as I recall); the word was (and I suppose still is) carved in stone and effected magical transport when uttered, er, typed. The fact that <xy|zz|y> is also my hat size I chalk up to the general perversity of Life, the Universe, and Everything -- but for that we really need <x|yyzx|x>. =============================================================================== Back to: →ratsum← See also: JitSub bt esh ary ratsum phinary fibonacci See also: eval.dws/notes.bta Back to: contents Back to: Workspaces