# Compute the Three Dimensional Discrete Cosine Transform

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.

1. 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

1. 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.

1. 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 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.

• You need to define a requirement on accuracy. Answers may (ab)use loss of accuracy to save time Feb 17, 2021 at 0:19
• So basically it's about implementing the VR DIF algorithm which has O(n^3 log n) time complexity, though I'm not sure if it works with non-power-of-2 dimensions. Feb 17, 2021 at 0:32
• I'd highly recommend the Sandbox the first few (or many) times you write challenges, but even more so for non-code-golf challenges, as these are notoriously hard to get right.