Since a few days I am fighting my way through implementing arithmetic coding. I found a really great source of information which made me understand how it should work. Long story short, it implements arithmetic coding on integers using two registers: HIGH and LOW. Those register store a fraction, ex. HIGH = 98765 //means 0.98765(9)LOW = 91234 // means 0.91234(0)Then comes magic, when the most significant numbers match (in this case it would be 9s) they are printed out. It's all clear to me.However, when we take the following example                         HIGH    LOW    RANGE   CUMULATIVE OUTPUTInitial state           99999  00000   100000Encode B (0.2-0.3)      29999  20000Shift out 2             99999  00000   100000    .2Encode I (0.5-0.6)      59999  50000             .2Shift out 5             99999  00000   100000    .25Encode L (0.6-0.8)      79999  60000   20000     .25 //here starts problemsEncode L (0.6-0.8)      75999  72000             .25 //how possible?Shift out 7             59999  20000   40000     .257Encode SPACE (0.0-0.1)  23999  20000             .257Shift out 2             39999  00000   40000     .2572Encode G (0.4-0.5)      19999  16000             .2572Shift out 1             99999  60000   40000     .25721Encode A (0.1-0.2)      67999  64000             .25721Shift out 6             79999  40000   40000     .257216Encode T (0.9-1.0)      79999  76000             .257216Shift out 7             99999  60000   40000     .2572167Encode E (0.3-0.4)      75999  72000             .2572167Shift out 7             59999  20000   40000     .25721677Encode S (0.8-0.9)      55999  52000             .25721677Shift out 5             59999  20000             .257216775Shift out 2                                      .2572167752Shift out 0                                      .25721677520I really don't know how the marked lines are achieved on computers, on paper it's easy, since:/*     range, HIGH, LOw - integer    symbol->high, symbol->low - real*/HIGH = HIGH - (range - symbol->high*range)LOW = LOW + range*symbol->lowBut on computers? The real-number inaccuracy comes in and my intervals are much different.[0; 99999)  100000  b   [0.2; 0.3)[20000; 29999)  100000  ===> 2[0; 99999)  100000  i   [0.5; 0.6)[50000; 59998)  100000  ===> 5 //inaccuracy[0; 99989)  99990   l   [0.6; 0.8)[59993; 79990)  19998   l   [0.6; 0.8)[71991; 75990)  19998   ===> 7[19910; 59909)  40000       [0; 0.1)[19910; 23908)  3999    g   [0.4; 0.5)[21509; 21908)  3999    ===> 2[15090; 19089)  3999    ===> 1[50900; 90899)  40000   a   [0.1; 0.2)[54900; 58898)  40000   ===> 5[49000; 88989)  39990   t   [0.9; 1)[84991; 88988)  39990   ===> 8[49910; 89889)  39980   e   [0.3; 0.4)[61904; 65900)  39980   ===> 6[19040; 59009)  39970   s   [0.8; 0.9)[51016; 55011)  39970   ===> 5zakodowano: 257215865I would appreciate any help.
Arithmetic coding issue
c++;coding
You shouldn't use floating point in such cases.Probabilities can be represented as rational numbers with denominator 10^something, this allows you to divide current interval exactly without rounding errors.So in your case 0.6 becomes 6/10, 0.8 - 8/10. How you will store such things is your choice. Usually some kind of fixed point format is used. For example you store 60 and know that this is actually probability*100, so whenever you multiply by it, you also divide by 100.Also note that later you will encounter another type of overflow - when you cannot shift out anything, but number of digits doesn't allow to divide interval without rounding errors. In such cases you either allow some inaccuracy in dividing interval or artificially narrow it to make shift out possible. If decode does everything in the same way, this doesn't impact correctness, but reduces compression a bit.