Chris@19: (*
Chris@19:  * Copyright (c) 1997-1999 Massachusetts Institute of Technology
Chris@19:  * Copyright (c) 2003, 2007-14 Matteo Frigo
Chris@19:  * Copyright (c) 2003, 2007-14 Massachusetts Institute of Technology
Chris@19:  *
Chris@19:  * This program is free software; you can redistribute it and/or modify
Chris@19:  * it under the terms of the GNU General Public License as published by
Chris@19:  * the Free Software Foundation; either version 2 of the License, or
Chris@19:  * (at your option) any later version.
Chris@19:  *
Chris@19:  * This program is distributed in the hope that it will be useful,
Chris@19:  * but WITHOUT ANY WARRANTY; without even the implied warranty of
Chris@19:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
Chris@19:  * GNU General Public License for more details.
Chris@19:  *
Chris@19:  * You should have received a copy of the GNU General Public License
Chris@19:  * along with this program; if not, write to the Free Software
Chris@19:  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
Chris@19:  *
Chris@19: *)
Chris@19: 
Chris@19: open Complex
Chris@19: open Util
Chris@19: 
Chris@19: let polyphase m a ph i = a (m * i + ph)
Chris@19: 
Chris@19: let rec divmod n i =
Chris@19:   if (i < 0) then 
Chris@19:     let (a, b) = divmod n (i + n)
Chris@19:     in (a - 1, b)
Chris@19:   else (i / n, i mod n)
Chris@19: 
Chris@19: let unpolyphase m a i = let (x, y) = divmod m i in a y x
Chris@19: 
Chris@19: let lift2 f a b i = f (a i) (b i)
Chris@19: 
Chris@19: (* convolution of signals A and B *)
Chris@19: let rec conv na a nb b =
Chris@19:   let rec naive na a nb b i =
Chris@19:     sigma 0 na (fun j -> (a j) @* (b (i - j)))
Chris@19: 
Chris@19:   and recur na a nb b =
Chris@19:     if (na <= 1 || nb <= 1) then
Chris@19:       naive na a nb b
Chris@19:     else
Chris@19:       let p = polyphase 2 in
Chris@19:       let ee = conv (na - na / 2) (p a 0) (nb - nb / 2) (p b 0)
Chris@19:       and eo = conv (na - na / 2) (p a 0) (nb / 2) (p b 1)
Chris@19:       and oe = conv (na / 2) (p a 1) (nb - nb / 2) (p b 0)
Chris@19:       and oo = conv (na / 2) (p a 1) (nb / 2) (p b 1) in
Chris@19:       unpolyphase 2 (function
Chris@19: 	  0 -> fun i -> (ee i) @+ (oo (i - 1))
Chris@19: 	| 1 -> fun i -> (eo i) @+ (oe i) 
Chris@19: 	| _ -> failwith "recur")
Chris@19: 
Chris@19: 
Chris@19:   (* Karatsuba variant 1: (a+bx)(c+dx) = (ac+bdxx)+((a+b)(c+d)-ac-bd)x *)
Chris@19:   and karatsuba1 na a nb b =
Chris@19:       let p = polyphase 2 in
Chris@19:       let ae = p a 0 and nae = na - na / 2
Chris@19:       and ao = p a 1 and nao = na / 2
Chris@19:       and be = p b 0 and nbe = nb - nb / 2
Chris@19:       and bo = p b 1 and nbo = nb / 2 in
Chris@19:       let ae = infinite nae ae and ao = infinite nao ao
Chris@19:       and be = infinite nbe be and bo = infinite nbo bo in
Chris@19:       let aeo = lift2 (@+) ae ao and naeo = nae
Chris@19:       and beo = lift2 (@+) be bo and nbeo = nbe in
Chris@19:       let ee = conv nae ae nbe be 
Chris@19:       and oo = conv nao ao nbo bo
Chris@19:       and eoeo = conv naeo aeo nbeo beo in
Chris@19: 
Chris@19:       let q = function
Chris@19: 	  0 -> fun i -> (ee i)  @+ (oo (i - 1))
Chris@19: 	| 1 -> fun i -> (eoeo i) @- ((ee i) @+ (oo i))
Chris@19: 	| _ -> failwith "karatsuba1" in
Chris@19:       unpolyphase 2 q
Chris@19: 
Chris@19:   (* Karatsuba variant 2: 
Chris@19:      (a+bx)(c+dx) = ((a+b)c-b(c-dxx))+x((a+b)c-a(c-d)) *)
Chris@19:   and karatsuba2 na a nb b =
Chris@19:       let p = polyphase 2 in
Chris@19:       let ae = p a 0 and nae = na - na / 2
Chris@19:       and ao = p a 1 and nao = na / 2
Chris@19:       and be = p b 0 and nbe = nb - nb / 2
Chris@19:       and bo = p b 1 and nbo = nb / 2 in
Chris@19:       let ae = infinite nae ae and ao = infinite nao ao
Chris@19:       and be = infinite nbe be and bo = infinite nbo bo in
Chris@19: 
Chris@19:       let c1 = conv nae (lift2 (@+) ae ao) nbe be
Chris@19:       and c2 = conv nao ao (nbo + 1) (fun i -> be i @- bo (i - 1))
Chris@19:       and c3 = conv nae ae nbe (lift2 (@-) be bo) in
Chris@19: 
Chris@19:       let q = function
Chris@19: 	  0 -> lift2 (@-) c1 c2
Chris@19: 	| 1 -> lift2 (@-) c1 c3
Chris@19: 	| _ -> failwith "karatsuba2" in
Chris@19:       unpolyphase 2 q
Chris@19: 
Chris@19:   and karatsuba na a nb b =
Chris@19:     let m = na + nb - 1 in
Chris@19:     if (m < !Magic.karatsuba_min) then
Chris@19:       recur na a nb b
Chris@19:     else
Chris@19:       match !Magic.karatsuba_variant with
Chris@19: 	1 -> karatsuba1 na a nb b
Chris@19:       |	2 -> karatsuba2 na a nb b
Chris@19:       |	_ -> failwith "unknown karatsuba variant"
Chris@19: 
Chris@19:   and via_circular na a nb b =
Chris@19:     let m = na + nb - 1 in
Chris@19:     if (m < !Magic.circular_min) then
Chris@19:       karatsuba na a nb b
Chris@19:     else
Chris@19:       let rec find_min n = if n >= m then n else find_min (2 * n) in
Chris@19:       circular (find_min 1) a b
Chris@19: 
Chris@19:   in
Chris@19:   let a = infinite na a and b = infinite nb b in
Chris@19:   let res = array (na + nb - 1) (via_circular na a nb b) in
Chris@19:   infinite (na + nb - 1) res
Chris@19:     
Chris@19: and circular n a b =
Chris@19:   let via_dft n a b =
Chris@19:     let fa = Fft.dft (-1) n a 
Chris@19:     and fb = Fft.dft (-1) n b
Chris@19:     and scale = inverse_int n in
Chris@19:     let fab i = ((fa i) @* (fb i)) @* scale in
Chris@19:     Fft.dft 1 n fab
Chris@19: 
Chris@19:   in via_dft n a b