Problem
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}
};Explanation
Position 0 is sin(0) = 0 and cos(0) = 1 for every pair: [0, 1, 0, 1]. Position 1 uses frequencies 1 and 1 / 10000^(2/4) = 0.01: [sin 1, cos 1, sin 0.01, cos 0.01] ≈ [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}
};Explanation
With one dimension only sin(pos) is used: [[0], [0.841471], [0.909297]].
How to approach it
Try on your own first, then open one hint at a time.
Hint 1
Each column belongs to a frequency pair, with even and odd dimensions using sine and cosine of the same angle.
Hint 2
Build the matrix by iterating positions and dimensions, computing the angle from the position and the dimension pair.
Hint 3
Be careful with integer division and zero-based indexing so the first row at position 0 becomes the expected starting pattern.
Expected complexity
O(length * d_model) time, O(length * d_model) extra space
References
This challenge is adapted for CodeUtility. Follow the statement and constraints above.