Return to Answer

org_value = (int) exp(stored_value / constant) + 0.5)

 Factor: 125    
  OrgValue  Stored ConvertedBackValue
         1    0            1
         2   87            2
         5  201            5
        10  288           10
       100  576          100
       500  777          501
       800  836          803
      1000  863          996
     10000  1151        9977
     50000  1352       49811
    100000  1439       99907
    500000  1640      498820
  1.00E+06  1727     1000490
  1.00E+07  2015    10019062 

org_value = (int) (exp(stored_value / constant) + 0.5)

 Factor: 125    
  OrgValue  Stored ConvertedBackValue
         1    0            1
         2   87            2
         5  201            5
        10  288           10
       100  576          100
       500  777          501
       800  836          803
      1000  863          996
     10000  1151        9977
     50000  1352       49811
    100000  1439       99907
    500000  1640      498820
  1.00E+06  1727     1000490
  1.00E+07  2015    10019062 

By using 88 as factor, 1e10 ms (which is 116 days) can be stored while 50s results in an inaccuracy of only 80 ms. See the table below.

Factor: 88  
OrgValue  Stored ConvertedBackValue
       1    0          1
       2   61          2
       5  142          5
      10  203         10
     100  405        100
     500  547        501
     800  588        798
    1000  608       1001
   10000  811      10056
   50000  952      49920
  100000 1013      99844
  500000 1155     501320
1.00E+06 1216    1002675
1.00E+07 1418    9955506
1.00E+08 1621   99977383
1.00E+09 1824 1004014929
1.00E+10 2026 9968812163

Update:

Edgar Bonnet's idea brought me on the idea to use a logarithmic formula:

Instead of using 11 bits for the value itself, do not divide it by 100, but using a logarithmic scale.

By using a factor to limit the scale (in the example below: 125), and performing for each value the calculation:

stored_value = (int) (ln(value) * factor + 0.5)

And by converting back:

org_value = (int) exp(stored_value / constant) + 0.5)

Below a table is shown with some example values.

The advantage is that the decrease of accuracy is now very gradually. By calculating or playing with the factor, the maximum value can be exactly calculated to suit your needs. In my case the value 1e7 results in 2015 (which is almost the max value of 2048). 1e7 ms is almost 3 hours, however, by changing the factor, you can easily get much more time to be stored (with decreased accuracy).

Of course this method needs some more computing power.

 Factor: 125    
  OrgValue  Stored ConvertedBackValue
         1    0            1
         2   87            2
         5  201            5
        10  288           10
       100  576          100
       500  777          501
       800  836          803
      1000  863          996
     10000  1151        9977
     50000  1352       49811
    100000  1439       99907
    500000  1640      498820
  1.00E+06  1727     1000490
  1.00E+07  2015    10019062 

You already tried to minimize some memory by reducing accuracy. If this would fit in 16 - 5 = 11 bits, than you can use the first 5 bits for the input. With 11 bits you have a range of 2048, so you have to divide your values (upto let's say 32768) by 16. Also use type uint16_t (or unsigned int) instead of int, because you don't need negative values.

This way you will need 200 (max records) * 2 = 400 bytes.

Assuming the array will be

uint16_t times[max_record];

Than the input is

ubyte input = (times[record_index] & 0xF8) >> 11;
uint16_t time = (times[record_index] & 0x7F);

You already tried to minimize some memory by reducing accuracy. 

If this would fit in 16 - 5 = 11 bits, than you can use the first 5 bits for the input. 

With 11 bits (left) you have a range of 2048. Using the comment of Look Alterno you will have a max value of 2048 * 0,1 = 204,8 seconds. 

Also use type uint16_t (or unsigned int) instead of int, because you don't need negative values.

This way you will need 200 (max records) * 2 = 400 bytes.

Assuming the array will be

uint16_t times[max_record];

Than the input is

ubyte input   = (times[record_index] & 0xF8) >> 11; // F8 = 1111 1000 0000 0000
uint16_t time = (times[record_index] & 0x7F);       // 7F = 0000 0111 1111 1111