An arithmetic encoder for encoding a plurality of symbols having symbol values to derive an interval size information for an arithmetic encoding of one or more symbol values to be encoded based on a plurality of state variable values representing statistics of a plurality of previously encoded symbol values with different adaptation time constants. The arithmetic encoder maps a first state variable value, or a scaled and/or rounded version thereof, using a lookup-table and maps a second state variable value, or a scaled and/or rounded version thereof using the lookup-table, to obtain the interval size information describing an interval size for the arithmetic encoding of one or more symbols to be encoded. Further arithmetic encoders, arithmetic decoders, video encoders, video decoder, methods for encoding, methods for decoding and computer programs are also disclosed.