Sinusoidal Positional Encoding

Attention ignores word order, so the original Transformer adds a positional encoding to each token embedding. For position pos and dimension j (both starting at 0) in a model of size d_model:

• even j: PE[pos][j] = sin(pos / 10000^(j / d_model))
• odd j: PE[pos][j] = cos(pos / 10000^((j - 1) / d_model))

So dimensions 0 and 1 share one frequency, dimensions 2 and 3 the next, and so on.

Implement positional_encoding(length, d_model).

Input

length: The number of positions (0 to length - 1).

d_model: The embedding size.

Output

Return a length × d_model matrix.

Constraints

1 ≤ length ≤ 200, 1 ≤ d_model ≤ 128

Examples

Input:
length = 2
d_model = 4

Expected output:
expected = [
    [0.0, 1.0, 0.0, 1.0],
    [0.841471, 0.540302, 0.01, 0.99995]
]

Input:
long long length = 2;
long long d_model = 4;

Expected output:
std::vector<std::vector<double>> expected = {
    {0.0, 1.0, 0.0, 1.0},
    {0.841471, 0.540302, 0.01, 0.99995}
};

Input:
long length = 2;
long d_model = 4;

Expected output:
double[][] expected = new double[][] {
    new double[] {0.0, 1.0, 0.0, 1.0},
    new double[] {0.841471, 0.540302, 0.01, 0.99995}
};

Input:
length = 3
d_model = 1

Expected output:
expected = [
    [0.0],
    [0.841471],
    [0.909297]
]

Input:
long long length = 3;
long long d_model = 1;

Expected output:
std::vector<std::vector<double>> expected = {
    {0.0},
    {0.841471},
    {0.909297}
};

Input:
long length = 3;
long d_model = 1;

Expected output:
double[][] expected = new double[][] {
    new double[] {0.0},
    new double[] {0.841471},
    new double[] {0.909297}
};

References

This challenge is adapted for CodeUtility. Follow the statement and constraints above.

• Vaswani et al., Attention Is All You Need
• Jay Alammar, The Illustrated Transformer