A predistorters for use with a nonlinear element and methods of predistorting for a nonlinear element for use in a 3G, e.g., WCDMA transmitter. In one embodiment, the predistorter includes: (1) a lookup table having non-uniformly spaced entries therein, (2) a compander configured to compand an input signal based on a nonlinearity of the nonlinear element to address the entries and (3) an interpolation offset calculation circuit associated with the lookup table and configured to produce an output based on a value of the input signal and a linear interpolation involving at least two entries from the lookup table.