www.digitalmars.com         C & C++   DMDScript  

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

reply Michelle Long <HappyDance321 gmail.com> writes:
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
parent reply Olivier FAURE <couteaubleu gmail.com> writes:
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
next sibling parent Michelle Long <HappyDance321 gmail.com> writes:
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
prev sibling parent reply Simen =?UTF-8?B?S2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:
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
next sibling parent reply Simen =?UTF-8?B?S2rDpnLDpXM=?= <simen.kjaras gmail.com> writes:
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
parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
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
prev sibling next sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
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
parent Michelle Long <HappyDance321 gmail.com> writes:
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
prev sibling parent 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