2
\$\begingroup\$

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.

3D Discrete Cosine Transform formula1

Considering the different size case in three dimension.

3D Discrete Cosine Transform formula2

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.

\$\endgroup\$
15
  • 1
    \$\begingroup\$ You need to define a requirement on accuracy. Answers may (ab)use loss of accuracy to save time \$\endgroup\$ – Luis Mendo Feb 17 at 0:19
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Bubbler Feb 17 at 0:32
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Adám Feb 17 at 0:39
  • 1
    \$\begingroup\$ I also recommend answering a few existing challenges that have the same winning criteria as the challenges you contemplate posting, as this will give you a sense of the kind of details one needs to write an answer to that type of challenge. \$\endgroup\$ – Adám Feb 17 at 0:41
  • 6
    \$\begingroup\$ > 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. This challenge has been posted here for few days. \$\endgroup\$ – JimmyHu Feb 17 at 1:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.