⍝ 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

⍝∇ xtimes to

Back to: code

Back to: Workspaces