Pada Kurva Bezier dan Kecepatan Arduino, Bagian Dua

Kami akan melewati - dan selanjutnya

Dalam posting saya sebelumnya, saya menunjukkan bagaimana Anda dapat meningkatkan kecepatan menghitung poin pada kurva Bezier (KB) dengan:

1. Transformasi rumus perhitungan - akselerasi ~ 3 kali.
2. Hampir tidak ada akselerasi dari PT ke FT - tetapi memungkinkan 3.
3. Operasi penggantian divisi dengan multiplikasi dan shift merupakan akselerasi 40% lainnya.

Di akhir pos yang disebutkan, saya mengatakan bahwa perhitungan dapat dilakukan lebih cepat, tetapi apa yang "dikatakan bocah itu - bocah itu melakukannya."

Biarkan saya mengingatkan Anda sekali lagi tentang formula yang diperoleh untuk menghitung titik pada KB

$$

$$P = (A1 * dan + B1) * dan + C (=> 2 * 2 +)$$

Peningkatan kecepatan berikutnya terkait dengan kekhasan masalah - kita tidak perlu hanya menghitung nilai KB pada nilai yang berbeda dari parameter "dan", tetapi untuk menemukan serangkaian nilai ketika mengubah (dalam hal ini, meningkatkan) parameter ini dengan diketahui, apalagi, nilai tetap (dalam case case), yang memungkinkan Anda menggunakan teknik yang dijelaskan di bawah ini. Di masa saya, itu disebut metode perhitungan yang berbeda (jika ingatan saya benar, setidaknya itulah yang disebut dalam kuliah), seluruh internet siap membantu Anda, mungkin (bahkan pasti), ada nama lain.

Kami mempertimbangkan kasus P = A * dan (=> 1 *), dan anggaplah kita tahu nilai P0 dengan beberapa argumen u0. Maka nilai dengan argumen berikutnya u0 + 1 dapat dihitung sebagai P = A * (u0 + 1) = A * u0 + A = P0 + A (=> 1+). Tanpa kehilangan presisi, kami dapat mengganti operasi perkalian dengan operasi penambahan, yang jauh lebih cepat.

Sekarang contoh yang lebih kompleks P = A * dan * dan (=> 2 *), kita pertimbangkan dengan analogi P = A * (dan + 1) * (dan + 1) = A * (dan * dan + 2 * dan + 1) = A * dan * dan + 2 * A * dan + A = P0 + 2 * A * dan + A (=> 2 * 2 +). Pada pandangan pertama, kami tidak memenangkan apa pun, tetapi jika kami menghitung A '= 2 * A sebelumnya, kami mendapatkan (=> 1 * 2 +), kemenangan sangat mungkin terjadi. Tetapi kita tidak akan berhenti pada apa yang telah dicapai dengan ekspresi yang diperoleh A '* dan menerapkan teknik yang sudah dikenal kepada kita, maka kita akan mendapatkan dua operasi pada dua variabel: P = P + A' + A; A '= A' + A (=> 3+). Jika kita memperhitungkan bahwa nilai awal A 'dapat dilakukan lebih banyak oleh A, maka secara umum hanya ada dua penambahan, bukan dua perkalian. Ya, kami harus mendapatkan dua variabel tambahan, tetapi ini adalah pertukaran klasik - kami membayar dengan memori untuk saat itu.

Tetap hanya untuk menghitung nilai awal yang benar, tetapi ini dilakukan hanya sekali pada awal iterasi, dan jika nilai awal dari parameter adalah u = 0, maka umumnya sepele P = 0, A '= A. Kami akan menguji metode kami pada beberapa iterasi (ini sama sekali tidak perlu, matematika yang diterapkan dengan benar tidak dapat memberikan jawaban yang salah), tetapi itu akan memungkinkan kami untuk lebih memahami apa yang terjadi. Jadi
iterasi 0: dan = 0; P = 0 (benar); A '= A; A '' = 2 * A;
iterasi 1: dan = 1; P = 0 + A '= 0 + A = A (benar); A '= A' + A '' = A + 2 * A = 3 * A;
iterasi 2: dan = 2; P = A + 3 * A = 4 * A (benar); A '= 3 * A + 2 * A = 5 * A;
iterasi 3: dan = 3; P = 9 * A (benar); A '= 7 * A dan seterusnya.

Kami mencatat hubungan antara rumus yang diperoleh dan metode Newton untuk menghitung nilai fungsi di sekitar titik dengan nilai yang diketahui. Selain itu, mengingat bahwa fungsi kami adalah urutan kedua dan semua turunannya, mulai dari urutan ketiga, sama dengan nol, kami dapat dengan aman mengganti perkiraan tanda sama dengan yang tepat. Satu-satunya perbedaan dari metode ini adalah bahwa kami terus-menerus memindahkan titik relatif yang kami bangun lingkungan baru untuk menghindari melakukan operasi multiplikasi dalam formulasi asli.

Tulis ulang ekspresi asli kami untuk KB dalam bentuk yang diperluas

$$

$$P = A1 * dan * dan + B1 * dan + C$$

maka untuk perhitungan menggunakan metode ini kita perlu 2+ untuk suku pertama (dan dua variabel), 1+ untuk suku kedua (dan satu variabel) dan 2+ untuk menambahkan semuanya bersama-sama (=> 5+). Dapat diharapkan bahwa bahkan pendekatan (salah) ini akan memberikan keuntungan dibandingkan dengan 2 * 2 +, tetapi semuanya jauh lebih baik. Jelas, operasi penjumlahan adalah aditif (terima kasih, kapten), sehingga Anda dapat mengelompokkan istilah dan mengganti istilah konstan dengan ekspresi baru, yang memberikan algoritme berikut:

1. Nilai awal P = C; A '= A1 + B1; A '' = 2 * A1;
2. pada langkah selanjutnya P = P + A '; A '= A' + A '' (=> 2+), yang tidak diragukan lagi lebih cepat daripada skema Horner.

Kami menerapkan algoritme kami dalam bentuk program (ini tidak sepele seperti kelihatannya, karena untuk kesederhanaan saya lupa tentang perlunya shift, tetapi tidak terlalu sulit ... selama 20 menit), kami mendapatkan kompleksitas komputasi (=> 2 + 1 >>) dan mengukur kecepatan - ternyata 140 (peningkatan kecepatan oleh 3 kali) siklus per siklus, tetapi ini hampir merupakan hasil yang ideal. Apa yang harus kita lakukan untuk mendapatkan opsi yang ideal (dalam arti tertentu) adalah memperhatikan dimensi operan dalam formula. Sekarang kami melakukan semua operasi pada bilangan bulat panjang (32-bit), dan ini mungkin tidak perlu di beberapa tempat. Jika kita mengurangi kapasitas operan ke minimum yang diperlukan, maka kita bisa mendapatkan keuntungan 20-25 persen, tetapi ini akan mengharuskan kita untuk beralih ke assembler (C tidak memiliki sarana yang cocok untuk operasi semacam itu) dan dengan cermat menganalisis data dari masalah aslinya. Apakah terserah pembaca untuk memutuskan apakah akan melakukan ini, kami telah mempercepat perhitungan lebih dari 1900/140 = 13 kali dibandingkan dengan pendekatan "naif".

Catatan terakhir tentang implementasi algoritma adalah bahwa kami masih mengecualikan operasi divisi dengan mengubahnya dengan perkalian konstan, yang kami perhitungkan saat membuat data awal dan bergeser dengan kelipatan konstan 8. Ini dapat dilakukan dengan berbagai cara dengan waktu eksekusi yang sedikit berbeda, membiarkan eksperimen semacam itu menjadi perhatian pembaca yang ingin tahu. .

Namun, satu masalah muncul sepenuhnya secara tak terduga - kami dengan jelas melihat dua operasi tambahan pada angka 32 bit, yang harus mengambil 4 + 4 = 8 siklus clock, menempatkan 8 * 3 * 2 = 48 siklus clock untuk mengirim operan, 4 siklus clock untuk menerima hasil shift, 4 siklus clock untuk memanggil prosedur perhitungan dan kembali, dan 4 siklus clock untuk mengatur siklus - dari mana 60 siklus clock lainnya tidak jelas. Sebelumnya, kami sama sekali tidak memperhatikan ini dengan latar belakang ratusan siklus jam, tetapi sekarang Anda dapat memperhatikan. Langkah-langkah berlebihan mudah ditemukan - dalam siklus ada operasi debugging yang tidak perlu, jika Anda membersihkan semuanya dengan hati-hati, maka hanya 120 langkah yang tersisa dan tujuan masing-masing cukup dimengerti (well, tidak begitu sepenuhnya jelas, tetapi masih). Selanjutnya, kita mengetahui waktu pelaksanaan siklus kosong - 22 langkah, saya ingin tahu apa yang mereka lakukan di sana selama ini, tapi oh well, dan hapus waktu perhitungan yang sebenarnya, yang akan menjadi 98 siklus. Perhatikan bahwa perkiraan perubahan akselerasi kerja yang diperoleh: alih-alih 1900/140 = 13 kita mendapatkan (1900-50) / (140-40) = 19 kali, yang tidak masuk akal secara praktis, karena siklus masih diperlukan, tetapi memungkinkan Anda untuk meningkatkannya lebih banyak lagi harga diri.

Dan komentar terakhir - karena mudah dilihat, kami mulai mencari dan menghilangkan kutu hanya ketika kami berurusan dengan kumbang rusa besar dan keberadaan (kutu) mereka menjadi jelas dan, terlebih lagi, penting. Saya sangat merekomendasikan pendekatan ini (dan saya tidak sendirian dalam rekomendasi ini) ketika mengoptimalkan program dalam hal kinerja.

Kesimpulannya, tentang catatan “dalam arti” - jika kita berbicara tentang menghitung secara berurutan titik koordinat berikutnya pada KB ketika mengubah parameter (mewakili waktu), maka algoritma yang diusulkan (setelah semua optimasi) tidak lagi mungkin untuk ditingkatkan. Tetapi jika Anda merumuskan ulang tugas dan, misalnya, menetapkan tujuan hanya membangun biro desain di layar (tanpa referensi waktu), maka ada metode yang sangat menjanjikan, kata kunci "Brezenheim", tetapi "ini adalah kisah yang sama sekali berbeda", yang akan saya curahkan pada pos terpisah. (mungkin suatu hari nanti jika kakak perempuannya tidak keberatan).