Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I think I've mentioned sometime before about logarithmic number system. In this system, a real number $r$ is represented by $(\text{sgn}(r), \log|r|) \in \{-1, 0, 1\} \times \mathbb R$. If $\mathbb R$ is represented in computer by a floating point number system, this logarithmic number system would be able to capture a lot more numbers near $0$. Of course, its capability diminishes faster than regular floating point as the number gets larger, but it is much better when dealing with numbers very close to 0, like probabilities.

One good thing about this logarithmic number system is that multiplication and division are super easy, while addition and subtraction get a bit more complicated. It's still doable though.

But as I mentioned the use in representing probabilities, the logarithmic number system does not use the whole range of the underlying floating point system to represent numbers in [0, 1]. Can I make a system that makes better use of the underlying real representation to represent numbers in [0, 1]? Of course there are infinitely many surjections $\mathbb R \to [0, 1]$, but basic operations don't seem to carry out as nicely.

For example, if I use the logistic function as a mapping, I can represent $A \in (0, 1)$ as

$$ A = \frac 1{1 + e^{-a}} $$

where $a \in \mathbb R$. Addition is more complicated but doable:

$$ A + B = \frac 1{1 + e^{-a}} + \frac 1{1 + e^{-b}} = \frac 1{1 + e^{-c}} $$ where $$ c = -\log(e^{-(a + b)} - 1) + \log((1 + e^{-a}) + (1 + e^{-b})). $$ (If my math is correct.) So if there's an efficient way to compute $\log(e^{-x} - 1)$ and $\log(2 + e^{-x} + e^{-y})$, we can implement addition for this "logistic number system". Multiplication seems simple too: $$ AB = \frac{1}{(1 + e^{-a})(1 + e^{-b})} = \frac 1{1 + e^{-c}} $$ where $$ c = a + b - \log(1 + e^a + e^b) $$ (Again, if my math is correct.) I have not worked out other operations, but I assume they're not too terrible. One nice property we get from this logistic number system is that complement $B = 1 - A$ is easy to compute. Just set $b = -a$.

Ok, I admit that was a pretty long example. Here comes my question. Do you think there are other interesting number systems that might be of practical use? I am not talking about bignum arbitrary precision because that's like an overkill. I'm more interested in more efficient ways to represent numbers for specific applications. The domain is the important thing.

What's available:

$\mathbb R \to \mathbb R$: $x \mapsto x$

$\mathbb R \to (0, \infty)$: $x \mapsto e^x$

What I think may be interesting to explore:

$\mathbb R \to (0, 1)$: $x \mapsto \frac{1}{1 + e^{-x}}$

$\mathbb R \to (-1, 1)$: $x \mapsto \tanh x$

I would really appreciate if you help me work out the details or provide me with information on existing systems or suggest other interesting choices or provide me with reasons not to pursue this any further.

share|improve this question
    
I don't think "number system" is a good term for what you're trying to describe; when I hear this term I think something like $\mathbb{Q}$ or $\mathbb{R}$ or $\mathbb{C}$ (that is, a collection of numbers, independent of a particular computational description of those numbers). Anyway, this strikes me as a little vague. Can you ask a more precise question? –  Qiaochu Yuan Aug 23 '12 at 3:30
1  
You might be interested in the "level-index system" discussed at bit-player.org/2009/outnumbered –  Gerry Myerson Aug 23 '12 at 3:54
    
@QiaochuYuan I thought there was no definite definition of "Number System" so I used it to agree with "Logarithmic Number System". The link that Gerry posted also uses the term system. Anyway, I am open for suggestion :) I may edit the title a little for better understanding. I don't know how to make the question clearer. I am asking if you've seen or have ideas on other interesting representations of subsets of the real numbers that might be useful to study. (Actually Gerry gave one.) –  Tunococ Aug 23 '12 at 6:15
    
I did some search on the term "SLI arithmetic" and found that there are some people working on this level-index arithmetic. From what I've seen, they are willing to sacrifice more computational time for basic operations than I thought. Maybe the logistic and $\tanh$ systems are not that bad to consider... –  Tunococ Aug 23 '12 at 6:31
add comment

2 Answers

I think I've used $\tanh$ in this sort of way before! The reason wasn't because of general principle, but because for the specific thing I was computing, storing $\tanh x$ instead of $x$ made the individual calculations easier. (I can't give the details because I don't remember them anymore!)

Have you seen Zech logarithms before? It doesn't have anything to do with real numbers: it's a way to do calculation in finite fields. But it's a pretty neat one. There's a real number analog of it which has apparently had applications. I don't remember the details, but I think it was slightly different than yours.

share|improve this answer
    
No I have not seen it before. Thank you for showing me that :) –  Tunococ Aug 23 '12 at 6:20
add comment

One obvious choice would be to use the logarithm of the odds: $$\mathrm{rep}(p) = \ln\frac{p}{1-p}$$ Since $p\in [0,1]$, $\frac{p}{1-p}\in[0,\infty]$ and thus $\ln\frac{p}{1-p}\in[-\infty,\infty]$. Note that IEEE floating point numbers contain representations of $\pm\infty$, so probabilities of $0$ and $1$ are no problem.

One nice property of this representation is that it is symmetric: $\mathrm{rep}(1-p) = -\mathrm{rep}(p)$. However, it certainly doesn't simplify calculations.

On the other hand, very small probabilities are generally not significant anyway, therefore I'd say the best representation for probabilities is fixed point arithmetics, where an integer $k\in\{0,\dots,n\}$ represents the value $p = k/n$. This is trivial to add, very simple to multiply, and has the added bonus that most programming languages already offer unsigned integer types (with $n=2^k-1$ where typically $k=2^m$ with $m\ge 3$).

share|improve this answer
    
There are cases small probabilities matter. For example, in a usual Baum-Welch algorithm implementation, probabilities at each step need to be scaled to avoid underflow. If we use the logarithmic (or other) number system, scaling would be unnecessary. BTW, thank you for letting me know that there are some people interested in this thing :D (Your suggestion is the same as the logistic system I mentioned though.) –  Tunococ Aug 24 '12 at 0:24
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.