An adaptive predistorter for applying a predistortion gain to an input signal to be amplified by a power amplifier having a variable supply voltage, the predistorter including: a predistortion gain block adapted to apply a complex gain to a complex input signal; a first table implemented in a first memory and including a 2-dimensional array of cells storing complex gain values, the first table adapted to output the complex gain values based on an amplitude of the input signal and the value of the variable supply voltage of the power amplifier; and a second table implemented in a second memory and including a 2-dimensional array of cells storing gain update values for updating the complex gain values of the first table, the gain update values being generated based on an output of the power amplifier.