## digitalmars.D - Efficient Symmetric level-index arithmetic in D?

• Michelle Long (3/3) Feb 27 2019 https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4927227/
```https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4927227/
https://en.wikipedia.org/wiki/Symmetric_level-index_arithmetic

It would be worth while to have something like this in D!
```
Feb 27 2019
```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 ?
```
Mar 01 2019
```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 ?

Uses tetration to represent very small and large numbers(much
larger and smaller than anyone can use). This improves the
accuracy of many algorithms since it can represent these large
numbers well enough to do computations on them. The first link
shows some examples with how much better it works than floating
point.

e^e^...^e^(frac(x))

where the iteration occurs floor(x) times.

the integer part of x is called the level and controls
essentially how large the number is. For even a few levels the
values are astronomical or infinitesimal.

It's really not much different than FP except instead of a fixed
base, the base is a tetrated base so it allows for much larger
values to be expressed. The cost of course is resolution at those
large values, but generally it is not a problem since we
generally only care about the most significant terms.

E.g., a FP value uniformly partitions between min and max. A SLI
value uses less resolution near the extremes but uses it to allow
for much larger values.

It's more suited for certain problems that can become unstable.
Because essentially inside the algorithm it will tetrate values
and produce very large/small values that are not representable
using FP and hence will fail, but with SLI one can represent
those values.

What makes it useful is that it offers very small values. These
values allow for building a representation that is far more
accurate than can be achieved with FP.

E.g., with FP one has a minimal division. One cannot achieve any
better accuracy because one cannot get any more precise.

With SLI one has very small values available to represent far
more precision(but the error between values is larger). What
makes it different is that these small differences are incoherent
and sorta provide noise for algorithms that help them converge
faster. With FP one is stuck with a fixed minimum and if an
algorithm gets in a "cycle" on it then it will not be able to
escape. With tet's one can get smaller values and it will escape
the cycle(as if adding some more precise noise to the value).

If, say, the minimum precision is 1 and an algorithm is something
like x = 1 - x^2 then all we can get is 0 and 1. If though we can
represent smaller values like, say 1/2, then we can get a value
of 3/4 and then that now escapes the algorithm producing other
values. With floating point it is impossible to get any lower but
with tet's one can easily represent values that are smaller than
anything achievable in the universe without much cost.

It's ultimately just using a non-uniform scaling to get some very
small and very large values in a nice way that can't be done with
uniform scaling and that then helps with some problems that need
to have better precision in the extremes. It then simplifies
having to deal with those problems by using more complicated
algorithms.
```
Mar 01 2019
```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
```
Mar 01 2019
```On Friday, 1 March 2019 at 15:02:04 UTC, Simen Kjærås wrote:
It is very unlikely that a software implementation would be
useful for normal numbers, but may possibly be useful for some
esoteric calculations, maybe.

For an example of when such a representation may be useful,
Numberphile had a video on the number 10^10^10^10^10^1.1:

https://youtu.be/1GCf29FPM4k

To give an idea of the accuracy of the calculations for this kind
of number, the units for that number, in a scientific paper, is
given as 'Planck times, millennia, or whatever'. A factor of
10^55 is inconsequential here. That would never be the case for
floating points numbers, where the accuracy is always a certain
percentage of the absolute value.

--
Simen
```
Mar 01 2019
```On Fri, Mar 01, 2019 at 03:12:15PM +0000, Simen Kj�r�s via Digitalmars-d wrote:
On Friday, 1 March 2019 at 15:02:04 UTC, Simen Kj�r�s wrote:
It is very unlikely that a software implementation would be useful
for normal numbers, but may possibly be useful for some esoteric
calculations, maybe.

For an example of when such a representation may be useful, Numberphile had
a video on the number 10^10^10^10^10^1.1:

https://youtu.be/1GCf29FPM4k

That's a pretty "small" number in the grand scheme of things. Look up
Graham's number, for example, and be boggled at how many times it
explodes your mental visualization of "infinity" and yet it's still
*finite*. :-D (And if it doesn't cause your brain to explode many times
over, you haven't truly appreciated how huge it is -- read it again.
:-P)

And BTW, Graham's number G is beyond even the reach of SIL -- many
orders of representation beyond. (Yes I said "orders of representation"
rather than "orders of magnitude": orders of magnitude are
insignificant(!) when talking about such huge numbers!) It's so big that
the difference between G, factorial(G), and e^G is basically
indiscernible -- i.e., these operations don't significantly change its
general magnitude such that we can meaningfully tell them apart. They're
mathematically different, certainly, but that difference is miniscule
(indeed, indiscernible) compared to the general, unimaginably humongous
magnitude that they all lie in.

To give an idea of the accuracy of the calculations for this kind of
number, the units for that number, in a scientific paper, is given as
'Planck times, millennia, or whatever'. A factor of 10^55 is
inconsequential here. That would never be the case for floating points
numbers, where the accuracy is always a certain percentage of the
absolute value.

[...]

Yes. When you're dealing with numbers of the magnitude of Ackermann's
function of Graham's number, a difference of 10^55 is not even on the
radar, it's basically non-existent. "Roundoff error" would be the
understatement of the millenium (or several millenia!). :-D

T

--
"No, John.  I want formats that are actually useful, rather than over-featured
megaliths that address all questions by piling on ridiculous internal links in
forms which are hideously over-complex." -- Simon St. Laurent on xml-dev
```
Mar 01 2019
```On Fri, Mar 01, 2019 at 03:02:04PM +0000, Simen Kj�r�s via Digitalmars-d 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.

[...]
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.

[...]

I've encountered such number representations before, in the form of a
Perl script called hypercalc.pl that, paraphrasing the author, allows
you to compute the factorial of the US national debt raised to the power
of the number of atoms in the universe, and make meaningful comparisons
of the result with other humongous numbers.

I've never heard of such a representation being useful outside of pure
mathematical curiosity, though.  For one thing, it (greatly!) expands
the range of representible numbers by (greatly!) diminishing accuracy. A
number like e^e^e^...(n times)..^x has an error margin of roughly
e^e^... (n-1 times), which for any non-trivial values of n is pretty
huge. e^e^1, for example, is "only" around 15, but e^e^e^1 is around
3814279.10476. So e^e^e^e^x has a really big margin of error, and that's
only for n=4. For large values of n, the error is so large it doesn't
even fit in IEEE 754 double(!).  This inaccuracy is most obvious when
subtracting values of equal (or almost equal) magnitude.  Because of the
inherent inaccuracy in the representation, it's often not possible to
tell whether the result of a subtraction is 0, or some number on the
order of magnitude of e^e^...(n-k times)...^x for some small k, which,
for large n, can be so huge you can't even represent it in a IEEE
double. So while inequalities generally work fine, equality is in
general not a very meaningful operation with this representation (except
for exact equality, which in real computations rarely ever happens).

So I don't think such a representation has general applicability in
terms of computations most people would be working with, as opposed to
specialized applications that primarily deal with humongous numbers (or
near-infinitesimal numbers).

T

--
Freedom: (n.) Man's self-given right to be enslaved by his own depravity.
```
Mar 01 2019
```On Friday, 1 March 2019 at 15:35:33 UTC, H. S. Teoh wrote:
On Fri, Mar 01, 2019 at 03:02:04PM +0000, Simen Kjærås via
Digitalmars-d 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.

[...]
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.

[...]

I've encountered such number representations before, in the
form of a Perl script called hypercalc.pl that, paraphrasing
the author, allows you to compute the factorial of the US
national debt raised to the power of the number of atoms in the
universe, and make meaningful comparisons of the result with
other humongous numbers.

I've never heard of such a representation being useful outside
of pure mathematical curiosity, though.  For one thing, it
(greatly!) expands the range of representible numbers by
(greatly!) diminishing accuracy. A number like e^e^e^...(n
times)..^x has an error margin of roughly e^e^... (n-1 times),
which for any non-trivial values of n is pretty huge. e^e^1,
for example, is "only" around 15, but e^e^e^1 is around
3814279.10476. So e^e^e^e^x has a really big margin of error,
and that's only for n=4. For large values of n, the error is so
large it doesn't even fit in IEEE 754 double(!).  This
inaccuracy is most obvious when subtracting values of equal (or
almost equal) magnitude.  Because of the inherent inaccuracy in
the representation, it's often not possible to tell whether the
result of a subtraction is 0, or some number on the order of
magnitude of e^e^...(n-k times)...^x for some small k, which,
for large n, can be so huge you can't even represent it in a
IEEE double. So while inequalities generally work fine,
equality is in general not a very meaningful operation with
this representation (except for exact equality, which in real
computations rarely ever happens).

So I don't think such a representation has general
applicability in terms of computations most people would be
working with, as opposed to specialized applications that
primarily deal with humongous numbers (or near-infinitesimal
numbers).

It is no worse than FP. In the range of -1..1 it is FP minus a
few bits so whatever issues it has FP will have and vice versa.

It uses those few bits to add very large and small representable
numbers(it approximates infinity and the differential very well).

These benefits is that MANY scientific algorithms can stall on
certain points because the algorithm itself cannot represent the
values it needs to move beyond them.

With SLI one can represent them and so the algorithm can actually
produce a new value that would not be possible otherwise.

With FP essentially one gets 0 for any value < e. With SLI one
can get far closer. So it works well for unstable problems such
as matrices with determinants near 0, and other numerically
unstable problems which are in fact common.

Here is a trivial algorithm that values with FP but passes with
SLI:

A(x) = { A(x/1.5) if x >= fp.e, else 0}

Then for x = 1,

A(x) = x/1.5^n for some n.

Now, we know this is 0 in the limit, but eventually the fp will
not be able to produce anything below fp.e and the algorithm will
end up in an infinite loop.

With SLI, the value will be representable for some n, although
highly inaccurately, and so will will actually produce a value of
eventually 0.

Of course, it's as if we are just using a much larger
epsilon(Whatever the "epsilon" for SLI is)... but that is the
point. We get the ability to represent very small changes that
some algorithms require to be stable even though we cannot
represent small values precisely. Sometimes the precision is not
as important because it's already precise beyond what we need.

In fact, the above algorithm sort of shows it. For fp the
algorithm will always be unstable but for SLI the algorithm will
pass even though we will have less precision(since some bits
would be used for the tetration).

The first link I gave demonstrate this problem for some PDE's.

Essentially it is "shaping" the FP's in such a way that we
sacrifice some of the bits to represent extremes. In FP these
extremes are impossible and in many problems are not needed, but
in some problems they are and if one doesn't have them the
problem cannot be solved correctly.
```
Mar 01 2019    Michelle Long <HappyDance321 gmail.com> writes:
```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.
```
Mar 01 2019