package Ġnet . dev rom ik . poly Ċ Ċ import Ġnet . dev rom ik . poly . utils .* Ċ import Ġjava . lang . Integer . numberOf Leading Z eros Ċ import Ġjava . lang . Integer . reverse Ċ Ċ /** Ċ Ġ* Ġ@ author ĠSh ul ny ae v ĠRoman Ċ Ġ*/ Ċ private Ġval ĠPR INC IP AL _ ROOT S _ OF _ UN ITY _ FOR _ DIRECT _ FFT Ġ= ĠarrayOf ( ĊĠĠĠ ĠComplex ( re =- 1 . 0 , Ġim = 1 . 2 2 4 6 4 6 7 9 9 1 4 7 3 5 3 2 E - 1 6 ), ĊĠĠĠ ĠComplex ( re = 6 . 1 2 3 2 3 3 9 9 5 7 3 6 7 6 6 E - 1 7 , Ġim = 1 . 0 ), ĊĠĠĠ ĠComplex ( re = 0 . 7 0 7 1 0 6 7 8 1 1 8 6 5 4 7 6 , Ġim = 0 . 7 0 7 1 0 6 7 8 1 1 8 6 5 4 7 5 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 2 3 8 7 9 5 3 2 5 1 1 2 8 6 7 , Ġim = 0 . 3 8 2 6 8 3 4 3 2 3 6 5 0 8 9 8 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 8 0 7 8 5 2 8 0 4 0 3 2 3 0 4 , Ġim = 0 . 1 9 5 0 9 0 3 2 2 0 1 6 1 2 8 2 5 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 5 1 8 4 7 2 6 6 7 2 1 9 6 9 , Ġim = 0 . 0 9 8 0 1 7 1 4 0 3 2 9 5 6 0 6 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 8 7 9 5 4 5 6 2 0 5 1 7 2 4 , Ġim = 0 . 0 4 9 0 6 7 6 7 4 3 2 7 4 1 8 0 1 5 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 6 9 8 8 1 8 6 9 6 2 0 4 2 , Ġim = 0 . 0 2 4 5 4 1 2 2 8 5 2 2 9 1 2 2 8 8 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 2 4 7 0 1 8 3 9 1 4 4 5 , Ġim = 0 . 0 1 2 2 7 1 5 3 8 2 8 5 7 1 9 9 2 5 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 8 1 1 7 5 2 8 2 6 0 1 1 , Ġim = 0 . 0 0 6 1 3 5 8 8 4 6 4 9 1 5 4 4 7 5 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 9 5 2 9 3 8 0 9 5 7 6 2 , Ġim = 0 . 0 0 3 0 6 7 9 5 6 7 6 2 9 6 5 9 7 6 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 9 8 8 2 3 4 5 1 7 0 1 9 , Ġim = 0 . 0 0 1 5 3 3 9 8 0 1 8 6 2 8 4 7 6 5 5 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 9 9 7 0 5 8 6 2 8 8 2 2 , Ġim = 7 . 6 6 9 9 0 3 1 8 7 4 2 7 0 4 5 E - 4 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 9 9 9 2 6 4 6 5 7 1 7 9 , Ġim = 3 . 8 3 4 9 5 1 8 7 5 7 1 3 9 5 5 6 E - 4 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 9 9 9 8 1 6 1 6 4 2 9 3 , Ġim = 1 . 9 1 7 4 7 5 9 7 3 1 0 7 0 3 3 E - 4 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 9 9 9 9 5 4 0 4 1 0 7 3 , Ġim = 9 . 5 8 7 3 7 9 9 0 9 5 9 7 7 3 4 E - 5 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 9 9 9 9 8 8 5 1 0 2 6 9 , Ġim = 4 . 7 9 3 6 8 9 9 6 0 3 0 6 6 8 8 E - 5 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 9 9 9 9 9 7 1 2 7 5 6 7 , Ġim = 2 . 3 9 6 8 4 4 9 8 0 8 4 1 8 2 2 E - 5 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 9 9 9 9 9 9 2 8 1 8 9 2 , Ġim = 1 . 1 9 8 4 2 2 4 9 0 5 0 6 9 7 0 5 E - 5 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 9 9 9 9 9 9 8 2 0 4 7 2 , Ġim = 5 . 9 9 2 1 1 2 4 5 2 6 4 2 4 2 7 5 E - 6 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 9 9 9 9 9 9 9 5 5 1 1 8 , Ġim = 2 . 9 9 6 0 5 6 2 2 6 3 3 4 6 6 1 E - 6 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 9 9 9 9 9 9 9 8 8 7 8 , Ġim = 1 . 4 9 8 0 2 8 1 1 3 1 6 9 0 1 1 1 E - 6 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 9 9 9 9 9 9 9 9 7 1 9 4 , Ġim = 7 . 4 9 0 1 4 0 5 6 5 8 4 7 1 5 7 E - 7 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 9 9 9 9 9 9 9 9 9 2 9 8 , Ġim = 3 . 7 4 5 0 7 0 2 8 2 9 2 3 8 4 1 3 E - 7 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 9 9 9 9 9 9 9 9 9 8 2 5 , Ġim = 1 . 8 7 2 5 3 5 1 4 1 4 6 1 9 5 3 5 E - 7 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 9 9 9 9 9 9 9 9 9 9 5 7 , Ġim = 9 . 3 6 2 6 7 5 7 0 7 3 0 9 8 0 8 E - 8 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 9 9 9 9 9 9 9 9 9 9 8 9 , Ġim = 4 . 6 8 1 3 3 7 8 5 3 6 5 4 9 0 9 E - 8 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 8 , Ġim = 2 . 3 4 0 6 6 8 9 2 6 8 2 7 4 5 5 E - 8 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 , Ġim = 1 . 1 7 0 3 3 4 4 6 3 4 1 3 7 2 7 7 E - 8 ) Ċ ) Ċ Ċ private Ġval ĠPR INC IP AL _ ROOT S _ OF _ UN ITY _ FOR _ IN VERSE _ FFT Ġ= ĠarrayOf ( ĊĠĠĠ ĠComplex ( re =- 1 . 0 , Ġim =- 1 . 2 2 4 6 4 6 7 9 9 1 4 7 3 5 3 2 E - 1 6 ), ĊĠĠĠ ĠComplex ( re = 6 . 1 2 3 2 3 3 9 9 5 7 3 6 7 6 6 E - 1 7 , Ġim =- 1 . 0 ), ĊĠĠĠ ĠComplex ( re = 0 . 7 0 7 1 0 6 7 8 1 1 8 6 5 4 7 6 , Ġim =- 0 . 7 0 7 1 0 6 7 8 1 1 8 6 5 4 7 5 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 2 3 8 7 9 5 3 2 5 1 1 2 8 6 7 , Ġim =- 0 . 3 8 2 6 8 3 4 3 2 3 6 5 0 8 9 8 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 8 0 7 8 5 2 8 0 4 0 3 2 3 0 4 , Ġim =- 0 . 1 9 5 0 9 0 3 2 2 0 1 6 1 2 8 2 5 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 5 1 8 4 7 2 6 6 7 2 1 9 6 9 , Ġim =- 0 . 0 9 8 0 1 7 1 4 0 3 2 9 5 6 0 6 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 8 7 9 5 4 5 6 2 0 5 1 7 2 4 , Ġim =- 0 . 0 4 9 0 6 7 6 7 4 3 2 7 4 1 8 0 1 5 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 6 9 8 8 1 8 6 9 6 2 0 4 2 , Ġim =- 0 . 0 2 4 5 4 1 2 2 8 5 2 2 9 1 2 2 8 8 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 2 4 7 0 1 8 3 9 1 4 4 5 , Ġim =- 0 . 0 1 2 2 7 1 5 3 8 2 8 5 7 1 9 9 2 5 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 8 1 1 7 5 2 8 2 6 0 1 1 , Ġim =- 0 . 0 0 6 1 3 5 8 8 4 6 4 9 1 5 4 4 7 5 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 9 5 2 9 3 8 0 9 5 7 6 2 , Ġim =- 0 . 0 0 3 0 6 7 9 5 6 7 6 2 9 6 5 9 7 6 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 9 8 8 2 3 4 5 1 7 0 1 9 , Ġim =- 0 . 0 0 1 5 3 3 9 8 0 1 8 6 2 8 4 7 6 5 5 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 9 9 7 0 5 8 6 2 8 8 2 2 , Ġim =- 7 . 6 6 9 9 0 3 1 8 7 4 2 7 0 4 5 E - 4 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 9 9 9 2 6 4 6 5 7 1 7 9 , Ġim =- 3 . 8 3 4 9 5 1 8 7 5 7 1 3 9 5 5 6 E - 4 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 9 9 9 8 1 6 1 6 4 2 9 3 , Ġim =- 1 . 9 1 7 4 7 5 9 7 3 1 0 7 0 3 3 E - 4 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 9 9 9 9 5 4 0 4 1 0 7 3 , Ġim =- 9 . 5 8 7 3 7 9 9 0 9 5 9 7 7 3 4 E - 5 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 9 9 9 9 8 8 5 1 0 2 6 9 , Ġim =- 4 . 7 9 3 6 8 9 9 6 0 3 0 6 6 8 8 E - 5 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 9 9 9 9 9 7 1 2 7 5 6 7 , Ġim =- 2 . 3 9 6 8 4 4 9 8 0 8 4 1 8 2 2 E - 5 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 9 9 9 9 9 9 2 8 1 8 9 2 , Ġim =- 1 . 1 9 8 4 2 2 4 9 0 5 0 6 9 7 0 5 E - 5 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 9 9 9 9 9 9 8 2 0 4 7 2 , Ġim =- 5 . 9 9 2 1 1 2 4 5 2 6 4 2 4 2 7 5 E - 6 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 9 9 9 9 9 9 9 5 5 1 1 8 , Ġim =- 2 . 9 9 6 0 5 6 2 2 6 3 3 4 6 6 1 E - 6 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 9 9 9 9 9 9 9 8 8 7 8 , Ġim =- 1 . 4 9 8 0 2 8 1 1 3 1 6 9 0 1 1 1 E - 6 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 9 9 9 9 9 9 9 9 7 1 9 4 , Ġim =- 7 . 4 9 0 1 4 0 5 6 5 8 4 7 1 5 7 E - 7 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 9 9 9 9 9 9 9 9 9 2 9 8 , Ġim =- 3 . 7 4 5 0 7 0 2 8 2 9 2 3 8 4 1 3 E - 7 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 9 9 9 9 9 9 9 9 9 8 2 5 , Ġim =- 1 . 8 7 2 5 3 5 1 4 1 4 6 1 9 5 3 5 E - 7 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 9 9 9 9 9 9 9 9 9 9 5 7 , Ġim =- 9 . 3 6 2 6 7 5 7 0 7 3 0 9 8 0 8 E - 8 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 9 9 9 9 9 9 9 9 9 9 8 9 , Ġim =- 4 . 6 8 1 3 3 7 8 5 3 6 5 4 9 0 9 E - 8 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 8 , Ġim =- 2 . 3 4 0 6 6 8 9 2 6 8 2 7 4 5 5 E - 8 ), ĊĠĠĠ ĠComplex ( re = 0 . 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 , Ġim =- 1 . 1 7 0 3 3 4 4 6 3 4 1 3 7 2 7 7 E - 8 ) Ċ ) Ċ Ċ fun Ġfft ( a : ĠArray < Complex >, Ġinverse : ĠBoolean ) Ġ{ ĊĠĠĠ Ġdo Bit Re versal Per mutation Of ( a ) ĊĊĠĠĠ Ġval Ġprincipal Roots Of Unity Ġ= Ġif Ġ( inverse ) ĠPR INC IP AL _ ROOT S _ OF _ UN ITY _ FOR _ IN VERSE _ FFT Ġelse ĠPR INC IP AL _ ROOT S _ OF _ UN ITY _ FOR _ DIRECT _ FFT ĊĊĠĠĠ Ġval Ġn Ġ= Ġa . size ĊĠĠĠ Ġvar Ġr Ġ= Ġ 2 ĊĠĠĠ Ġvar Ġprincipal Root Of Unity Index Ġ= Ġ 0 ĊĊĠĠĠ Ġwhile Ġ( r Ġ<= Ġn ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġprincipal Root Of Unity Ġ= Ġprincipal Roots Of Unity [ principal Root Of Unity Index ] ĊĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 .. n Ġ- Ġ 1 Ġstep Ġr ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġw Ġ= ĠCOMP LEX _ UN ITY ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( j Ġin Ġ 0 .. r Ġ/ Ġ 2 Ġ- Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġu Ġ= Ġa [ i Ġ+ Ġj ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġv Ġ= Ġa [ i Ġ+ Ġj Ġ+ Ġr Ġ/ Ġ 2 ] Ġ* Ġw ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġa [ i Ġ+ Ġj ] Ġ= Ġu Ġ+ Ġv ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġa [ i Ġ+ Ġj Ġ+ Ġr Ġ/ Ġ 2 ] Ġ= Ġu Ġ- Ġv ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġw Ġ*= Ġprincipal Root Of Unity ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġr Ġ= Ġr . sh l ( 1 ) ĊĠĠĠĠĠĠĠ Ġ++ principal Root Of Unity Index ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġif Ġ( inverse ) Ġ{ ĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 .. n Ġ- Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġa [ i ] Ġ= Ġa [ i ] Ġ/ Ġn ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ } Ċ Ċ fun Ġdo Bit Re versal Per mutation Of ( a : ĠArray < Complex >) Ġ{ ĊĠĠĠ Ġval Ġn Ġ= Ġa . size ĊĠĠĠ Ġval Ġshift Ġ= ĠnumberOf Leading Z eros ( n ) Ġ+ Ġ 1 ĊĊĠĠĠ Ġfor Ġ( i Ġin Ġ 0 .. n Ġ- Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġp Ġ= Ġreverse ( i ). ush r ( shift ) ĊĊĠĠĠĠĠĠĠ Ġif Ġ( i Ġ< Ġp ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtemp Ġ= Ġa [ i ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġa [ i ] Ġ= Ġa [ p ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġa [ p ] Ġ= Ġtemp ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ }