18 Sep
2009
18 Sep
'09
10:58 a.m.
Okay, let me try again, this time in ASCII only. First off, we change the associativity of ^ to match that of Knuth's arrow operator, which is to say that for the rest of this email, a^b^c = a^(b^c). We will also bind ^ more tightly than negation, so that -2^4 = -16 not +16. Second, I'll be using +/- as an ASCII version of the plus or minus symbol. With that out of the way, level index arithmetic writes numbers as +/- e^e^e^...^e^e^m where m is in [0,1). Specifically, you store the sign, the number of e's, and m, so that for example, -42 = -e^e^e^.276466... would be stored as (+, 3, .276466). Wikipedia has an article on a particular variant of level index arithmetic: http://en.wikipedia.org/wiki/Symmetric_level-index_arithmetic In the signed level index system, you write numbers as +/- 2 ^ +/- 2 ^ +/- 2 ^ ... Specifically, you just store the signs. Examples: infinity = +2 ^ +2 ^ +2 ^ ..., so we will write it as "+ + + + ..." -infinity = - + + + + + ... 0 = +2 ^ (-infinity) = + - + + + + + ... but also 0 = -2 ^ (-infinity) = - - + + + + + ... 1 = +2 ^ 0 = + + - + + + + + ... To convert a number to SLI form, just take it's sign, then repeat on log_2(|x|). When storing only a finite number of bits of a SLI, I recommend treating the remaining signs as all pluses, so that you can "exactly" represent 0, infinity, and other useful numbers. The following operations are trivial to compute on a number in SLI form: negation, log base 2, and 2^x. Comparison is also easy: + x > - y unless x = y = 0 + x > + y iff x > y - x > - y iff y > x where "+ x" is a pattern match for a SLI number that starts with + and follows with the sequence of signs x. If you are doing lots of comparisons, you might want to convert your SLI forms into an alternate form defined by: alt(+ x) = + alt(x) alt(- x) = - flip(alt(x)) where flip(+ x) = - flip(x) flip(- x) = + flip(x) Then x > y implies alt(x) > alt(y) in the lexicographic ordering with + > -. (There is still the issue of signed zeros here, but at least alt(+0) = + - - - - - - ... and alt(-0) = - + + + + + + ... have the decency to be adjacent). Finally, I would love people's ideas for an algorithm for adding two numbers in SLI form. If we could do addition, then multiplication would be easy, since (+/- 2^x) * (+/- 2^y) = +/- 2^(x+y). -Thomas C On Fri, Sep 18, 2009 at 11:59 AM, Henry Baker <hbaker1@pipeline.com> wrote: > Very cool! > > Your email formatting was a bit trashed, so I couldn't completely > understand your system. Perhaps you can try again (only ASCII characters) ? > > While it doesn't solve the "economical" range problem of the level/index > system, I keep coming back to the "asinh" representation (discussed here > before), which provides the "smoothness" missing from usual floating point > (see the American Scientist article), incorporates both the "exponent", > "mantissa" and "sign" smoothly into a single number, and provides for a > linear representation in the vicinity of zero. I believe that asinh > representation is now utilized for star magnitudes in star catalogs. > > At 08:38 AM 9/18/2009, Thomas Colthurst wrote: > >The latest American Scientist has a nice article about computer > arithmetic: > http://www.americanscientist.org/issues/id.7300,y.2009,no.5,content.true,page.1,css.print/issue.aspx > > > >One scheme that was new to me was level index arithmetic, in which numbers > are written as ± e↑e↑ … ↑e↑m where m is in [0,1). > > > >I've sometimes thought about a similar arrangement, which we might call > signed level index (SLI), in which numbers are written as ± 2 ↑ ± 2 ↑ ± 2 ↑ > ± 2 ↑ ... and the signs are what you store. > > > >For example, infinity = +2 ↑ +2 ↑ +2 ↑ +2 ↑ ... which I'll abbreviate as + > + + + + + ... . > > > >We then have - infinity = - + + + + + + ..., 0 = +2 ^(-infinity) = + - + + > + + + + ... and also -2 ^(-infinity) = - - + + + + + + ..., 1 = +2 ^ 0 = + + > - + + + + + ..., etc. > > > >Because of these examples, when using a finite number of bits to store a > SLI, I recommend treating all trailing signs as pluses -- for example, > interpret the eight signs + - + - + - + - as the infinite sequence + - + - + > - + - + + + + + + ... = 2 ^ -2 ^ 2 ^ -2 ^ 2 ^ -1 which is approximately > 0.406963. > > > >Converting a number to SLI is easy: just write down it's sign, then take > it's log base 2, then repeat. > > > >It is also trivial to negate a SLI, or take it's log base 2, or compute > 2^x. > > > >There is also a simple recursive algorithm for comparing two SLIs: + x > > - y unless x = y = 0 (but ignore the exception if you want signed 0s), > + x > +y iff x > y, and - x > - y iff y > x where I'm using "+ x" as a > pattern match for the SLI that starts with a + and has x as its subsequent > signs. > > > >Finally, if there was a good algorithm for SLI addition, there would be a > good algorithm for SLI multiplication, too, since (±2^x) * (±2^y) = ± 2 ^ > (x+y) . > > > >Sadly, I don't know of any good algorithms for SLI addition. > > > >Do you? > > > >-Thomas C > >