Kami sedang menulis "kalkulator". Bagian II Memecahkan persamaan, render dalam LaTeX, mempercepat fungsi menjadi superlight

Hai

Jadi, pada bagian pertama, kami sudah melakukan pekerjaan dengan baik melakukan turunan, penyederhanaan, dan kompilasi. Jadi, apa lagi yang bisa dilakukan kalkulator sederhana kita? Yah, setidaknya persamaan bentuk

$$

$$(x - b) (\ tan (\ sin (x)) ^ 2 - 3 \ tan (\ sin (x)) + c) = 0$$

pasti harus memutuskan. Sangat indah untuk menggambar kasing ini di latech, dan akan baik-baik saja! Ayo pergi!

Akselerasi kompilasi

Pada bagian terakhir, kami mengkompilasi fungsi sehingga kami dapat mengompilasinya sekali, dan kemudian menjalankannya berkali-kali di masa depan.
Jadi, kami memperkenalkan fungsinya

$$

$$\ sin (x ^ 2) + \ cos (x ^ 2) + x ^ 2 + \ sin (x ^ 2)$$

Pada akhir bagian pertama, kecepatan fungsi ini adalah sebagai berikut:


Seperti yang dapat kita lihat, ada bagian berulang dalam fungsi ini, misalnya, $$$x ^ 2$ , dan alangkah baiknya untuk menyimpannya.

Untuk melakukan ini, kami memperkenalkan dua instruksi PULLCACHE dan TOCACHE. Yang pertama akan mendorong nomor dalam cache di alamat yang kami berikan ke stack. Yang kedua akan menyalin ( stack.Peek() ) nomor terakhir dari stack ke cache, juga di alamat tertentu.

Masih membuat tabel di mana selama kompilasi kita akan menulis fungsi untuk caching. Apa yang tidak akan kita cache? Pertama, apa yang terjadi sekali. Instruksi tambahan untuk mengakses cache tidak baik. Kedua, operasi yang terlalu sederhana juga tidak masuk akal untuk di-cache. Yah, misalnya, mengakses variabel atau angka.

Saat menafsirkan daftar instruksi, kami akan memiliki larik yang sudah dibuat sebelumnya untuk caching. Sekarang petunjuk untuk fungsi ini terlihat seperti

 PUSHCONST (2, 0) PUSHVAR 0 CALL powf TOCACHE 0 #   ,         , -  . CALL sinf TOCACHE 1 #      PULLCACHE 0 # ,   .    PULLCACHE 0 CALL cosf PULLCACHE 1 CALL sumf CALL sumf CALL sumf 

Setelah itu kami mendapatkan hasil yang jelas lebih baik:

Dalam lobak, baik kompilasi maupun interpretasi instruksi dilaksanakan di sini .

LaTeX

Ini adalah format yang terkenal untuk merekam rumus matematika (meskipun tidak hanya itu!), Yang dirender menjadi gambar yang indah. Itu juga di hub, dan semua formula yang saya tulis hanya ditulis dalam format ini.

Memiliki pohon ekspresi membuat rendering dalam lateks sangat sederhana. Bagaimana melakukan ini dalam hal logika? Jadi, kita memiliki puncak pohon. Jika itu angka atau variabel, maka semuanya sederhana. Jika simpul ini, misalnya, operator divisi, kami ingin lebih $$$\ frac {a} {b}$ dari $$$a / b$ , jadi untuk pembagian kita menulis sesuatu seperti

 public static class Div { internal static string Latex(List<Entity> args) => @"\frac{" + args[0].Latexise() + "}{" + args[1].Latexise() + "}"; } 

Semuanya sangat sederhana, seperti yang kita lihat. Satu-satunya masalah yang saya temui selama implementasi adalah tidak jelas bagaimana menempatkan tanda kurung. Jika kita hanya mendorong mereka ke setiap operator, kita akan mendapatkan omong kosong seperti itu:

$$

$$\ kiri (\ kiri (\ kiri (\ kiri (x + 3 \ kanan) + \ kiri (a + b \ kanan) \ kanan) \ kanan) + c \ kanan)$$

Namun, orang yang penuh perhatian akan segera (dan tidak menyukai saya) memperhatikan bahwa jika mereka sepenuhnya dihapus, maka ketika membangun ekspresi bentuk $$$c * (a + b)$ , kami akan mencetak

$$

$$c * a + b$$

Ini diselesaikan dengan sederhana, kami memasuki prioritas operator a la

 args[0].Latexise(args[0].Priority < Const.PRIOR_MUL) + "*" + args[1].Latexise(args[1].Priority < Const.PRIOR_MUL); 

Dan voila, kamu cantik.

Lateksisasi dilakukan di sini . Dan kata latexise tidak ada, saya menciptakannya sendiri, jangan menendang saya untuk itu.

Solusi persamaan

Sebenarnya, dari sudut pandang matematika, Anda tidak dapat menulis algoritma yang menemukan semua solusi dari beberapa persamaan. Oleh karena itu, kami ingin menemukan akar yang berbeda sebanyak mungkin, menyadari pencapaian tujuan akhir yang tidak tercapai. Ada dua komponen: solusi numerik (semuanya sesederhana mungkin) dan analitis (tetapi ini adalah sejarah).

Solusi numerik. Metode Newton

Dia sangat sederhana, mengetahui fungsinya $$$f (x)$ kami akan mencari root menggunakan formula berulang

$$

$$x_ {n + 1} = x_n - \ frac {f (x)} {f (x) '}$$

Karena kita semua menyelesaikan dalam bidang yang kompleks, kita pada dasarnya dapat menulis siklus dua dimensi yang akan mencari solusi dan kemudian mengembalikan yang unik. Selain itu, kita sekarang dapat menemukan turunan dari fungsi secara analitis, dan kemudian kedua fungsi tersebut $$$f (x)$ dan $$$f (x) '$ kompilasi.

Newton duduk di sini .

Solusi analitik

Pikiran pertama cukup jelas. Jadi, ungkapan, akar persamaan $$$a (x) * b (x)$ totalitas akar yang sama $$$a (x)$ dan $$$b (x)$ , demikian pula untuk divisi:

 internal static void Solve(Entity expr, VariableEntity x, EntitySet dst) { if (expr is OperatorEntity) { switch (expr.Name) { case "mul": Solve(expr.Children[0], x, dst); Solve(expr.Children[1], x, dst); return; case "div": Solve(expr.Children[0], x, dst); return; } } ... 

Untuk sinus, ini akan terlihat sedikit berbeda:

 case "sinf": Solve(expr.Children[0] + "n" * MathS.pi, x, dst); return; 

Lagi pula, kami ingin menemukan semua root, dan bukan hanya yang 0.

Setelah kami memastikan bahwa ekspresi saat ini bukan produk, dan bukan operator dan fungsi yang mudah disederhanakan lainnya, kami perlu mencoba menemukan templat untuk menyelesaikan persamaan.

Ide pertama adalah menggunakan pola yang kami buat untuk menyederhanakan ekspresi. Dan pada kenyataannya, kita akan membutuhkan sekitar ini, tetapi pertama-tama kita perlu melakukan penggantian variabel. Dan memang, untuk persamaan

$$

$$\ sin (x) ^ 2 + \ sin (x) - 0.4 = 0$$

tidak ada template, kecuali pasangan

$$

$$\ begin {cases} t ^ 2 + t - 0.4 = 0 \\ t = \ sin (x) \ end {cases}$$

bahkan saat itu ada.

Oleh karena itu, kami membuat fungsi dari tipe GetMinimumSubtree, yang akan mengembalikan penggantian variabel yang paling efisien. Apa pengganti yang efektif? Ini adalah pengganti di mana kita

1. Maksimalkan penggunaan penggantian ini
   
2. Maksimalkan kedalaman pohon (sehingga dalam persamaan $$$\ sin (\ sin (x)) ^ 2 + 3$ kami punya pengganti $$$\ sin (\ sin (x))$ )
   
3. Kami memastikan bahwa dengan penggantian ini, kami telah mengganti semua referensi ke variabel, misalnya, jika dalam persamaan $$$\ sin (x) ^ 2 + \ sin (x) + x$ kami akan melakukan penggantian $$$t = \ sin (x)$ maka semuanya akan menjadi buruk. Oleh karena itu, dalam persamaan ini, penggantian terbaik untuk $$$x$ itu $$$x$ (Yaitu, tidak ada pengganti yang baik), tetapi misalnya dalam $$$\ sin (x) ^ 2 + \ sin (x) + c$ kita dapat dengan aman melakukan penggantian $$$t = \ sin (x)$ .
   

Setelah mengganti persamaan terlihat jauh lebih sederhana.

Polinomial

Jadi, hal pertama yang kita lakukan, kita lakukan expr.Expand() - buka semua tanda kurung untuk menyingkirkan kotoran formulir $$$x (x + 2)$ berubah menjadi $$$x ^ 2 + 2x$ . Sekarang, setelah pengungkapan, kami mendapatkan sesuatu seperti

$$

$$c + x ^ 3 + 3x ^ 2 - a * x ^ 3 + x$$

Bukan kanonik? Kemudian pertama-tama kami mengumpulkan informasi tentang setiap monomial, menerapkan "anak-anak linier" (dalam artikel terakhir ) dan memperluas semua persyaratan.

Apa yang kita miliki tentang monomial? Monomial adalah produk faktor, salah satunya adalah variabel, atau operator tingkat variabel dan integer. Oleh karena itu, kami akan memperkenalkan dua variabel, satu akan memiliki gelar, dan yang lainnya koefisien. Selanjutnya, cukup periksa faktor-faktornya, dan setiap kali kita memastikan itu ada $$$x$ sampai batas tertentu, atau tanpa gelar sama sekali. Jika kita bertemu byaku - kita kembali dengan nol.


Oke, kami telah menyusun kamus di mana kuncinya adalah gelar (integer) dan nilainya adalah koefisien monomial. Seperti inilah contoh sebelumnya:

 0 => c 1 => 1 2 => 3 3 => 1 - a 

Di sini, misalnya, implementasi solusi persamaan kuadratik

 if (powers[powers.Count - 1] == 2) { var a = GetMonomialByPower(2); var b = GetMonomialByPower(1); var c = GetMonomialByPower(0); var D = MathS.Sqr(b) - 4 * a * c; res.Add((-b - MathS.Sqrt(D)) / (2 * a)); res.Add((-b + MathS.Sqrt(D)) / (2 * a)); return res; } 

Poin ini belum selesai (misalnya, Anda harus melakukannya dengan benar untuk polinomial kubik), tetapi secara umum hal ini terjadi di sini .

Sapu Terbalik

Jadi, di sini kita telah melakukan beberapa penggantian tipe $$$t = \ arcsin (x ^ 3 + a ^ 2)$ , dan sekarang kami ingin mendapatkan x dari sana. Di sini kita hanya memiliki penyebaran fungsi dan operator selangkah demi selangkah, seperti

$$

$$t = \ arcsin (x ^ 3 + a ^ 2)$$

$$

$$\ sin (t) = x ^ 3 + a ^ 2$$

$$

$$\ sin (t) - a ^ 2 = x ^ 3$$

$$

$$(\ sin (t) - a ^ 2) ^ {\ frac {1} {3}} = x$$

Cuplikan kode terlihat seperti ini:

 switch (func.Name) { case "sinf": // sin(x) = value => x = arcsin(value) return FindInvertExpression(a, MathS.Arcsin(value), x); case "cosf": // cos(x) = value => x = arccos(value) return FindInvertExpression(a, MathS.Arccos(value), x); case "tanf": // tan(x) = value => x = arctan(value) return FindInvertExpression(a, MathS.Arctan(value), x); ... 

Kode untuk fungsi-fungsi ini ada di sini .

Semuanya, solusi terakhir dari persamaan (sampai jumpa!) Terlihat seperti ini

1. Jika kita tahu nol fungsi atau operator, kirim Selesaikan di sana (misalnya, jika $$$a * b = 0$ kemudian jalankan Solve (a) dan Solve (b))
2. Temukan penggantinya
3. Pecahkan sebagai polinomial jika memungkinkan
4. Untuk semua solusi, gunakan pengganti untuk mendapatkan solusi akhir
5. Jika, sebagai polinomial, itu tidak diselesaikan dan kami hanya memiliki satu variabel, kami menyelesaikannya dengan metode Newton

Jadi, hari ini kita adalah:

• Mempercepat fungsi yang dikompilasi karena cache
• Diberikan dalam LaTeX
• Kami memecahkan sebagian kecil dari kasus persamaan

Saya mungkin tidak akan berbicara tentang perhitungan numerik integral tertentu, karena sangat sederhana . Saya tidak berbicara tentang penguraian, karena saya menerima kritik tentang hal ini di artikel sebelumnya. Idenya adalah menulis sendiri. Namun demikian, perlukah kita berbicara tentang bagaimana kita mengurai ekspresi dari string?
Proyeknya ada di sini .





Dan berikut adalah beberapa contoh dari apa yang kami lakukan hari ini

 var x = MathS.Var("x"); var y = MathS.Var("y"); var expr = x.Pow(y) + MathS.Sqrt(x + y / 4) * (6 / x); Console.WriteLine(expr.Latexise()); >>> {x}^{y}+\sqrt{x+\frac{y}{4}}*\frac{6}{x} 

$$${x} ^ {y} + \ sqrt {x + \ frac {y} {4}} * \ frac {6} {x}$

 var x = MathS.Var("x"); var expr = MathS.Sin(x) + MathS.Sqrt(x) / (MathS.Sqrt(x) + MathS.Cos(x)) + MathS.Pow(x, 3); var func = expr.Compile(x); Console.WriteLine(func.Substitute(3)); >>> 29.4752368584034 

 Entity expr = "(sin(x)2 - sin(x) + a)(b - x)((-3) * x + 2 + 3 * x ^ 2 + (x + (-3)) * x ^ 3)"; foreach (var root in expr.Solve("x")) Console.WriteLine(root); >>> arcsin((1 - sqrt(1 + (-4) * a)) / 2) >>> arcsin((1 + sqrt(1 + (-4) * a)) / 2) >>> b >>> 1 >>> 2 >>> i >>> -i 

Terima kasih atas perhatian anda!