package Ġde sel by . std Ċ Ċ import Ġde sel by . std . collections . Double ND Array Ċ import Ġkotlin . math . PI Ċ import Ġkotlin . math . sin Ċ Ċ object ĠFour ier Ġ{ ĊĠĠĠ Ġ// ĠND Array Ġshould Ġhave Ġshape Ġ( 2 ^ n An nih il ations , 2 ) Ġfinal Ġdimension Ġis Ġfor ĊĠĠĠ Ġ// Ġreal Ġand Ġimag inary Ġcomponents . ĊĠĠĠ Ġ// ĠForward Ġtransform Ġis Ġdefined Ġas ĊĠĠĠ Ġ// ĊĠĠĠ Ġ// ĠH _ n Ġ= Ġ\ sum _{ k = 0 }^{ N - 1 } Ġh _ k Ġe ^{ 2 \ pi Ġi Ġk Ġn An nih il ations Ġ/ ĠN } ĊĠĠĠ Ġ// ĊĠĠĠ Ġ// ĠBack ward Ġis Ġdefined Ġas ĊĠĠĠ Ġ// ĊĠĠĠ Ġ// Ġh _ k Ġ= Ġ 1 / N Ġ\ sum _{ n An nih il ations = 0 }^{ N - 1 } ĠH _ n Ġe ^{- 2 \ pi Ġi Ġk Ġn An nih il ations Ġ/ ĠN } ĊĠĠĠ Ġ// ĊĠĠĠ Ġ// ĠSee ĠNum erical ĠRe cipes Ġ 3 rd ĠEdition ĠSection Ġ 1 2 . 1 ĊĠĠĠ Ġfun Ġtransform In Place ( data Ġ: ĠDouble ND Array , Ġis Forward Ġ: ĠBoolean ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif ( data . shape [ 1 ] Ġ!= Ġ 2 ) Ġthrow ( IllegalArgumentException (" second Ġdimension Ġshould Ġbe Ġof Ġsize Ġ 2 Ġto Ġstore Ġcomplex Ġnumbers ")) ĊĠĠĠĠĠĠĠ Ġif ( data . shape [ 0 ] Ġand Ġ( data . shape [ 0 ]- 1 ) Ġ!= Ġ 0 ) Ġthrow ( IllegalArgumentException (" size Ġof Ġlist Ġmust Ġbe Ġa Ġpower Ġof Ġ 2 ")) ĊĠĠĠĠĠĠĠ Ġif ( data . shape [ 0 ] Ġ< Ġ 2 ) Ġreturn ĊĠĠĠĠĠĠĠ Ġval Ġis ign Ġ= Ġif ( is Forward ) Ġ 1 Ġelse Ġ- 1 ĊĠĠĠĠĠĠĠ Ġvar Ġj Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġfor ( i Ġin Ġ 0 Ġuntil Ġdata . shape [ 0 ]) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif ( j Ġ> Ġi ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtmp 0 Ġ= Ġdata [ i , 0 ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtmp 1 Ġ= Ġdata [ i , 1 ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdata [ i , 0 ] Ġ= Ġdata [ j , 0 ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdata [ i , 1 ] Ġ= Ġdata [ j , 1 ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdata [ j , 0 ] Ġ= Ġtmp 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdata [ j , 1 ] Ġ= Ġtmp 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġm Ġ= Ġdata . shape [ 0 ]/ 2 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile ( m Ġin Ġ 1 Ġ.. Ġj ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġj Ġ-= Ġm ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġm Ġ/= Ġ 2 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġj Ġ+= Ġm ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġvar Ġm max Ġ= Ġ 1 ĊĠĠĠĠĠĠĠ Ġvar Ġwr Ġ: ĠDouble ĊĠĠĠĠĠĠĠ Ġvar Ġwi Ġ: ĠDouble ĊĠĠĠĠĠĠĠ Ġwhile ( m max Ġ< Ġdata . shape [ 0 ]) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġist ep Ġ= Ġm max Ġ* Ġ 2 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtheta Ġ= Ġis ign *( PI Ġ/ m max ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġw temp Ġ= Ġsin ( 0 . 5 * theta ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġw pr Ġ= Ġ- 2 . 0 * w temp * w temp ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġw pi Ġ= Ġsin ( theta ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwr Ġ= Ġ 1 . 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwi Ġ= Ġ 0 . 0 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor ( m Ġin Ġ 0 Ġuntil Ġm max ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor ( i Ġin Ġm Ġuntil Ġdata . shape [ 0 ] Ġstep Ġist ep ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġj Ġ= Ġi Ġ+ Ġm max ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtmp r Ġ= Ġwr * data [ j , 0 ] Ġ- Ġwi * data [ j , 1 ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtmp i Ġ= Ġwr * data [ j , 1 ] Ġ+ Ġwi * data [ j , 0 ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdata [ j , 0 ] Ġ= Ġdata [ i , 0 ]- tmp r ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdata [ j , 1 ] Ġ= Ġdata [ i , 1 ]- tmp i ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdata [ i , 0 ] Ġ+= Ġtmp r ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdata [ i , 1 ] Ġ+= Ġtmp i ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġwr 0 Ġ= Ġwr ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwr Ġ+= Ġwr Ġ* Ġw pr Ġ- Ġwi Ġ* Ġw pi ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwi Ġ+= Ġwi Ġ* Ġw pr Ġ+ Ġwr 0 Ġ* Ġw pi ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġm max Ġ= Ġist ep ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif (! is Forward ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġs Ġ= Ġ 1 . 0 / data . shape [ 0 ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor ( i Ġin Ġ 0 Ġuntil Ġdata . shape [ 0 ]) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdata [ i , 0 ] Ġ*= Ġs ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdata [ i , 1 ] Ġ*= Ġs ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ } Ċ Ċ // ĠND Array Ġshould Ġhave Ġshape Ġ( 2 ^ i 0 ... 2 ^ in , 2 ) Ċ fun ĠDouble ND Array . four ier Transform In Place ( is Forward Ġ: ĠBoolean ) Ġ{ ĊĠĠĠ Ġval Ġslice Ġ= ĠND Range ( shape . size ) Ġ{ 0 .. 0 } ĊĠĠĠ Ġslice [ shape . size - 1 ] Ġ= Ġ 0 .. 1 ĊĠĠĠ Ġvar Ġi Ġ: ĠInt ĊĠĠĠ Ġvar Ġnot Overflow Ġ: ĠBoolean ĊĠĠĠ Ġfor ( transform Dimension Ġin Ġ 0 Ġ.. Ġshape . size - 2 ) Ġ{ ĊĠĠĠĠĠĠĠ Ġslice [ transform Dimension ] Ġ= Ġ 0 Ġuntil Ġshape [ transform Dimension ] ĊĠĠĠĠĠĠĠ Ġnot Overflow Ġ= Ġtrue ĊĠĠĠĠĠĠĠ Ġwhile ( not Overflow ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġone D slice Ġ= Ġthis [ slice ]. re Shape ( shape [ transform Dimension ], 2 ) ĊĠĠĠĠĠĠĠĠĠĠĠ ĠFour ier . transform In Place ( one D slice , is Forward ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġcount Ġthrough Ġother Ġdimensions ĊĠĠĠĠĠĠĠĠĠĠĠ Ġi Ġ= Ġshape . size Ġ- Ġ 2 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif ( i Ġ== Ġtransform Dimension ) Ġ-- i ĊĠĠĠĠĠĠĠĠĠĠĠ Ġslice [ i ] Ġ= Ġslice [ i ]. first Ġ+ Ġ 1 Ġ.. Ġslice [ i ]. last Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnot Overflow Ġ= Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( not Overflow Ġ&& Ġ( slice [ i ]. last Ġ== Ġshape [ i ])) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġslice [ i ] Ġ= Ġ 0 .. 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif (-- i Ġ== Ġtransform Dimension ) Ġ-- i ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif ( i < 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnot Overflow Ġ= Ġfalse ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġslice [ i ] Ġ= Ġslice [ i ]. first Ġ+ Ġ 1 Ġ.. Ġslice [ i ]. last Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġslice [ transform Dimension ] Ġ= Ġ 0 .. 0 ĊĠĠĠ Ġ} Ċ } Ċ