Interpolation can be effective done in transformed space if gradient table has entries in the same space.
Squared distance in such transformed space can be computed with following formula (3D case):
r2 = Vx\\^2 + Vy\\^2 + Vz\\^2 - g*(Vx + Vy + Vz)\\^2
g = (1 - a\\^2)/n, a -- scaling factor along main diagonal, n = 3
Full noise can be computed effectively with following algorithm.
Consider B, B, B -- fractional part of the transformed coordinates and K, K, K -- corresponding indexes.
First, determine order of the values in B, say I -- index of the smallest, I -- middle and I -- largest value from array.
This step effectively is choosing correct simplex from hypercube.
Second, calculate start squared distance
R2 = B\\^2 + B\\^2 + B\\^2 - g*(B + B + B)\\^2,
C = 2*g*(B + B + B) - g + 1.
Use this values for the first contribution to final result
Z = F(R2) * (grad[K] * B).
Then iterate, i = 0..n-1.
R2 += C - 2*B[I], C -= 2*g,
K[I]++, B[I] -= 1,
Z += F(R2) * (grad[K] * B).
I think this implementation can be quite fast even in large dimension case.