fork download
copy 
  1. open System
  2. open System.Diagnostics
  3.  
  4. type complex = C of float*float
  5.  
  6. let check (n: int) = true
  7.  
  8. let sum (a: complex) (b: complex) =
  9.     match a, b with
  10.         | C(x1, y1), C(x2, y2) -> C(x1+x2, y1+y2)
  11.  
  12. let mult (a: complex) (b: complex) =
  13.     match a, b with
  14.         | C(x1, y1), C(x2, y2) -> C(x1*x2-y1*y2, x1*y2+x2*y1)
  15.  
  16. let exp (e: float) =
  17.     C(cos e, -sin e)
  18.  
  19. let opp (c: complex) =
  20.     match c with
  21.         | C(a, b) -> C(-a, -b)
  22.  
  23. let rec transform (x: complex array) =
  24.     if not (check x.Length) then failwith "Error, input size invalid"
  25.  
  26.     if x.Length = 1 then x
  27.     else
  28.         let even = Array.init (x.Length/2) (fun i -> x.[2*i])
  29.         let odd = Array.init (x.Length/2) (fun i -> x.[2*i+1])
  30.         let es: complex array = transform even
  31.         let os: complex array = transform odd
  32.         let ret: complex array = Array.zeroCreate x.Length
  33.  
  34.         for i in 0..(x.Length/2)-1 do
  35.             let e = 2. * Math.PI * float i / float x.Length
  36.             ret.[i] <- sum (es.[i]) (mult (exp e) (os.[i]))
  37.             ret.[i+(x.Length/2)] <- sum (es.[i]) (mult (opp (exp e)) (os.[i]))
  38.  
  39.         ret
  40.  
  41. let rndGen = new System.Random(int System.DateTime.Now.Ticks)
  42. let a: complex array = Array.init 65536 (fun _ ->
  43.     let x, y = float (rndGen.Next(128)), float (rndGen.Next(128))
  44.     C(x, y)
  45. )
  46. let t = new Stopwatch()
  47. t.Start()
  48. //let x = transform [|C(1., 0.); C(1., 0.); C(1., 0.); C(1., 0.) |]
  49. let x = transform a
  50. printfn "tempo di esecuzione: %i" t.ElapsedMilliseconds
  51. printfn "%A" x
Success #stdin #stdout 0.96s 22264KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
tempo di esecuzione: 704
[|C (4149143.0,4166585.0); C (-7235.163768,-398.9893226);
  C (-5994.864666,891.0077132); C (8251.184313,3909.848781);
  C (-35.66852321,8136.721674); C (-763.8116348,22142.01248);
  C (-38345.68224,-7427.808025); C (-2539.094144,3181.7744);
  C (-14629.37242,6287.941036); C (8076.987493,3899.705412);
  C (-1066.615623,-5327.083734); C (-6658.972021,-9415.400024);
  C (10657.1039,1521.844033); C (16670.48233,-3869.706528);
  C (12677.54846,-9186.857472); C (8599.287833,-5642.522095);
  C (18356.80642,-755.4423474); C (10810.63638,-9724.896734);
  C (-3145.904863,-6143.049964); C (6759.397742,-12372.30309);
  C (17559.34443,2009.317881); C (-2990.133938,5184.482826);
  C (14919.17518,-4008.774961); C (-12968.95548,-8576.951824);
  C (5699.082135,-11642.63163); C (13406.96216,14110.83624);
  C (17393.50725,11029.32234); C (-5285.615596,3249.728949);
  C (-4216.358485,5392.800673); C (-15506.02132,-8716.545463);
  C (15246.28845,-4771.490678); C (8740.369073,-3726.813186);
  C (-6149.747458,8263.331556); C (14493.58368,-4433.651385);
  C (3399.516443,3779.909975); C (7290.779498,-801.8484442);
  C (-13962.4039,-7066.513782); C (-5407.09571,-13254.87526);
  C (-14150.42905,-390.9538946); C (6749.233737,13153.28217);
  C (-9153.926347,-2471.815901); C (10236.25462,14165.52355);
  C (8312.859234,-5152.600413); C (-9174.192671,1433.003688);
  C (-1822.817019,6078.533903); C (-14547.82901,10065.82906);
  C (1327.745165,-9910.466635); C (-16321.92772,-3337.258233);
  C (1611.61451,-12826.69135); C (-13331.18088,12922.85405);
  C (-5030.318333,19242.84003); C (-18918.29968,7306.882988);
  C (-5841.246669,2577.389984); C (-111.8028628,-3030.304656);
  C (-17181.09913,-12625.77587); C (13833.5913,67.85167031);
  C (-14870.91198,15385.11766); C (13230.67215,-6049.236488);
  C (25497.39219,4230.226945); C (12592.30301,-12542.47096);
  C (2786.655505,-12289.26571); C (-3090.709973,15980.4306);
  C (18619.7197,-6695.02515); C (-17322.00412,-9961.777233);
  C (-10463.20396,6097.344413); C (7301.336905,1101.425591);
  C (16467.31869,2235.234018); C (-12652.07389,632.0751484);
  C (1798.741329,-4184.803705); C (500.7971826,6205.269842);
  C (12854.73471,15115.44969); C (9854.665375,6411.802586);
  C (-728.3673836,2343.879212); C (4526.211058,15271.54153);
  C (6602.530187,9870.168164); C (-4059.356314,5048.84742);
  C (7857.622825,9085.671735); C (-12747.57477,-13305.79812);
  C (-5109.406249,12382.90823); C (425.8445174,-6188.171538);
  C (-12213.48584,2516.078507); C (-11247.70811,1590.235323);
  C (5623.297408,6341.03779); C (-4272.358229,10382.91245);
  C (8489.663457,-12173.55806); C (25989.26116,-2136.88027);
  C (14769.07074,4492.355262); C (970.535618,3929.906537);
  C (3064.79459,-17324.85003); C (-9077.197195,10771.99562);
  C (5500.24536,4120.699541); C (7055.468447,-15321.11942);
  C (5858.489831,7929.181805); C (3909.108808,-6643.95879);
  C (-9749.256198,5584.976536); C (4587.067614,-6168.118171);
  C (-8710.721252,-10356.09788); C (11159.07579,-14347.89195);
  C (-12489.3924,-7024.886512); C (8019.956617,-21042.3045); ...|]
https://ideone.com/qYmpl
language:
F# (mono 4.1)
created:
14 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!