```⍝ Fast multi-digit product using FFT:

⍝ xtimes requires support for complex arithmetic:

⍝ Fast multi-digit product using FFT for cmpx:

⎕io←0

roots     ← {×\1,1↓(⍵÷2)⍴¯1*2÷⍵}
cube      ← {⍵⍴⍨2⍴⍨2⍟⍴⍵}
extend    ← {(2*⌈2⍟¯1+(⍴⍺)+⍴⍵)↑¨⍺ ⍵}
floop     ← {(⊣/⍺)∇⍣(×m)⊢(+⌿⍵),[m-0.5]⍺×[⍳m←≢⍴⍺]-⌿⍵}
FFT       ← {      ,(cube  roots ⍴⍵)floop cube ⍵}
iFFT      ← {(⍴⍵)÷⍨,(cube +roots ⍴⍵)floop cube ⍵}
rconvolve ← {(¯1+(⍴⍺)+⍴⍵)↑iFFT ⊃×/FFT¨⍺ extend ⍵}
carry     ← {1↓+⌿1 0⌽0,0 10⊤⍵}

convolve  ← {+⌿(-⍳⍴⍺)⌽⍺∘.×⍵,0×1↓⍺}

x←¯50+?23⍴100
y←¯50+?17⍴100

(¯1+(⍴x)+⍴y)≡⍴x rconvolve y
1
(x rconvolve y)≡x rconvolve⍨y
1
(x convolve y)≡⌊0.5+9○ x rconvolve y
1
x←¯500+?16⍴1000

x≡⌊0.5+9○ iFFT FFT x
1
x≡⌊0.5+9○ FFT iFFT x
1
x←?7⍴10
y←?5⍴10

(' '~⍨⍕x xtimes y)≡{⎕pp←18 ⋄ ⍕⍵}(10⊥x)×10⊥y
1
(x xtimes y)≡y xtimes x
1
p←(?1000)⍴0
q←(?1000)⍴0

((x xtimes y),p,q)≡(x,p)xtimes(y,q)
1
xtimes⍨ 9/9
9 9 9 9 9 9 9 9 8 0 0 0 0 0 0 0 0 1

↑{⍕xtimes⍨ ⍵/9}¨2 to 10
9 8 0 1
9 9 8 0 0 1
9 9 9 8 0 0 0 1
9 9 9 9 8 0 0 0 0 1
9 9 9 9 9 8 0 0 0 0 0 1
9 9 9 9 9 9 8 0 0 0 0 0 0 1
9 9 9 9 9 9 9 8 0 0 0 0 0 0 0 1
9 9 9 9 9 9 9 9 8 0 0 0 0 0 0 0 0 1
9 9 9 9 9 9 9 9 9 8 0 0 0 0 0 0 0 0 0 1

try←{                       ⍝ test 999...s squared.
exp←(⍵ 2 ⍵ 2-1)/9 8 0 1 ⍝ expected result
act←xtimes⍨⍵/9          ⍝ actual result
act≡exp                 ⍝ actual matches expected.
}

∧/try¨ 10 20 to 100         ⍝ square lots of 999...s.
1

Back to: code

Back to: Workspaces
```