Integer Multiplication Index   <<   >>

 

⍺ ptimes ⍵ 
   ←→ interp (⍺ eval v) × (⍵ eval v)
   ←→ iFFT (FFT ⍺) × (FFT ⍵)

   ←→ ⍺ ×⍢(eval∘v) ⍵
   ←→ ⍺ ×⍢FFT ⍵


Henry Rich, http://www.jsoftware.com/jwiki/Essays/FFT


cube      =: ($~ q:@#) :. ,
roots     =: _1 ^ i. % ] 
butterfly =: 4 : 'for_r. i.#$y do. (x=.{."1 x) ] y=.(+/y) ,&,:"r x*-/y end.'
FFT       =: (       roots@-:@# butterfly&.cube ]) f. :. iFFT
iFFT      =: (# %~ +@roots@-:@# butterfly&.cube ]) f. :.  FFT
extend    =: >.&.(2&^.)@<:@+&# {."1 ,:
ptimesj   =: *&.FFT/ @ extend

ptimesa←{
  cube      ← {⍵⍴⍨2⍴⍨2⍟⍴⍵}
  roots     ← {¯1*(⍳⍵)÷⍵}
  butterfly ← {(⊣/⍺)∇⍣(×r)⊢(+⌿⍵),[r-0.5]⍺×[⍳r←⍬⍴⍴⍴⍺]-⌿⍵}
  FFT       ← {      ,(cube  roots 2÷⍨⍴⍵) butterfly cube ⍵}
  iFFT      ← {(⍴⍵)÷⍨,(cube +roots 2÷⍨⍴⍵) butterfly cube ⍵}
  m←2*⌈2⍟¯1+(⍴⍺)+⍴⍵
  iFFT (FFT m↑⍺) × (FFT m↑⍵)
}

_______________________

4 : 'for_r. i.#$x do. (x=.{."1 x) ] y=.(+/y) ,&,:"r x*-/y end.'
{(⊣/⍺)∇⍣(×r)⊢(+⌿⍵),[r-0.5]⍺×[⍳r←⍬⍴⍴⍴⍺]-⌿⍵}