Challenge
I've checked that there is a question Compute the Discrete Cosine Transform which is a competition for implementing a shortest solution to compute the one dimensional discrete cosine transform.
The goal of this challenge is to implement a program to calculate three dimensional discrete cosine transform which makes processing time as short as possible.
The formula of 3D Discrete Cosine Transform is as below.
Considering the different size case in three dimension.
About the accuracy requirement in this challenge, you need to perform the calculation based on double precision floating point.
Example Input / Output for Performance Evaluation
Because it is 3D numerical data input / output in this challenge, the structure of input / output data in example is as below.
- N = 8 :
x(0, 0, 0) x(0, 0, 1) x(0, 0, 2) x(0, 0, 3) x(0, 0, 4) x(0, 0, 5) x(0, 0, 6) x(0, 0, 7)
x(0, 1, 0) x(0, 1, 1) x(0, 1, 2) x(0, 1, 3) x(0, 1, 4) x(0, 1, 5) x(0, 1, 6) x(0, 1, 7)
...
x(0, 7, 0) x(0, 7, 1) x(0, 7, 2) x(0, 7, 3) x(0, 7, 4) x(0, 7, 5) x(0, 7, 6) x(0, 7, 7)
x(1, 0, 0) x(1, 0, 1) x(1, 0, 2) x(1, 0, 3) x(1, 0, 4) x(1, 0, 5) x(1, 0, 6) x(1, 0, 7)
x(1, 1, 0) x(1, 1, 1) x(1, 1, 2) x(1, 1, 3) x(1, 1, 4) x(1, 1, 5) x(1, 1, 6) x(1, 1, 7)
...
x(1, 7, 0) x(1, 7, 1) x(1, 7, 2) x(1, 7, 3) x(1, 7, 4) x(1, 7, 5) x(1, 7, 6) x(1, 7, 7)
x(7, 0, 0) x(7, 0, 1) x(7, 0, 2) x(7, 0, 3) x(7, 0, 4) x(7, 0, 5) x(7, 0, 6) x(7, 0, 7)
x(7, 1, 0) x(7, 1, 1) x(7, 1, 2) x(7, 1, 3) x(7, 1, 4) x(7, 1, 5) x(7, 1, 6) x(7, 1, 7)
...
x(7, 7, 0) x(7, 7, 1) x(7, 7, 2) x(7, 7, 3) x(7, 7, 4) x(7, 7, 5) x(7, 7, 6) x(7, 7, 7)
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
255 255 255 255 255 255 255 255
255 255 255 255 255 255 255 255
255 255 255 255 255 255 255 255
255 255 255 255 255 255 255 255
255 255 255 255 255 255 255 255
255 255 255 255 255 255 255 255
255 255 255 255 255 255 255 255
255 255 255 255 255 255 255 255
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
255 255 255 255 255 255 255 255
255 255 255 255 255 255 255 255
255 255 255 255 255 255 255 255
255 255 255 255 255 255 255 255
255 255 255 255 255 255 255 255
255 255 255 255 255 255 255 255
255 255 255 255 255 255 255 255
255 255 255 255 255 255 255 255
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
255 255 255 255 255 255 255 255
255 255 255 255 255 255 255 255
255 255 255 255 255 255 255 255
255 255 255 255 255 255 255 255
255 255 255 255 255 255 255 255
255 255 255 255 255 255 255 255
255 255 255 255 255 255 255 255
255 255 255 255 255 255 255 255
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
255 255 255 255 255 255 255 255
255 255 255 255 255 255 255 255
255 255 255 255 255 255 255 255
255 255 255 255 255 255 255 255
255 255 255 255 255 255 255 255
255 255 255 255 255 255 255 255
255 255 255 255 255 255 255 255
255 255 255 255 255 255 255 255
360.624 2.81997e-14 -2.88658e-14 4.24105e-14 1.42109e-14 -2.84217e-14 -2.77001e-13 4.26437e-13
3.10862e-15 3.14018e-16 6.28037e-16 2.51215e-15 0 -1.25607e-15 1.57009e-16 -1.17757e-15
-1.46549e-14 9.42055e-15 -3.14018e-16 2.19813e-15 -2.19813e-15 -3.14018e-16 1.25607e-15 1.17757e-15
7.10543e-14 -9.42055e-16 5.0243e-15 -3.14018e-16 0 2.51215e-15 2.51215e-15 1.25607e-15
2.13163e-14 6.28037e-16 -5.0243e-15 0 -2.51215e-15 -1.09906e-15 0 -1.41308e-15
-5.01821e-14 -5.65233e-15 4.71028e-15 2.82617e-15 -1.57009e-16 -5.0243e-15 1.17757e-15 -1.13832e-15
-2.6934e-13 -4.39626e-15 5.49532e-15 1.57009e-16 0 1.09906e-15 2.51215e-15 -1.25607e-15
4.39315e-13 1.33458e-15 9.42055e-16 2.51215e-15 -1.02056e-15 -1.41308e-15 -2.74766e-16 -3.76822e-15
-64.9989 -7.22243e-15 8.79252e-15 -2.51215e-15 -1.25607e-15 5.65233e-15 5.66803e-14 -7.87401e-14
-6.28037e-15 -3.55271e-15 -8.88178e-16 8.88178e-16 8.88178e-16 -8.88178e-16 -1.33227e-15 -6.66134e-16
3.51701e-14 1.77636e-15 4.44089e-16 -2.66454e-15 4.44089e-16 8.88178e-16 2.22045e-16 3.33067e-16
2.07252e-14 0 -4.44089e-15 2.22045e-15 4.44089e-16 0 -1.77636e-15 0
0 1.77636e-15 1.33227e-15 1.33227e-15 -8.88178e-16 -2.22045e-16 -1.33227e-15 4.44089e-16
1.00486e-14 1.77636e-15 -8.88178e-16 1.33227e-15 -1.11022e-15 2.22045e-16 0 -7.21645e-16
5.80934e-14 -1.33227e-15 -1.77636e-15 -1.9984e-15 0 -1.11022e-16 -9.99201e-16 8.32667e-16
-7.96037e-14 1.33227e-15 3.33067e-15 -7.77156e-16 1.11022e-16 4.44089e-16 1.38778e-15 -9.71445e-16
-4.74731e-13 -6.28037e-16 3.14018e-16 4.71028e-15 -3.76822e-15 -3.76822e-15 3.14018e-15 3.68972e-15
-4.52187e-14 3.55271e-15 8.88178e-16 -4.44089e-16 -8.88178e-16 0 0 -3.33067e-16
4.39626e-15 4.88498e-15 -1.33227e-15 8.88178e-16 0 2.22045e-16 -4.44089e-16 -1.88738e-15
8.16448e-15 1.77636e-15 -1.77636e-15 8.88178e-16 -8.88178e-16 1.77636e-15 -2.22045e-16 7.77156e-16
6.28037e-16 -1.77636e-15 -1.33227e-15 0 0 -8.88178e-16 -1.44329e-15 1.88738e-15
-1.25607e-14 -8.88178e-16 3.77476e-15 1.9984e-15 -6.66134e-16 4.44089e-16 2.22045e-15 7.21645e-16
1.57009e-15 4.88498e-15 -2.22045e-16 1.33227e-15 -9.99201e-16 3.33067e-16 -1.44329e-15 -2.22045e-16
4.71028e-16 4.21885e-15 6.66134e-16 3.33067e-16 1.66533e-15 -5.55112e-17 2.77556e-16 -6.93889e-16
-76.6715 2.82617e-15 1.19327e-14 -5.96635e-15 -3.76822e-15 6.90841e-15 5.95065e-14 -8.98093e-14
-3.14018e-14 2.22045e-15 -1.33227e-15 -4.44089e-16 0 8.88178e-16 -2.22045e-16 6.66134e-16
2.51215e-14 -4.44089e-16 1.77636e-15 4.44089e-16 0 6.66134e-16 -2.22045e-16 -5.55112e-16
-3.57981e-14 4.44089e-16 -2.66454e-15 -4.44089e-16 8.88178e-16 0 -1.55431e-15 0
-8.16448e-15 1.33227e-15 0 1.55431e-15 1.55431e-15 -8.88178e-16 -4.44089e-16 -4.44089e-16
1.31888e-14 3.10862e-15 -1.11022e-15 -8.88178e-16 6.66134e-16 1.77636e-15 5.55112e-16 -1.4988e-15
5.68373e-14 0 4.66294e-15 -1.9984e-15 1.11022e-16 2.22045e-16 7.21645e-16 6.10623e-16
-8.79252e-14 -2.22045e-16 7.77156e-16 9.99201e-16 -5.55112e-16 -1.11022e-15 1.83187e-15 -1.05471e-15
-4.9738e-14 8.79252e-15 -6.90841e-15 -2.82617e-15 -5.0243e-15 2.35514e-15 -2.51215e-15 -1.57009e-16
-5.0243e-15 -3.55271e-15 -8.88178e-16 4.44089e-16 -8.88178e-16 -2.22045e-16 6.66134e-16 1.11022e-15
-1.7585e-14 -5.77316e-15 4.44089e-16 -2.66454e-15 2.22045e-16 -6.66134e-16 3.33067e-16 8.88178e-16
-5.65233e-15 3.55271e-15 -1.33227e-15 -4.44089e-16 -2.22045e-16 -4.44089e-16 0 -2.22045e-16
-1.00486e-14 -2.22045e-15 1.9984e-15 2.22045e-16 0 0 0 -2.22045e-16
3.14018e-16 -2.22045e-16 -8.88178e-16 -6.66134e-16 4.44089e-16 4.44089e-16 2.10942e-15 3.88578e-16
2.82617e-15 -3.55271e-15 1.77636e-15 1.22125e-15 2.22045e-16 7.77156e-16 1.88738e-15 1.05471e-15
2.51215e-15 1.9984e-15 2.10942e-15 -1.4988e-15 -9.99201e-16 5.55112e-17 1.11022e-15 2.77556e-16
-114.747 -3.14018e-14 1.22467e-14 -8.16448e-15 -6.90841e-15 1.00486e-14 8.81607e-14 -1.39149e-13
-5.0243e-15 -4.44089e-15 0 4.44089e-16 -4.44089e-16 0 -1.22125e-15 -4.996e-16
-2.51215e-15 5.32907e-15 -8.88178e-16 -1.9984e-15 4.44089e-16 2.22045e-15 -5.55112e-16 -1.66533e-16
1.57009e-14 2.22045e-16 -4.44089e-16 1.77636e-15 -8.88178e-16 -8.88178e-16 1.11022e-16 -6.10623e-16
-3.76822e-15 1.77636e-15 -6.66134e-16 0 0 2.22045e-16 -1.66533e-15 4.996e-16
8.4785e-15 3.77476e-15 6.66134e-16 -1.33227e-15 -1.11022e-16 -8.88178e-16 -1.11022e-16 9.71445e-16
9.02803e-14 7.21645e-15 -6.66134e-16 -7.77156e-16 1.11022e-16 1.05471e-15 -1.94289e-15 -4.16334e-16
-1.42957e-13 2.72005e-15 6.10623e-16 -1.66533e-16 7.77156e-16 1.05471e-15 2.77556e-16 1.84575e-15
-1.00209e-12 6.28037e-16 1.57009e-16 1.25607e-15 1.25607e-15 3.76822e-15 0 -3.76822e-15
1.41308e-14 -3.77476e-15 -2.44249e-15 0 4.44089e-16 -7.77156e-16 -6.66134e-16 9.4369e-16
6.59439e-15 6.66134e-16 -1.11022e-15 -1.33227e-15 4.44089e-16 -1.44329e-15 -5.55112e-16 -8.88178e-16
9.10654e-15 -6.21725e-15 6.66134e-16 -2.22045e-16 4.44089e-16 3.33067e-16 -1.11022e-16 -4.996e-16
3.14018e-16 2.22045e-15 4.44089e-16 -6.66134e-16 3.33067e-16 -7.77156e-16 3.88578e-16 1.02696e-15
1.25607e-15 3.10862e-15 5.55112e-16 -4.44089e-16 -5.55112e-16 -1.27676e-15 9.99201e-16 -1.08247e-15
2.35514e-15 2.77556e-15 -1.22125e-15 2.22045e-16 1.38778e-15 6.10623e-16 1.22125e-15 -1.95677e-15
-1.31888e-14 2.9976e-15 1.27676e-15 -3.05311e-16 1.08247e-15 -5.82867e-16 -1.26288e-15 5.34295e-16
-326.772 -3.41495e-14 3.26579e-14 -3.51701e-14 -1.31888e-14 2.51215e-14 2.49174e-13 -3.90796e-13
-3.18729e-14 -2.66454e-15 -3.21965e-15 -7.77156e-16 -8.88178e-16 8.32667e-16 -1.27676e-15 -1.08247e-15
5.85644e-14 1.66533e-15 -2.22045e-15 -7.77156e-16 1.88738e-15 7.77156e-16 -1.33227e-15 -1.58207e-15
-2.32374e-14 3.33067e-15 7.77156e-16 -3.33067e-16 -1.66533e-15 -2.55351e-15 -1.94289e-15 2.498e-16
-8.16448e-15 3.10862e-15 5.55112e-16 1.27676e-15 1.94289e-15 7.21645e-16 5.55112e-16 1.95677e-15
2.69271e-14 1.38778e-15 -4.60743e-15 -1.9984e-15 7.21645e-16 3.02536e-15 -2.35922e-15 9.15934e-16
2.57495e-13 5.93969e-15 -2.94209e-15 1.7486e-15 -8.32667e-17 -8.32667e-16 -9.15934e-16 1.08941e-15
-3.88284e-13 -1.33227e-15 -1.9984e-15 1.05471e-15 9.29812e-16 7.21645e-16 5.34295e-16 3.66027e-15
- N = 16, N = 25, N = 30 and N = 100
Because the limitation of the body length, the input / output contents of N = 16, N = 25 and N = 30 are as here. Based on my experiment, when N is up to 25, the run time is about a few seconds.
- Different size case in each dimension
N1 = 40, N2 = 30, N3 = 20
Note:
- Each test case is run separately (not parallelly) to ensure the computing resource is available.
- The needed compilers and interpreters are installed for testing.
Winning Criterion & Scores
This is a fastest-code challenge, the runtime performance is determined. Scores are from running on my desktop with an AMD 3950x CPU (16C / 32T) and 64GB of 3600MHz RAM.
