Efficient Symmetric level-index arithmetic in D?

[Michelle Long]

On Friday, 1 March 2019 at 15:02:04 UTC, Simen Kjærås wrote:
> On Friday, 1 March 2019 at 14:00:46 UTC, Olivier FAURE wrote:
>> On Wednesday, 27 February 2019 at 20:47:34 UTC, Michelle Long 
>> wrote:
>>> https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4927227/
>>> https://en.wikipedia.org/wiki/Symmetric_level-index_arithmetic
>>
>> tl;dr ?
>
> It's a different way of storing and operating on numbers, 
> essentially.
>
> For redonkulously humongous numbers, IEEE-754 is not good 
> enough. You know scientific notation? Imagine repeated 
> scientific notation: 10^10^...^10^10^A. By having A in [0, 1), 
> we don't need a number before the first 10 as we're used to, 
> and we'll just add more steps in the exponentiation tower to 
> get A small enough. For instance, 2 is 10^0.301. Also, since 
> we're mathy, we like using e instead of 10. It's more... 
> natural. :p
>
> So, the number 1234567 can be written as approximately 
> e^e^e^0.97113083, for 3 e's and a final exponent of 0.97113083. 
> Since the number of e's will always be a whole number, and the 
> exponent always positive and < 1, we can add them together as 
> φ(3.97113083).
>
> We can also introduce the sign bit back in, and have 
> -φ(3.97113083) represent the number -1234567.
>
> One problem now is we can only represent big numbers. We can 
> introduce another bit, called the reciprocal bit, to indicate 
> that a number is actually a reciprocal. Thus, -1/1234567 would 
> be -φ(3.97113083)^-1. And bingo, we can represent the whole 
> real number line.
>
> That sums up what SLI is, and sorta explains when it might be 
> useful. It might in fact be faster in silicon than regular 
> floating point, and so may be interesting for hardware 
> manufacturers. It is very unlikely that a software 
> implementation would be useful for normal numbers, but may 
> possibly be useful for some esoteric calculations, maybe.
>
> I'd never heard of it before, but found it an interesting idea, 
> like the unum format that has been posted here once or twice. 
> Interesting on a theoretical level, but probably not useful for 
> D.
>
> --
>   Simen

It's more than that. Because it can represent very small numbers 
to nearly arbitrary degree it stabilizes many algorithms that 
fail with FP.

With FP no value smaller than epsilon can be added and so an 
algorithm cannot produce any new output(same input same output). 
With SLI, one has a very small epsilon so very small values can 
be represented and these can produce new values.

e.g.,

suppose A is an algorithm and e is the epsilon:

A(x) = x + q

where q << e. For FP it then is 0 and so

A(x) = x

but with SLI q can be represented and is not 0! It can't be 
represented accurately but it can be represented and so A(x) != x 
unlike the FP case.

For unstable algorithms this can be enough to produce get 
somewhere.

The differential of SLI is nearly that of a true differential as 
compared to FP.

In FP, scaled for convenience, the differential is 1 and the next 
value is 1 more. In SLI the differential is 10^(-1000000) but the 
next value is 10^(-10000).

(so there is extreme inaccuracy but at least there is something 
there)

In fact, all computers should use SLI if the the performance can 
be had because one can make them almost as accurate as FP for 
most common values needed and extreme values solve a lot of 
problems that with FP one must increase the bits and modify the 
algorithm.