deleted 106 characters in body

Source Link

edited Aug 11, 2017 at 14:29

17k
2
30
94

J, 110 104 95 8979 bytes, OO(nn log nn)

f=:_2&([:0((+,-)(%_1^i]%_1^i.@#%#))&f/@|:_2]\])^:(1<#]\)~1<#
9:o.<:@+&#{.[:@+&#$9(o.f%#)[:+@*/,:f@;f@{."1~2^#@#&>~2^#@#:@+&#

   f =: _2&([:0((+,-)(%_1^i]%_1^i.@#%#))&f/@|:_2]\])^:(1<#]\)~1<#
   g =: 9:o.<:@+&#{.[:@+&#$9(o.f%#)[:+@*/,:f@;f@{."1~2^#@#&>~2^#@#:@+&#
   1 2 3 4 g 5 6 7 8
5 16 34 60 61 52 32
   2 4 5 6 1 g 1 2 4 7
2 8 21 46 61 61 46 7

Try it online!

Explanation (Outdated)

9 o.<:@+&#{.[:@+&#$9(o.f%#)[:+@*/,:f@;f@{."1~2^2>.@^.+&#&>~2^#@#:@+&#  Input: A on LHS, B on RHS
                                            #  Get the lengths of A and B
                                          +&   Sum them
                                    2   ^.  #:@   Find log baseGet 2list of it
      binary digits
                              >.@ #@      Find its ceilingLength
                                  2^           Raise 2 to that power, call it PN
                         ,:;                    JoinLink A and B as separatea rows
pair of boxed arrays
                          {."1~&>~             PadFor each row with zeros to length Pbox
                           f@{.                  Take theN FFTvalues, ofextending eachwith rowzeros
                   [:  */   f@                   Multiply theApply rowsFFT togetherto elementwiseit
                     +@    [:  */                  Take the conjugate ofReduce eachusing valuemultiplication
            [: f            +@                   Take the FFT of that listConjugate
                 #       f                      Get the length of the list (equal toApply P)FFT
                %                              Divide each by P
         #             #                        Get the lengths of A and BLength
       +&      9 o.                              Take Sumthe themreal togetherpart
    <:@           #                             Decrement it
      Get the lengths of {.A and B
   +&                              Take that many values from the previousSum listthem
9 o.           <:@                                Take the real part of each valueDecrement
            $                                  Shape Returnto that list aslength theand resultreturn

J, 110 104 95 89 bytes, O(n log n)

f=:([:((+,-)(%_1^i.@#%#))&f/@|:_2]\])^:(1<#)
9:o.<:@+&#{.[:(f%#)[:+@*/,:f@{."1~2^#@#:@+&#

   f =: ([:((+,-)(%_1^i.@#%#))&f/@|:_2]\])^:(1<#)
   g =: 9:o.<:@+&#{.[:(f%#)[:+@*/,:f@{."1~2^#@#:@+&#
   1 2 3 4 g 5 6 7 8
5 16 34 60 61 52 32
   2 4 5 6 1 g 1 2 4 7
2 8 21 46 61 61 46 7

Explanation (Outdated)

9 o.<:@+&#{.[:(f%#)[:+@*/,:f@{."1~2^2>.@^.+&#  Input: A on LHS, B on RHS
                                            #  Get the lengths of A and B
                                          +&   Sum them
                                    2   ^.     Find log base 2 of it
                                     >.@       Find its ceiling
                                  2^           Raise 2 to that power, call it P
                         ,:                    Join A and B as separate rows
                             {."1~             Pad each row with zeros to length P
                           f@                  Take the FFT of each row
                   [:  */                      Multiply the rows together elementwise
                     +@                        Take the conjugate of each value
            [: f                               Take the FFT of that list
                 #                             Get the length of the list (equal to P)
                %                              Divide each by P
         #                                     Get the lengths of A and B
       +&                                      Sum them together
    <:@                                        Decrement it
          {.                                   Take that many values from the previous list
9 o.                                           Take the real part of each value
                                               Return that list as the result

J, 79 bytes, O(n log n)

f=:_2&(0((+,-)]%_1^i.@#%#)&f/@|:]\)~1<#
<:@+&#$9(o.f%#)[:+@*/;f@{.&>~2^#@#:@+&#

   f =: _2&(0((+,-)]%_1^i.@#%#)&f/@|:]\)~1<#
   g =: <:@+&#$9(o.f%#)[:+@*/;f@{.&>~2^#@#:@+&#
   1 2 3 4 g 5 6 7 8
5 16 34 60 61 52 32
   2 4 5 6 1 g 1 2 4 7
2 8 21 46 61 61 46 7

Try it online!

Explanation

<:@+&#$9(o.f%#)[:+@*/;f@{.&>~2^#@#:@+&#  Input: A on LHS, B on RHS
                                      #  Get the lengths of A and B
                                    +&   Sum them
                                 #:@     Get list of binary digits
                               #@        Length
                             2^           Raise 2 to that power, call it N
                     ;                    Link A and B as a pair of boxed arrays
                          &>~             For each box
                        {.                  Take N values, extending with zeros
                      f@                    Apply FFT to it
               [:  */                    Reduce using multiplication
                 +@                      Conjugate
           f                             Apply FFT
            %                            Divide by
             #                           Length
       9 o.                              Take the real part
     #                                   Get the lengths of A and B
   +&                                    Sum them
<:@                                      Decrement
      $                                  Shape to that length and return

replaced http://codegolf.stackexchange.com/ with https://codegolf.stackexchange.com/

Source Link

edited Apr 13, 2017 at 12:38

Community Bot

1

I used the FFT implementation from a previous solution solution. That implementation uses the Cooley-Tukey algorithm for sequences where the length is a power of 2. Therefore, I have to zero-pad the input sequences to the a power of 2 (typically the minimal value that is valid) such that their lengths are greater than or equal to the sum of the lengths of the input sequences.

An explanation for the FFT portion in J is included in my previous solution solution to a different challenge.

added 9 characters in body

Source Link

edited Oct 14, 2016 at 8:43

miles

17k
2
30
94

J, 110 104 9595 89 bytes, O(n log n)

f=:((#~[:((+,-)(%_1^i.@#%#))&f(#~-.))1:`0/@|:\_2]\])^:(1<#)
9 :o.<:@+&#{.[:(f%#)[:+@*/,:f@{."1~2^2>.@^.+&#"1~2^#@#:@+&#

   f =: ((#~[:((+,-)(%_1^i.@#%#))&f(#~-.))1:`0/@|:\_2]\])^:(1<#)
   g =: 9 :o.<:@+&#{.[:(f%#)[:+@*/,:f@{."1~2^2>.@^.+&#"1~2^#@#:@+&#
   1 2 3 4 g 5 6 7 8
5 16 34 60 61 52 32
   2 4 5 6 1 g 1 2 4 7
2 8 21 46 61 61 46 7

Explanation (Outdated)

J, 110 104 95 bytes, O(n log n)

f=:((#~((+,-)(%_1^i.@#%#))&f(#~-.))1:`0:\)^:(1<#)
9 o.<:@+&#{.[:(f%#)[:+@*/,:f@{."1~2^2>.@^.+&#

   f =: ((#~((+,-)(%_1^i.@#%#))&f(#~-.))1:`0:\)^:(1<#)
   g =: 9 o.<:@+&#{.[:(f%#)[:+@*/,:f@{."1~2^2>.@^.+&#
   1 2 3 4 g 5 6 7 8
5 16 34 60 61 52 32
   2 4 5 6 1 g 1 2 4 7
2 8 21 46 61 61 46 7

Explanation

J, 110 104 95 89 bytes, O(n log n)

f=:([:((+,-)(%_1^i.@#%#))&f/@|:_2]\])^:(1<#)
9:o.<:@+&#{.[:(f%#)[:+@*/,:f@{."1~2^#@#:@+&#

   f =: ([:((+,-)(%_1^i.@#%#))&f/@|:_2]\])^:(1<#)
   g =: 9:o.<:@+&#{.[:(f%#)[:+@*/,:f@{."1~2^#@#:@+&#
   1 2 3 4 g 5 6 7 8
5 16 34 60 61 52 32
   2 4 5 6 1 g 1 2 4 7
2 8 21 46 61 61 46 7

Explanation (Outdated)

deleted 158 characters in body

Source Link

edited Jul 23, 2016 at 11:58

miles

17k
2
30
94

Loading

added 49 characters in body

Source Link

edited Jun 19, 2016 at 10:20

miles

17k
2
30
94

Loading

Source Link

created Jun 18, 2016 at 21:52

miles

17k
2
30
94

Loading

Stack Exchange Network

Return to Answer

J, 110 104 95 8979 bytes, OO(nn log nn)

Explanation (Outdated)

J, 110 104 95 89 bytes, O(n log n)

Explanation (Outdated)

J, 79 bytes, O(n log n)

Explanation

J, 110 104 9595 89 bytes, O(n log n)

Explanation (Outdated)

J, 110 104 95 bytes, O(n log n)

Explanation

J, 110 104 95 89 bytes, O(n log n)

Explanation (Outdated)