RandomConvolution.fs

#if INTERACTIVE
let (++) a b = System.IO.Path.Combine(a, b)
let source = __SOURCE_DIRECTORY__ ++ __SOURCE_FILE__
let args = sprintf "--platform:x86 %s -o:%s" source <| source.Replace("fs", "exe")
System.Diagnostics.Process.Start(System.AppDomain.CurrentDomain.BaseDirectory ++ "fsc", args)
#endif

let time f x =
    let ts = System.Diagnostics.Stopwatch.StartNew()
    let result = f x
    printfn "Took %.3fs" ts.Elapsed.TotalSeconds
    result

let inline ffoldi n f state =
    let mutable state = state
    for i = 0 to n - 1 do
        state <- f state i
    state

let product values n =
    let p = Array.length values
    Array.init (pown p n) (fun i ->
        (Array.zeroCreate n, i)
        |> ffoldi n (fun (result, i') j ->
            result.[j] <- values.[i' % p]
            result, i' / p
        )
        |> fst
    )

let convolute signals filter =
    let m = Array.length signals
    let n = Array.length filter
    let len = max m n - min m n + 1
    
    Array.init len (fun offset ->
        ffoldi n (fun acc i ->
            acc + filter.[i] * signals.[m - 1 - offset - i]
        ) 0
    )

let go () =
    let n = 6
    let iters = 1000
 
    let next =
        time (fun () ->
            let arrays =
                product [|-1; 0; 0; 1|] n
                |> Array.filter (Array.forall ((=) 0) >> not)
            let rnd = System.Random()
            fun () -> arrays.[rnd.Next arrays.Length]
        ) ()

    let signals = product [|-1; 1|] (n + 1)

    let firstzero, bothzero =
        ffoldi signals.Length (fun (firstzero, bothzero) i ->
            let s = signals.[i]
            ffoldi iters (fun (first, both) _ ->
                let f = next()
                match convolute s f with
                | [|0; 0|] -> first + 1, both + 1
                | [|0; _|] -> first + 1, both
                | _ -> first, both
            ) (firstzero, bothzero)
        ) (0, 0)

    printfn "firstzero %i" firstzero
    printfn "bothzero %i" bothzero

[<EntryPoint>]
let main _ =
    time go ()
    0