Sequence

Sequence

Sequence在英文當中是「一連串」的意思,在數學當中則是「一連串數字」的意思,中文譯作「數列」。

(4 -1 6 0 9)

Sequence運算

數學家談數列,是談等差數列、等比數列、數列求和。計算學家談數列,則是談微分、積分、排序、搜尋。

加減乘除

對應項加減乘除。

加法 (1 2 3) + (4 5 6) = (1+4 2+5 3+6) = (5 7 9)

微分、積分

請見本站文件「Sequence」。

微分 (4 -1 6 0 9) -> (4 -5 7 -6 9)
積分 (4 -1 6 0 9) -> (4 3 9 9 18)

最小值、最大值、總和

靜態版本請見本站文件「Maximum Sum Subarray」。

動態版本請見本站文件「Sequence」。

最小值 (4 -1 6 0 9) -> -1
最大值 (4 -1 6 0 9) -> 9
總和   (4 -1 6 0 9) -> 18

排序、搜尋、選擇、計數

請見本站文件「Sequence」。

排序 (4 -1 6 0 9) -> (-1 0 4 6 9)
搜尋 (4 -1 6 0 9) , 0 -> 3
選擇 (4 -1 6 0 9) , 0 -> -1
計數 (4 -1 6 0 9) , 0 -> 1

數列搜尋

請見本站文件「String Searching」。

數列搜尋 (4 -1 6 0 9) , (0 9) -> 3

排列、組合

請見本站文件「Permutation」。

排列 (4 -1 6 0 9) -> (6 0 9 -1 4)
組合 (4 -1 6 0 9) -> (-1 0 9)

點積、摺積

點積 (1 2 3) · (4 5 6) = 1×4 + 2×5 + 3×6 = 32
摺積 (1 2 3 4 5) ∗ (4 5 6) = (4 13 28 43 58 49 30)

(- - 1 2 3 4 5 - -) · (6 5 4 - - - - - -) = 4
(- - 1 2 3 4 5 - -) · (- 6 5 4 - - - - -) = 13
(- - 1 2 3 4 5 - -) · (- - 6 5 4 - - - -) = 28
(- - 1 2 3 4 5 - -) · (- - - 6 5 4 - - -) = 43
(- - 1 2 3 4 5 - -) · (- - - - 6 5 4 - -) = 58
(- - 1 2 3 4 5 - -) · (- - - - - 6 5 4 -) = 49
(- - 1 2 3 4 5 - -) · (- - - - - - 6 5 4) = 30

Convolution(Under Construction!)

Convolution

pairwise binding (+/x), pairwise operation (x), merge operation (+)
+x+: linear convolution      fft/fnt
xx+: dirichlet convolution   brute force     mobius, ui principle, ...
      additive convolution:加法結合,數值相乘,加法累計。
        dyadic convolution:AND/OR/XOR結合,數值相乘,加法累計。
multiplicative convolution:乘法結合,數值相乘,加法累計。
       infimal convolution:加法結合,函數加法,下界累計。Minkowski sum。

Additive Convolution(Under Construction!)

Additive Convolution(Linear Convolution)

演算法(Fast Fourier Transform)

演算法(Fast Number Theoretic Transform)

Dyadic Convolution(Under Construction!)

Dyadic Convolution

結合運算是位元運算,例如AND、OR、XOR。

矩陣形式是Hadamard matrix或Walsh matrix。數值都是±1而且向量互相垂直(點積為零)。

轉換名稱叫做Hadamard transform或Walsh transform。因為沒有循環,所以沒有對偶?

http://book.huihoo.com/pdf/algorithms-for-programmers/afp.pdf   p362 $9.6
http://iris.elf.stuba.sk/JEEEC/data/pdf/09-10_102-10.pdf
http://en.wikipedia.org/wiki/Hadamard_matrix
https://en.wikipedia.org/wiki/Dyadic_rational
http://www.jjj.de/fxt/fxtbook.pdf

演算法(Fast Walsh-Hadamard Transform)

Circular Convolution

Circular Convolution

數列、多項式、多項式函數!

數列循環摺積的高速演算法:O(NlogN)!

Duality: Circular Convolution ⟺ Multiplication

(2 -5 1 0 4)  <———>  2x⁰ - 5x¹ + 1x² + 0x³ + 4x⁴

數列與多項式互相轉換!

               2x⁰ - 5x¹ + 1x² + 0x³ + 4x⁴
(2 -5 1 0 4)  <———————————————————————————> (2 2 60 320 5192)
                   x = {0, 1, 2, 3, 6}

係數與函數值互相轉換!

正向轉換:多項式求值N回合O(N²)。

反向轉換:多項式內插O(N³)。

[ 0⁰ 0¹ 0² 0³ 0⁴ ] [  2 ]   [    2 ]
[ 1⁰ 1¹ 1² 1³ 1⁴ ] [ -5 ]   [    2 ]
[ 2⁰ 2¹ 2² 2³ 2⁴ ] [  1 ] = [   60 ]
[ 3⁰ 3¹ 3² 3³ 3⁴ ] [  0 ]   [  320 ]
[ 6⁰ 6¹ 6² 6³ 6⁴ ] [  4 ]   [ 5192 ]

改寫成矩陣形式。稱做Vandermonde Matrix。

正向轉換:矩陣求值O(N²)。

反向轉換:先求反矩陣O(N³),再求值O(N²)。

    [ x₀⁰ x₀¹ x₀² x₀³ ] [  2 ]   [ y₀ ]
 1  [ x₁⁰ x₁¹ x₁² x₁³ ] [ -5 ]   [ y₁ ]
——— [ x₂⁰ x₂¹ x₂² x₂³ ] [  1 ] = [ y₂ ]
 k  [ x₃⁰ x₃¹ x₃² x₃³ ] [  0 ]   [ y₃ ]

Fourier transform:
x = {e-i⋅(2π/N)⋅0, e-i⋅(2π/N)⋅1, ..., e-i⋅(2π/N)⋅(N-1)}
e = Euler number
k = 1 / √n

number theoretic transform:
x = {r⁰, r¹, ……, rN-1}
r = anyone primitive root 
k = 1

x設定成特殊數值,矩陣邊長恰是2的次方,有高速演算法!

已知兩種設定方式:複數系統傅立葉轉換、餘數系統數論轉換。

正向轉換:O(NlogN)。

反向轉換:O(NlogN)。

               2x⁰ - 5x¹ + 1x² + 0x³ + 4x⁴
(2 -5 1 0 4)  <———————————————————————————> (2 2 60 320 5192)
     ∗         1x⁰ - 1x¹ + 0x² + 1x³ + 2x⁴          ×
(1 -1 0 1 -2) <———————————————————————————> (1 -1 -25 -137 -2381)
               2x⁰ - 7x¹ + 6x² + 1x³ - 5x⁴
     ‖         + 7x⁵ - 2x⁶ + 4x⁷ - 8x⁸              ‖
(2 -7 6 1 -5  <———————————————————————————> (2 -2 -1500 -43840 -12362152)
 7 -2 4 -8)        x = {0, 1, 2, 3, 6}

係數與函數值互相轉換之特色:

一、係數加減=多項式加減=函數值加減。(這不是重點)

二、係數摺積與反摺積=多項式乘除=函數值乘除。

               (2x⁰-5x¹+1x²+0x³+4x⁴) ÷ √5
(2 -5 1 0 4)  <——————————————————————————> (0.8, 3.5-0.7i, 0.5+3.0i,
                                            0.5-3.0i, 3.5+0.7i)
      ×        (1x⁰-1x¹+0x²+1x³+2x⁴) ÷ √5             ⊛
(1 -1 0 1 -2) <——————————————————————————> (-0.4, -0.2-0.2i, -1.7+0.4i,
                                            -1.7-0.4i, -0.2+0.2i)
      ‖        (2x⁰+5x¹+0x²+0x³-8x⁴) ÷ √5             ‖
(2 5 0 0 -8)  <——————————————————————————> (-0.4, -5.1+2.1i, -3.6-1.6i,
               x = {e-i⋅(2π/5)⋅0, e-i⋅(2π/5)⋅1   -3.6+1.6i, -5.1-2.1i)
                    e-i⋅(2π/5)⋅2, e-i⋅(2π/5)⋅3
                    e-i⋅(2π/5)⋅4}

係數摺積=函數值乘法。

如果是對偶轉換(正向轉換=反向轉換),那麼性質就對稱了:係數乘法=函數值摺積。

改成對偶轉換,目前沒有辦法。改成幾乎是對偶變換,則有一種辦法:令多項式次方循環。

已知兩種設定方式:複數系統傅立葉轉換、餘數系統數論轉換。

多項式次方循環,導致性質稍有變化:

一、係數頭尾循環=多項式次方循環=函數值頭尾循環。

二、係數循環摺積=函數值乘法。

三、係數乘法=函數值循環摺積。

            fft
(2 -5 1 0) —————> (? ? ? ?)
     ⊛      fft       ×
(1 -1 0 1) —————> (? ? ? ?)
     ‖      ifft      ↓
(? ? ? ?)  <————— (? ? ? ?)

當數列長度恰是2的次方,循環摺積有高速演算法!

循環摺積:正向傅立葉轉換、相乘、逆向傅立葉轉換。

總時間複雜度O(NlogN)。

以上只是綱要。以下則是細節。

點積、摺積、循環摺積

點積是對應項相乘,然後加總。

(a₀ a₁ a₂) dot (b₀ b₁ b₂) = a₀b₀ + a₁b₁ + a₂b₂

摺積是很多次點積。

第二串數列頭尾顛倒,窮舉各種對齊方式,各做一次點積。

第二串數列頭尾顛倒,是為了配合多項式乘法。

數列摺積
  (a₀ a₁ a₂) convolution (b₀ b₁ b₂) = (c₀ c₁ c₂)

其中
c₀ = a₀b₀
c₁ = a₀b₁ + a₁b₀
c₂ = a₀b₂ + a₁b₁ + a₂b₀
c₃ = a₁b₂ + a₂b₁
c₄ = a₂b₂

直式
c₀:                     c₁:                     c₂:
(-  -  a₀ a₁ a₂ -  - )  (-  -  a₀ a₁ a₂ -  - )  (-  -  a₀ a₁ a₂ -  - )
(b₂ b₁ b₀ -  -  -  - )  (-  b₂ b₁ b₀ -  -  - )  (-  -  b₂ b₁ b₀ -  - )

c₃:                     c₄:
(-  -  a₀ a₁ a₂ -  - )  (-  -  a₀ a₁ a₂ -  - )
(-  -  -  b₂ b₁ b₀ - )  (-  -  -  -  b₂ b₁ b₀)

橫式
c₀ = (-  -  a₀ a₁ a₂ -  - ) dot (b₂ b₁ b₀ -  -  -  - )
c₁ = (-  -  a₀ a₁ a₂ -  - ) dot (-  b₂ b₁ b₀ -  -  - )
c₂ = (-  -  a₀ a₁ a₂ -  - ) dot (-  -  b₂ b₁ b₀ -  - )
c₃ = (-  -  a₀ a₁ a₂ -  - ) dot (-  -  -  b₂ b₁ b₀ - )
c₄ = (-  -  a₀ a₁ a₂ -  - ) dot (-  -  -  -  b₂ b₁ b₀)

循環摺積,超出數列的部分,改成頭尾循環。

                  circular
(a₀ a₁ a₂ a₃ a₄) convolution (b₀ b₁ b₂ b₃ b₄) = (c₀ c₁ c₂ c₃ c₄)

直式
c₀:               c₁:               c₂:
(a₀ a₁ a₂ a₃ a₄)  (a₀ a₁ a₂ a₃ a₄)  (a₀ a₁ a₂ a₃ a₄)
(b₀ b₄ b₃ b₂ b₁)  (b₁ b₀ b₄ b₃ b₂)  (b₂ b₁ b₀ b₄ b₃)

c₃:               c₄:
(a₀ a₁ a₂ a₃ a₄)  (a₀ a₁ a₂ a₃ a₄)
(b₃ b₂ b₁ b₀ b₄)  (b₄ b₃ b₂ b₁ b₀)

橫式
c₀ = (a₀ a₁ a₂ a₃ a₄) dot (b₀ b₄ b₃ b₂ b₁)
c₁ = (a₀ a₁ a₂ a₃ a₄) dot (b₁ b₀ b₄ b₃ b₂)
c₂ = (a₀ a₁ a₂ a₃ a₄) dot (b₂ b₁ b₀ b₄ b₃)
c₃ = (a₀ a₁ a₂ a₃ a₄) dot (b₃ b₂ b₁ b₀ b₄)
c₄ = (a₀ a₁ a₂ a₃ a₄) dot (b₄ b₃ b₂ b₁ b₀)

數列=多項式

(a₀ a₁ a₂)   <--->   a₀x⁰ + a₁x¹ + a₂x²

數列加法與減法=多項式加法與減法

數列加法
(a₀ a₁ a₂) + (b₀ b₁ b₂) = (a₀+b₀ a₁+b₁ a₂+b₂)
多項式加法
        a₀ x⁰ +       a₁ x¹ +       a₂ x²
+)      b₀ x⁰ +       b₁ x¹ +       b₂ x²
—————————————————————————————————————————
   (a₀+b₀) x⁰ +  (a₁+b₁) x¹ +  (a₂+b₂) x²

數列摺積與反摺積=多項式乘法與除法

多項式乘法
                         a₀ x⁰ +   a₁ x¹ +   a₂ x²
×)                       b₀ x⁰ +   b₁ x¹ +   b₂ x²
——————————————————————————————————————————————————
                       a₀b₂ x² + a₁b₂ x³ + a₂b₂ x⁴
             a₀b₁ x¹ + a₁b₁ x² + a₂b₁ x³
   a₀b₀ x⁰ + a₁b₀ x¹ + a₂b₀ x²
——————————————————————————————————————————————————
     c₀ x⁰ +   c₁ x¹ +   c₂ x² +   c₃ x³ +   c₄ x⁴
數列摺積
(a₀ a₁ a₂) convolution (b₀ b₁ b₂) = (c₀ c₁ c₂ c₃ c₄)
其中
c₀ = a₀b₀
c₁ = a₀b₁ + a₁b₀
c₂ = a₀b₂ + a₁b₁ + a₂b₀
c₃ = a₁b₂ + a₂b₁
c₄ = a₂b₂

直式
c₀:                     c₁:                     c₂:
(-  -  a₀ a₁ a₂ -  - )  (-  -  a₀ a₁ a₂ -  - )  (-  -  a₀ a₁ a₂ -  - )
(b₂ b₁ b₀ -  -  -  - )  (-  b₂ b₁ b₀ -  -  - )  (-  -  b₂ b₁ b₀ -  - )

c₃:                     c₄:
(-  -  a₀ a₁ a₂ -  - )  (-  -  a₀ a₁ a₂ -  - )
(-  -  -  b₂ b₁ b₀ - )  (-  -  -  -  b₂ b₁ b₀)

橫式
c₀ = (-  -  a₀ a₁ a₂ -  - ) dot (b₂ b₁ b₀ -  -  -  - )
c₁ = (-  -  a₀ a₁ a₂ -  - ) dot (-  b₂ b₁ b₀ -  -  - )
c₂ = (-  -  a₀ a₁ a₂ -  - ) dot (-  -  b₂ b₁ b₀ -  - )
c₃ = (-  -  a₀ a₁ a₂ -  - ) dot (-  -  -  b₂ b₁ b₀ - )
c₄ = (-  -  a₀ a₁ a₂ -  - ) dot (-  -  -  -  b₂ b₁ b₀)

數列循環摺積=多項式循環乘法

多項式循環乘法
                         a₀ x⁰ +   a₁ x¹ +   a₂ x²
×)                       b₀ x⁰ +   b₁ x¹ +   b₂ x²
—————————————————————————————————————————————————————
                       a₀b₂ x² + a₁b₂ x³ + a₂b₂ x⁴
             a₀b₁ x¹ + a₁b₁ x² + a₂b₁ x³
   a₀b₀ x⁰ + a₁b₀ x¹ + a₂b₀ x²
—————————————————————————————————————————————————————
   a₁b₂ x⁰ + a₂b₂ x¹ + a₀b₂ x²
   a₂b₁ x⁰ + a₀b₁ x¹ + a₁b₁ x²
   a₀b₀ x⁰ + a₁b₀ x¹ + a₂b₀ x²
—————————————————————————————————————————————————————
     c₀ x⁰ +   c₁ x¹ +   c₂ x²
數列循環摺積
(a₀ a₁ a₂) circular convolution (b₀ b₁ b₂) = (c₀ c₁ c₂)
其中
c₀ = a₁b₂ + a₂b₁ + a₀b₀
c₁ = a₂b₂ + a₀b₁ + a₁b₀
c₂ = a₀b₂ + a₁b₁ + a₂b₀

直式
c₀:         c₁:         c₂:
(a₀ a₁ a₂)  (a₀ a₁ a₂)  (a₀ a₁ a₂)
(b₀ b₂ b₁)  (b₁ b₀ b₂)  (b₂ b₁ b₀)

橫式
c₀ = (a₀ a₁ a₂) dot (b₀ b₂ b₁)
c₁ = (a₀ a₁ a₂) dot (b₁ b₀ b₂)
c₂ = (a₀ a₁ a₂) dot (b₂ b₁ b₀)

Convolution Theorem【尚無正式名稱】

數列轉換成多項式。

(a₀ a₁ a₂)  ---->  a₀x⁰ + a₁x¹ + a₂x²

數列轉換成多項式,可以看成點積,可以看成線性函數。

線性函數的矩陣
A = [ x⁰ x¹ x² ]

數列
    [ a₀ ]
a = [ a₁ ]
    [ a₂ ]

數列轉換成多項式
                  [ a₀ ]
Aa = [ x⁰ x¹ x² ] [ a₁ ] = a₀x⁰ + a₁x¹ + a₂x²
                  [ a₂ ]

這種線性函數有個特性:變換前的摺積=變換後的乘法。

A = [ x⁰ x¹ x² ]

    [ a₀ ]       [ b₀ ]
a = [ a₁ ]   b = [ b₁ ]
    [ a₂ ]       [ b₂ ]

p = Aa = (a₀x⁰ + a₁x¹ + a₂x²)
q = Ab = (b₀x⁰ + b₁x¹ + b₂x²)

pq = Aa Ab = (a₀x⁰ + a₁x¹ + a₂x²) (b₀x⁰ + b₁x¹ + b₂x²)
           = (a convolution b) 然後添上 [ x⁰ x¹ x² x³ x⁴ ]
           = A(a convolution b)    a與b末端補零,A末端補項。

次方值乘上任意倍率,此特性一樣成立。

A = [ x⁰ x¹ x² ]

A = [ x⁰ x⁵ x¹⁰ ]

A = [ x⁰ x⁻⁷ x⁻²¹ ]

A = [ x⁰ x⁰ x⁰ ]

所有元素一齊乘上任意倍率,此特性一樣成立。

A = [ 7x⁰ 7x¹ 7x² ]

A = [ -x⁰ -x⁵ -x¹⁰ ]

A = [ 0 0 0 ]

從一個橫列推廣到一個矩陣,此特性一樣成立。

    [ 7x⁰ 7x¹  7x²   ]
A = [ -x⁰ -x⁵  -x¹⁰  ]
    [  x⁰  x⁻⁷  x⁻²¹ ]

Aa multiply Ab = A(a convolution b)

結論就是:

Circular Convolution Theorem【尚無正式名稱】

接下來繼續補強矩陣,除了滿足「變換前的摺積=變換後的乘法」,也要滿足「變換前的乘法=變換後的摺積」!

從數學來看,補強性質,達成了對稱之美;從計算學來看,補強限制,極可能產生特殊演算法。

那麼就得讓A擁有反矩陣A⁻¹,而且A和A⁻¹都具備上個段落提到的特性。一種嘗試是正規正交矩陣:A⁻¹ = Aᵀ,前述特性變成了行與列同時成立,容易觀察。

實數系統下,x次方漸增,數值越來越大,導致基底不可能垂直(內積不可能為零)。很不幸的,這種矩陣不存在。

             [ x⁰ x⁰ x⁰ x⁰ .. ]
     -1   T  [ x⁰ x¹ x² x³ .. ]
A = A  = A = [ x⁰ x² x⁴ x⁶ .. ]
             [ x⁰ x³ x⁶ x⁹ .. ]
             [ :  :  :  :     ]

Aa multiply Ab = A(a convolution b)
Aa convolution Ab = A(a multiply b)

折衷的方式是令x的次方產生循環,讓數值能夠變小,使得基底互相垂直、內積是零。(用數學術語來說:從open set改成closed set。)

複數系統下,把x設定成ei⋅2π/N(或其倒數e-i⋅2π/N),令x的次方產生循環。此即「傅立葉轉換」。

Fourier Transform: x = e-i⋅2π/N; k = 1/sqrt(N); N is size of matrix

      [ x⁰ x⁰ x⁰ x⁰ .. ]          [ x⁻⁰ x⁻⁰ x⁻⁰ x⁻⁰ .. ]
      [ x⁰ x¹ x² x³ .. ]    -1    [ x⁻⁰ x⁻¹ x⁻² x⁻³ .. ]
A = k [ x⁰ x² x⁴ x⁶ .. ]   A  = k [ x⁻⁰ x⁻² x⁻⁴ x⁻⁶ .. ]
      [ x⁰ x³ x⁶ x⁹ .. ]          [ x⁻⁰ x⁻³ x⁻⁶ x⁻⁹ .. ]
      [ :  :  :  :     ]          [ :   :   :   :      ]

Aa multiply Ab = A(a circular convolution b)
Aa circular convolution Ab = A(a multiply b)

餘數系統下,則是把x設定成任意一個原根(或其倒數),令x的次方產生循環。此即「數論轉換」。

Number Theoretic Transform: x = primitive root (mod n)

    [ x⁰ x⁰ x⁰ x⁰ .. ]        [ x⁻⁰ x⁻⁰ x⁻⁰ x⁻⁰ .. ]
    [ x⁰ x¹ x² x³ .. ]    -1  [ x⁻⁰ x⁻¹ x⁻² x⁻³ .. ]
A = [ x⁰ x² x⁴ x⁶ .. ]   A  = [ x⁻⁰ x⁻² x⁻⁴ x⁻⁶ .. ]
    [ x⁰ x³ x⁶ x⁹ .. ]        [ x⁻⁰ x⁻³ x⁻⁶ x⁻⁹ .. ]
    [ :  :  :  :     ]        [ :   :   :   :      ]

Aa multiply Ab = A(a circular convolution b)
Aa circular convolution Ab = A(a multiply b)

原本的特性,也變得循環:「變換前的循環摺積=變換後的乘法」、「變換前的乘法=變換後的循環摺積」!

引入時域與頻域的觀念:「頻域的乘法=時域的循環摺積」、「頻域的循環摺積=時域的乘法」!

Fourier Transform

請見本站文件「Fourier Transform」。

Number Theoretic Transform

http://www.apfloat.org/prim.html

數論轉換是雙射函數,輸入和輸出都是一串餘數。

輸入輸出的每個數值都是餘數,皆大於等於零、小於模數。當輸入數值很大,那麼模數也必須足夠大。

數論轉換的特色是完全沒有浮點數誤差!

Circular Convolution快速演算法
Polynomial Circular Multiplication快速演算法

正向傅立葉轉換、數論轉換需時O(NlogN),對應項相乘需時O(N),逆向傅立葉轉換、數論轉換需時O(NlogN)。總時間複雜度為O(NlogN)。

傅立葉轉換的弱點是浮點數誤差。數論轉換的弱點是數值大小不得超過模數大小。

注意到,快速傅立葉轉換、快速數論轉換,數列長度必須是2的次方。當數列長度不是2的次方,千萬不能直接補零到2的次方。

正確的循環摺積計算結果:
            circular
(a₀ a₁ a₂) convolution (b₀ b₁ b₂) = (c₀ c₁ c₂)

c₀ = a₀b₀ + a₁b₂ + a₂b₁
c₁ = a₀b₁ + a₁b₀ + a₂b₂
c₂ = a₀b₂ + a₁b₁ + a₂b₀

長度補到2的次方,計算結果完全不同:
              circular
(a₀ a₁ a₂ 0) convolution (b₀ b₁ b₂ 0) = (d₀ d₁ d₂ d₃)

d₀ = a₀b₀ + a₂b₂
d₁ = a₀b₁ + a₁b₀
d₂ = a₀b₂ + a₁b₁ + a₂b₀
d₃ = a₁b₂ + a₂b₁

正確的方式:先補零直到不受循環影響,再補零直到長度是2的次方,最後讓輸出數列循環。

想要計算      circular
  (a₀ a₁ a₂) convolution (b₀ b₁ b₂) = (c₀ c₁ c₂)

改為計算          circular
 (a₀ a₁ a₂ 0 0) convolution (b₀ b₁ b₂ 0 0) = (d₀ d₁ d₂ d₃ d₄)

長度補到2的次方         circular
 (a₀ a₁ a₂ 0 0 0 0 0) convolution (b₀ b₁ b₂ 0 0 0 0 0)
= (d₀ d₁ d₂ d₃ d₄ 0 0 0)

最後讓輸出數列循環
  c₀ = d₀ + d₃
  c₁ = d₁ + d₄
  c₂ = d₂

Convolution快速演算法
Polynomial Multiplication快速演算法

運用循環摺積,計算摺積。

想要計算
  (a₀ a₁ a₂ a₃) convolution (b₀ b₁ b₂)
= (c₀ c₁ c₂ c₃ c₄ c₅)

改為計算             circular
  (a₀ a₁ a₂ a₃ 0 0) convolution (b₀ b₁ b₂ 0 0 0)
= (c₀ c₁ c₂ c₃ c₄ c₅ 0)

長度補到2的次方          circular
  (a₀ a₁ a₂ a₃ 0 0 0 0) convolution (b₀ b₁ b₂ 0 0 0 0 0)
= (c₀ c₁ c₂ c₃ c₄ c₅ 0 0)

截斷輸出數列至正確長度
  (c₀ c₁ c₂ c₃ c₄ c₅ 0 0) -> (c₀ c₁ c₂ c₃ c₄ c₅)

範例:大數乘法

大數乘法即是多項式乘法!

傅立葉轉換、數論轉換得以計算大數乘法,時間複雜度從O(N²)降為O(NlogN)。

範例:兩兩和(Pairwise Sum)(X+Y Problem)

甲集合、乙集合,只有整數。甲取一個數,乙取一個數,相加,會是哪些數?

集合資料結構是循序儲存:窮舉。O(N²)。

集合資料結構是索引儲存:摺積。O(RlogR)。R為數字範圍。

多項式觀點:整數是指數,該整數出現與否(未出現0,出現>0)是係數,兩兩和是多項式乘法。

摺積觀點:整數是索引值,相加是索引值位移,兩兩和是摺積。

範例:組合計數(Combination Counting)

蓮霧2顆、椪柑3顆、芭樂5顆。欲在盤中擺放6顆水果,有幾種方式?

(x⁰+x¹+x²)(x⁰+x¹+x²+x³)(x⁰+x¹+x²+x³+x⁴+x⁵),找到x⁶的係數。加是或、乘是且、次方是數量、係數是方式。原理如同兩兩和。

範例:數列搜尋(Sequence Searching)

經典問題「一條陣列,尋找一個值」,解法是循序搜尋、先排序再二分搜尋。

進階問題「一條陣列,尋找一串連續數列」,解法是字串搜尋、傅立葉轉換。此處討論傅立葉轉換。

兩串數列 a b
a = (1 2 3 4)
b = (1 3 5 7)

定義兩串數列 a b 的差距:對應項的差的平方的總和。
(1 - 1)² + (2 - 3)² + (3 - 5)² + (4 - 7)²

定義兩串數列 a b 的差距:對應項的差的平方的總和。
sum (a[i] - b[i])²

當差距等於零,則兩串數列相同。
sum (a[i] - b[i])² = 0  ---->  a = b

展開之後,重新整理,以數列為主角:數列每項平方和、數列點積。
  sum (a[i] - b[i])²
= sum (a[i]² + b[i]² - 2 a[i] b[i])
= sum a[i]² + sum b[i]² - 2 sum a[i] b[i]

縮寫。
(a - b)² = a² + b² - 2 (a · b)
兩串數列
(1 2 3 4 5 6)
(3 4 5)

窮舉各種對齊方式,判斷是否相符。
(1 2 3 4 5 6)  (1 2 3 4 5 6)  (1 2 3 4 5 6)  (1 2 3 4 5 6)
 | | |            | | |            | | |            | | |
(3 4 5)          (3 4 5)          (3 4 5)          (3 4 5)

換句話說,判斷差距是否等於零。
        (a - b)²              a²         b²     2(a·b)
(1-3)² + (2-4)² + (3-5)² = 1²+2²+3² + 3²+4²+5² - 2×26 = 12
(2-3)² + (3-4)² + (4-5)² = 2²+3²+4² + 3²+4²+5² - 2×38 = 3
(3-3)² + (4-4)² + (5-5)² = 3²+4²+5² + 3²+4²+5² - 2×50 = 0  <--- here!
(4-3)² + (5-4)² + (6-5)² = 4²+5²+6² + 3²+4²+5² - 2×62 = 5
                           ^^^^^^^^                ^^
                           moving window           convolution

預先計算每個數字的平方、預先計算各種對齊方式的點積(就是摺積),就可以快速求得a² + b² - 2ab。時間複雜度O(NlogN)。

搜尋(找到零)、最相似(找最小值)、最相異(找最大值)。

UVa 12298 ICPC 4671 5705 7159

Multiplicative Convolution(Under Construction!)

Multiplicative Convolution(Dirichlet Convolution)

好像沒有快速演算法。

Multiplicative Function(Under Construction!)

乘性函數

constant function 1: 1(1) = 1(2) = ... = 1
identity function I: I(n) = n
divisor function τ: τ(n) = # of divisors of n
totient function φ: φ(n) = # of relative prime of n
1 ∗ 1 = σ₀ = τ   divisor count

φ ∗ 1 = I        x
I ∗ 1 = σ₁ = σ   divisor sum

ICPC 7837

單位元素、反元素

加性摺積當中,單位元素是脈衝函數δ。

impulse function δ: δ(0) = 1; δ(±1) = δ(±2) = ... = 0
f ∗ g = δ  g是加性摺積反元素

乘性摺積當中,單位元素是脈衝函數ε。

常數函數1的反元素是乘性排容函數Möbius function。

impulse function ε: ε(1) = 1; ε(2) = ε(3) = ... = 0
f ∗ g = ε  g是乘性摺積反元素
μ ∗ 1 = ε

演算法(Sieve)