ในทางคณิตศาสตร์วิธี FEEหรือวิธีประเมินฟังก์ชัน E อย่างรวดเร็วเป็นวิธีการหาผลรวมอย่างรวดเร็วของอนุกรมในรูปแบบพิเศษ วิธีนี้ถูกสร้างขึ้นในปี 1990 โดยEkaterina Karatsuba ^{[ 1 ] [ 2 ]}และได้รับการตั้งชื่อเช่นนี้เพราะทำให้การคำนวณฟังก์ชันE ของ Siegelเป็นไปได้อย่างรวดเร็ว โดยเฉพาะอย่างยิ่ง ${\displaystyle e^{x}}$

คาร์ล ลุดวิก ซีเกลได้ตั้งชื่อฟังก์ชันกลุ่มหนึ่งว่า "ฟังก์ชัน E" ซึ่งมีลักษณะ "คล้ายกับฟังก์ชันเลขชี้กำลัง" ^{[ 3 ]}ในบรรดาฟังก์ชันเหล่านี้มีฟังก์ชันพิเศษ ต่างๆ เช่นฟังก์ชันไฮเปอร์จีโอเมตริก ทรงกระบอก ฟังก์ชัน ทรงกลมและอื่นๆ

โดยใช้ FEE เราสามารถพิสูจน์ทฤษฎีบทต่อไปนี้ได้:

ทฤษฎีบท : ให้เป็นฟังก์ชันอดิศัยพื้นฐานนั่นคือฟังก์ชันเลขชี้กำลังหรือ ฟังก์ชันตรีโกณมิติหรือฟังก์ชันพีชคณิตพื้นฐานหรือผลรวมของฟังก์ชันเหล่านั้น หรือฟังก์ชัน ผกผันของฟังก์ชันเหล่านั้น หรือผลรวมของฟังก์ชันผกผันเหล่านั้น แล้ว ${\displaystyle y=f(x)}$

${\displaystyle s_{f}(n)=O(M(n)\log ^{2}n).\,}$

นี่คือความซับซ้อนของการคำนวณ (บิต)ของฟังก์ชันที่มีความแม่นยำถึงหลักหลักซึ่งเป็นความซับซ้อนของการคูณจำนวนเต็มสองหลัก ${\displaystyle s_{f}(n)}$${\displaystyle f(x)}$${\displaystyle n}$${\displaystyle M(n)}$${\displaystyle n}$

อัลกอริทึมที่ใช้ตามวิธี FEE ประกอบด้วยอัลกอริทึมสำหรับการคำนวณอย่างรวดเร็วของฟังก์ชันทรานสเซนเดนทัลพื้นฐาน ใดๆ สำหรับค่าอาร์กิวเมนต์ใดๆ ค่าคงที่คลาสสิกe ค่าคงที่ออยเลอร์ค่า คง ที่คาตาลันและค่าคงที่อาเปรี [ ^{4 ]}ฟังก์ชันทรานสเซนเดนทัลระดับสูง เช่นฟังก์ชันแกมมาออย เลอร์ และ^{อนุพันธ์} ฟังก์ชัน ไฮเปอร์จี โอเมตริก ^{[ 5 ]} ฟังก์ชันทรงกลม ฟังก์ชัน ทรง กระบอก ( รวมถึง ฟังก์ชัน เบสเซล ) ^{[ 6 ]}และฟังก์ชันอื่นๆ สำหรับ ค่า พีชคณิตของอาร์กิวเมนต์และพารามิเตอร์ฟังก์ชันซีตาของรีมันน์สำหรับ ค่า จำนวนเต็มของอาร์กิวเมนต์^{[ 7 ] [ 8 ]}และฟังก์ชันซีตาของฮูร์วิตซ์สำหรับอาร์กิวเมนต์จำนวนเต็มและค่าพีชคณิตของพารามิเตอร์^{[ 9 ]}และอินทิกรัลพิเศษ เช่น อินทิกรัลของความน่าจะเป็น อินทิกรัลเฟรสเนลฟังก์ชันเลขชี้กำลังอินทิกรัลอิน ทิกรั ลตรีโกณมิติและอินทิกรัลอื่นๆ^{[ 10 ]}สำหรับค่าพีชคณิตของอาร์กิวเมนต์ด้วย ขอบเขตความซับซ้อนที่ใกล้เคียงกับค่าที่เหมาะสมที่สุด กล่าวคือ ${\displaystyle \pi ,}$${\displaystyle \gamma ,}$

${\displaystyle s_{f}(n)=O(M(n)\log ^{2}n).\,}$

FEE ทำให้สามารถคำนวณค่าของฟังก์ชันจากคลาสของฟังก์ชันเหนือธรรมชาติระดับสูงได้อย่างรวดเร็ว^{[ 11 ]} รวมถึง อินทิกรัลพิเศษบางอย่างของฟิสิกส์คณิตศาสตร์และค่าคงที่แบบคลาสสิก เช่น ค่าคงที่ของออยเลอร์ ค่าคงที่ของคาตาลัน^{[ 12 ]}และค่าคงที่ของอาเปรี ข้อดีเพิ่มเติมของวิธี FEE คือความเป็นไปได้ในการประมวลผลแบบขนานของอัลกอริธึมที่ใช้ FEE

สำหรับการประเมินค่าคงที่อย่างรวดเร็วสามารถใช้สูตรคล้ายของ Machin และใช้ FEE ในการรวมอนุกรมเทย์เลอร์ได้ ${\displaystyle \pi ,}$${\displaystyle {\frac {\pi }{4}}=\arctan {\frac {1}{2}}+\arctan {\frac {1}{3}},}$

${\displaystyle \arctan {\frac {1}{2}}={\frac {1}{1\cdot 2}}-{\frac {1}{3\cdot 2^{3}}}+\cdots +{\frac {(-1)^{r-1}}{(2r-1)2^{2r-1}}}+R_{1},}$

${\displaystyle \arctan {\frac {1}{3}}={\frac {1}{1\cdot 3}}-{\frac {1}{3\cdot 3^{3}}}+\cdots +{\frac {(-1)^{r-1}}{(2r-1)3^{2r-1}}}+R_{2},}$

โดยมีเงื่อนไขที่เหลือซึ่งเป็นไปตามขอบเขตที่กำหนด ${\displaystyle R_{1},}$${\displaystyle R_{2},}$

${\displaystyle |R_{1}|\leq {\frac {4}{5}}{\frac {1}{2r+1}}{\frac {1}{2^{2r+1}}};}$

${\displaystyle |R_{2}|\leq {\frac {9}{10}}{\frac {1}{2r+1}}{\frac {1}{3^{2r+1}}};}$

และสำหรับ

${\displaystyle r=n,\,}$

${\displaystyle 4(|R_{1}|+|R_{2}|)\ <\ 2^{-n}.}$

ในการคำนวณ โดยใช้ FEE สามารถใช้การประมาณค่าอื่นๆ ได้เช่นกัน^{[ 13 ]}ในทุกกรณี ความซับซ้อนคือ ${\displaystyle \pi }$

${\displaystyle s_{\pi }=O(M(n)\log ^{2}n).\,}$

ในการคำนวณค่าคงที่แกมมาของออยเลอร์ด้วยความแม่นยำถึงระดับ หลักทศนิยม จำเป็นต้องบวกอนุกรมสองชุดเข้าด้วยกันโดยใช้ FEE กล่าวคือ สำหรับ ${\displaystyle n}$

${\displaystyle m=6n,\quad k=n,\quad k\geq 1,\,}$

${\displaystyle \gamma =-\log n\sum _{r=0}^{12n}{\frac {(-1)^{r}n^{r+1}}{(r+1)!}}+\sum _{r=0}^{12n}{\frac {(-1)^{r}n^{r+1}}{(r+1)!(r+1)}}+O(2^{-n}).}$

ความซับซ้อนคือ

${\displaystyle s_{\gamma }=O(M(n)\log ^{2}n).\,}$

เพื่อประเมินค่าคงที่อย่างรวดเร็ว สามารถใช้ FEE กับการประมาณค่าอื่นๆ ได้^{[ 14 ]}${\displaystyle \gamma }$

ด้วย FEE ระบบจะคำนวณอนุกรมข้อมูลสองชุดต่อไปนี้ได้อย่างรวดเร็ว:

${\displaystyle f_{1}=f_{1}(z)=\sum _{j=0}^{\infty }{\frac {a(j)}{b(j)}}z^{j},}$

${\displaystyle f_{2}=f_{2}(z)=\sum _{j=0}^{\infty }{\frac {a(j)}{b(j)}}{\frac {z^{j}}{j!}},}$

ภายใต้สมมติฐานว่าเป็นจำนวนเต็ม ${\displaystyle a(j),\quad b(j)}$

${\displaystyle |a(j)|+|b(j)|\leq (Cj)^{K};\quad |z|\ <\ 1;\quad K}$

และเป็นค่าคงที่ และเป็นจำนวนพีชคณิต ความซับซ้อนของการประเมินอนุกรมคือ ${\displaystyle C}$${\displaystyle z}$

${\displaystyle s_{f_{1}}(n)=O\left(M(n)\log ^{2}n\right),\,}$

${\displaystyle s_{f_{2}}(n)=O\left(M(n)\log n\right).}$

สำหรับการประเมินค่า คงที่ ให้ใช้ พจน์ของอนุกรมเทย์เลอร์${\displaystyle e}$${\displaystyle m=2^{k},\quad k\geq 1}$${\displaystyle e,}$

${\displaystyle e=1+{\frac {1}{1!}}+{\frac {1}{2!}}+\cdots +{\frac {1}{(m-1)!}}+R_{m}.}$

ในที่นี้เราเลือกโดยกำหนดให้สำหรับส่วนที่เหลืออสมการต้องเป็นจริง ตัวอย่างเช่น กรณีนี้เกิดขึ้นเมื่อดังนั้น เราจึงเลือก โดยที่จำนวนธรรมชาติจะถูกกำหนดโดยอสมการ: ${\displaystyle m}$${\displaystyle R_{m}}$${\displaystyle R_{m}\leq 2^{-n-1}}$${\displaystyle m\geq {\frac {4n}{\log n}}.}$${\displaystyle m=2^{k}}$${\displaystyle k}$

${\displaystyle 2^{k}\geq {\frac {4n}{\log n}}>2^{k-1}.}$

เราคำนวณผลรวม

${\displaystyle S=1+{\frac {1}{1!}}+{\frac {1}{2!}}+\cdots +{\frac {1}{(m-1)!}}=\sum _{j=0}^{m-1}{\frac {1}{(m-1-j)!}},}$

โดยดำเนินการตามขั้นตอนดังต่อไปนี้ ${\displaystyle k}$

ขั้นตอนที่ 1. นำพจน์ในผลบวกมาจับคู่กันตามลำดับ แล้วดึงตัวประกอบร่วมที่ "เห็นได้ชัด" ออกจากวงเล็บ จะได้ผลลัพธ์ดังนี้ ${\displaystyle S}$

${\displaystyle {\begin{aligned}S&=\left({\frac {1}{(m-1)!}}+{\frac {1}{(m-2)!}}\right)+\left({\frac {1}{(m-3)!}}+{\frac {1}{(m-4)!}}\right)+\cdots \\&={\frac {1}{(m-1)!}}(1+m-1)+{\frac {1}{(m-3)!}}(1+m-3)+\cdots .\end{aligned}}}$

เราจะคำนวณเฉพาะค่าจำนวนเต็มของนิพจน์ในวงเล็บเท่านั้น นั่นคือค่าต่างๆ

${\displaystyle m,m-2,m-4,\dots .\,}$

ดังนั้น ในขั้นตอนแรก ผลรวมจึงถูกแบ่งออกเป็น ${\displaystyle S}$

${\displaystyle S=S(1)=\sum _{j=0}^{m_{1}-1}{\frac {1}{(m-1-2j)!}}\alpha _{m_{1}-j}(1),}$

${\displaystyle m_{1}={\frac {m}{2}},m=2^{k},k\geq 1.}$

ในขั้นตอนแรกจำนวนเต็มในรูปแบบ ${\displaystyle {\frac {m}{2}}}$

${\displaystyle \alpha _{m_{1}-j}(1)=m-2j,\quad j=0,1,\dots ,m_{1}-1,}$

คำนวณค่าต่างๆ เสร็จแล้ว จากนั้นเราก็ทำในลักษณะเดียวกัน คือ ในแต่ละขั้นตอน เราจะรวมพจน์ของผลรวมเข้าด้วยกันทีละคู่ แล้วนำตัวประกอบร่วมที่ 'เห็นได้ชัด' ออกจากวงเล็บ และคำนวณเฉพาะค่าจำนวนเต็มของนิพจน์ในวงเล็บเท่านั้น สมมติว่าขั้นตอนแรกของกระบวนการนี้เสร็จสมบูรณ์แล้ว ${\displaystyle S}$${\displaystyle i}$

ขั้นตอน( ) ${\displaystyle i+1}$${\displaystyle i+1\leq k}$

${\displaystyle S=S(i+1)=\sum _{j=0}^{m_{i+1}-1}{\frac {1}{(m-1-2^{i+1}j)!}}\alpha _{m_{i+1}-j}(i+1),}$

${\displaystyle m_{i+1}={\frac {m_{i}}{2}}={\frac {m}{2^{i+1}}},}$

เราคำนวณเฉพาะจำนวนเต็มในรูปแบบนี้ เท่านั้น${\displaystyle {\frac {m}{2^{i+1}}}}$

${\displaystyle \alpha _{m_{i+1}-j}(i+1)=\alpha _{m_{i}-2j}(i)+\alpha _{m_{i}-(2j+1)}(i){\frac {(m-1-2^{i+1}j)!}{(m-1-2^{i}-2^{i+1}j)!}},}$

${\displaystyle j=0,1,\dots ,\quad m_{i+1}-1,\quad m=2^{k},\quad k\geq i+1.}$

ที่นี่

${\displaystyle {\frac {(m-1-2^{i+1}j)!}{(m-1-2^{i}-2^{i+1}j)!}}}$

คือผลคูณของจำนวนเต็ม ${\displaystyle 2^{i}}$

เป็นต้น

ขั้นตอนสุดท้าย เราคำนวณค่าจำนวนเต็มหนึ่งค่า โดยใช้อัลกอริธึมเร็วที่อธิบายไว้ข้างต้น แล้วหารค่าจำนวนเต็มนั้น ด้วยจำนวนเต็ม อีกค่าหนึ่ง ด้วยความแม่นยำถึง หลักทศนิยม ผลลัพธ์ที่ได้คือผลรวมหรือค่าคงที่ที่มีความแม่นยำถึงหลักทศนิยม ความซับซ้อนของการคำนวณทั้งหมดคือ ${\displaystyle k}$${\displaystyle \alpha _{1}(k),}$${\displaystyle (m-1)!,}$${\displaystyle \alpha _{1}(k)}$${\displaystyle (m-1)!,}$${\displaystyle n}$${\displaystyle S,}$${\displaystyle e}$${\displaystyle n}$

${\displaystyle O\left(M(m)\log ^{2}m\right)=O\left(M(n)\log n\right).\,}$

• อัลกอริทึมที่รวดเร็ว
• วิธีการ AGM
• ความซับซ้อนในการคำนวณ

• http://www.ccas.ru/personal/karatsuba/divcen.htm
• http://www.ccas.ru/personal/karatsuba/algen.htm