Pembalikan efisien (1 / x) untuk AVR

Saya mencoba menemukan cara yang efisien untuk menghitung invers pada AVR (atau perkiraannya).

Saya mencoba menghitung periode pulsa untuk motor stepper sehingga saya dapat memvariasikan kecepatan secara linear. Periode ini sebanding dengan kebalikan dari kecepatan ( p = K/v), tapi saya tidak bisa memikirkan cara yang baik untuk menghitung ini dengan cepat.

Formula saya adalah

p = 202/v + 298; // p in us; v varies from 1->100

Menguji pada Arduino, divisi tersebut tampaknya diabaikan sepenuhnya ptetap pada 298(meskipun mungkin ini akan berbeda dalam avr-gcc). Saya juga telah mencoba menjumlahkan vdalam satu lingkaran sampai melebihi 202, dan menghitung loop, tetapi ini cukup lambat.

Saya bisa membuat tabel pencarian dan menyimpannya dalam flash, tapi saya bertanya-tanya apakah ada cara lain.

Sunting : Mungkin judulnya harus "pembagian efisien" ...

Pembaruan : Seperti yang ditunjukkan oleh pingswept, rumus saya untuk periode pemetaan ke kecepatan tidak benar. Tetapi masalah utama adalah operasi membagi.

Sunting 2 : Pada penyelidikan lebih lanjut, divide sedang mengerjakan arduino, masalahnya adalah karena rumus yang salah di atas dan limpahan int di tempat lain.

Satu hal yang menyenangkan tentang pembagian adalah bahwa setiap orang melakukannya. Ini adalah fitur inti yang cukup dari bahasa C, dan kompiler seperti AVR-GCC (disebut oleh Arduino IDE) akan memilih algoritma pembagian terbaik yang tersedia, bahkan ketika mikrokontroler tidak memiliki instruksi divisi perangkat keras.

Dengan kata lain, Anda tidak perlu khawatir tentang bagaimana pembagian dilaksanakan kecuali Anda memiliki kasus khusus yang sangat aneh.

Jika Anda khawatir, maka Anda mungkin menikmati membaca algoritma pembagian resmi yang disarankan Atmel (satu dioptimalkan untuk ukuran kode, dan satu dioptimalkan untuk kecepatan eksekusi; tidak mengambil memori data apa pun). Mereka di:

http://www.atmel.com/dyn/resources/prod_documents/doc0936.pdf

yang merupakan Catatan Aplikasi "AVR200: Multiply dan Divide Routines" yang tercantum pada halaman Atmel untuk prosesor Atmega (cukup besar) seperti Atmega 168 dan Atmega 328 yang digunakan dalam Arduinos standar. Daftar lembar data dan catatan aplikasi ada di:

http://www.atmel.com/dyn/products/product_card.asp?part_id=4720

Menurut saya seperti yang Anda butuhkan adalah tabel pencarian 100 entri. Tidak lebih cepat dari itu.

#define VALUE_FOR_V_EQUALS_ZERO 0
uint16_t formula_lookup[100] = {VALUE_FOR_V_EQUALS_ZERO, 500, 399, 365, 348, ..., 300};

...

//"calculate" formula
p = formula_lookup[v > 67 ? 67 : v];

EDIT Anda sebenarnya hanya tabel pencarian nilai 68 karena nilai v lebih besar dari 67 selalu mengevaluasi hingga 300.

Ada beberapa teknik yang sangat baik yang disebutkan dalam buku "Hackers Delight oleh Henry Warren dan di situs webnya hackersdelight.org . Untuk teknik yang bekerja dengan baik dengan mikrokontroler yang lebih kecil ketika membaginya dengan konstanta, lihat file ini .

Fungsi Anda sepertinya tidak akan memberikan hasil yang Anda inginkan. Sebagai contoh, nilai 50 mengembalikan sekitar 302, sedangkan 100 mengembalikan sekitar 300. Kedua hasil itu akan menyebabkan hampir tidak ada perubahan dalam kecepatan motor.

Jika saya memahami Anda dengan benar, Anda benar-benar mencari cara cepat untuk memetakan angka 1-100 ke kisaran 300-500 (kurang-lebih), sehingga 1 peta menjadi 500 dan 100 peta menjadi 300.

Mungkin coba: p = 500 - (2 * v)

Tapi saya mungkin salah paham - apakah Anda mencoba menghitung tepat waktu dari gelombang persegi frekuensi konstan? 298 Apa itu?

Cara efisien untuk memperkirakan pembagian adalah dengan shift. misal jika x = y / 103; membagi dengan 103 sama dengan mengalikan dengan 0,0097087, jadi untuk memperkirakan ini pertama pilih nomor shift 'baik' (yaitu nomor basis-2, 2,4,8,16,32 dan seterusnya)

Untuk contoh ini 1024 sangat cocok karena kita dapat mengatakan bahwa 10/1024 = 0,009765 Maka mungkin untuk kode:

x = (y * 10) >> 10;

Mengingat tentu saja untuk memastikan variabel y tidak melimpah tipenya ketika dikalikan. Ini tidak tepat, tetapi cepat.

Pada catatan lain jika Anda mencoba melakukan pembagian pada CPU yang tidak mendukung pembagian, ada cara yang sangat keren untuk melakukannya di artikel Wiki ini.

http://en.wikipedia.org/wiki/Multiplicative_inverse

Untuk memperkirakan kebalikan dari x, hanya menggunakan perkalian dan pengurangan, orang dapat menebak angka y, dan kemudian berulang kali mengganti y dengan 2y - xy2. Setelah perubahan y menjadi (dan tetap) cukup kecil, y adalah perkiraan kebalikan dari x.

Proses ini di sini terlihat ramah-MCU, meskipun mungkin perlu sedikit porting.

Padahal sepertinya LUT akan lebih mudah. Anda hanya perlu 100 byte, lebih sedikit jika Anda menggunakan beberapa interpolasi, dan karena LUT diisi dengan konstanta maka kompiler bahkan mungkin menemukannya di area kode alih-alih area data.

Periksa untuk memastikan bahwa divisi tersebut dilakukan sebagai titik mengambang. Saya menggunakan Microchip bukan AVR, tetapi ketika menggunakan C18 Anda harus memaksa literal Anda diperlakukan sebagai floating point. Misalnya. Coba ubah formula Anda menjadi:

p = 202.0/v + 298.0;

Anda ingin cepat jadi begini ..... Karena AVR tidak dapat melakukan normalisasi secara efisien (bergeser ke kiri hingga Anda tidak dapat menggeser lagi), abaikan semua algoritma floating point semu. Cara paling sederhana untuk pembagian integer yang sangat akurat dan tercepat dalam AVR adalah melalui tabel pencarian timbal balik. Tabel akan menyimpan timbal balik yang diskalakan dengan jumlah besar (katakanlah 2 ^ 32). Anda kemudian mengimplementasikan unsigned32 x unsigned32 = unsigned 64 multiplication in assembler, jadi answer = (numerator * inverseQ32 [denominator]) >> 32.
Saya menerapkan fungsi multiplikasi menggunakan inline assembler, (dibungkus dengan fungsi ac). GCC memang mendukung "long long" 64-bit, namun, untuk mendapatkan hasil Anda harus mengalikan 64bits dengan 64bits, bukan 32x32 = 64 karena keterbatasan bahasa C pada arsitektur 8-bit ......

Kelemahan dari metode ini adalah Anda akan menggunakan 4K x 4 = 16K flash jika Anda ingin membagi dengan bilangan bulat dari 1 hingga 4096 ......

Divisi unsigned yang sangat akurat sekarang dicapai dalam sekitar 300 siklus dalam C.

Anda dapat mempertimbangkan untuk menggunakan bilangan bulat berskala 24 bit atau 16 bit untuk kecepatan lebih tinggi, akurasi kurang.

p = 202/v + 298; // p in us; v varies from 1->100

Nilai balik dari persamaan Anda sudah ada p=298sejak kompiler membaginya terlebih dahulu lalu tambahkan, gunakan resolusi muldiv integer yaitu:

p = ((202*100)/v + (298*100))/100 

Menggunakan ini adalah kalikan yang sama a*f, dengan a = integer f = fraksi.

Itu menghasilkan r=a*ftetapi f=b/ckemudian r=a*b/ctetapi itu belum berfungsi karena posisi operator, menghasilkan fungsi final r=(a*b)/catau muldiv, cara untuk menghitung angka fraksi menggunakan hanya integer.