I realize that you're going at this from a clean room approach, but there is a lot to be learned from looking at some of the reference implementations of Perlin noise ( http://mrl.nyu.edu/~perlin/noise/ is his 2002 noise function implemented in Java; a few minutes shopping on the Perlin Noise Wikipedia page will also pay off handsomely ).

Also, when summing octaves of perlin noise, I strongly recommend not having an exact integer distance between octaves because any discontinuities that show at lattice points will be amplified. This sort of thing is usually only an issue for smoothing functions that aren't second-derivative continuous like the original Perlin noise (improved Perlin noise uses a quintic function that's smooth in its first and second derivatives).

On the interpolation subject, linear is 1D, order 1; bilinear is 2D, order 1; quadratic is 1D, order 2; biquadratic is 2D, order 2; cubic is 1D, order 3, bicubic is 2D, order 3; so on and so on. You'll need order + 1 points for each dimension of the interpolation (1D linear needs 2, quadratic needs 3, cubic needs 4, quartic needs 5, etc.; 2D linear needs 4, quadratic needs 9, cubic needs 16, etc.)