For pow(a,b), [a,b real numbers], you are essentially calculating:
a^b = (e^log(a))^b) or pow(pow(e, log(a)), b) which is e^(b*log(a)) or pow(e, b*log(a)) where e is the base of the natural logarithm.
What you have in your table are the values for e^x and log(x), like any good book of logarithms of ancient times. Precision according to your needs. For quick lookup you can even index the mantissa in a b-tree if your table is huge.
Then it becomes very quick:
step 1: look up log (a) in the table, interpolate if needed.
step 2: calculate b * (value in last step).
step 3: lookup up e^x where x is the value at step 2 in your table, interpolate if needed.
step 4: profit! as you now have your result.
And as a bonus, you are sure the result is within the precision of your table immediately, within the error of your interpolation.
Note that interpolation for exp(x) is quite fast. There are some exotic methods out there as well for interpolating exp(x) and log(x), as per this abstract which are quite efficient if you need high precision. For 10 digit precision you could easily fit both your tables into 8k.