Arduino'daki sines (ve cosines) hesaplamak için farklı yollar (ve en hızlı)

Sistemimin (robotik kol) açılarını hesaplamak için bir Arduino Uno kartı kullanıyorum. Açıları, ADC'nin tam aralığını kullanan ADC'den 10 bitlik değerler (0'dan 1023'e kadar). Sadece 1. çeyrekte (0 ila 90 derece) çalışacağım, her iki sinüs ve kosinüs pozitif ise, negatif sayılarla ilgili bir problem yok. Şüphelerim 3 soruyla ifade edilebilir:

  1. Arduino'da bu trigonometrik fonksiyonları hesaplamanın farklı yolları nelerdir?

  2. Aynı şeyi yapmanın en hızlı yolu nedir?

  3. Arduino IDE'de sin() ve cos() işlevleri var, ancak Arduino aslında bunları nasıl hesaplıyor (bak tablolarda veya yaklaşımlarda olduğu gibi)? Açık bir çözüm gibi görünüyorlar, ancak onları denemeden önce gerçek uygulamalarını bilmek istiyorum.

Not: Arduino IDE ve montaj kodlamada standart kodlamaya ve ayrıca belirtilmeyen diğer seçeneklere açıkım. Ayrıca, sayısal bir sistem için kaçınılmaz olan hatalar ve yaklaşımlarla ilgili hiçbir problemim yok; ancak mümkünse olası hataların kapsamını belirtmek iyi olur

8
Derece olarak çalışmak istediğini sanıyorum. Açı için tamsayı veya ondalık sayı girmek mi istiyorsun?
katma yazar Yoni Baciu, kaynak
Yaklaşık değerler ile iyi olur musun?
katma yazar Yoni Baciu, kaynak
Doğruluk ihtiyacınızı ölçebilir misiniz? Cos (π/2x) ≈ 1 − x² yaklaşımı maksimum 5.6e-2 hatası içerir. Ve 3 çarpma maliyeti olan (1 − x²) (1−0.224x²), 9.20e-4 içinde iyidir.
katma yazar Sprogz, kaynak
Sadece 90 (tamsayı) derece için 90 girişli bir arama tablosu en hızlı ve en verimli olacaktır. Aslında tam 360 derece için 90 girişli bir arama tablosu kullanabilirsiniz. Sadece 90-179 için geriye doğru oku ve 180-269 için ters çevir. 270-359 için ikisini de yapın.
katma yazar Majenko, kaynak
@EdgarBonet Geç cevap için özür dilerim. Mevcut nicel sabit bir doğruluğum yok. Sadece şu an mümkün olan tüm seçenekleri bilmek istiyorum
katma yazar Ken Arnold, kaynak
Derece evet. Kod yazmanın ve tamsayıları kullanırsak test etmenin daha kolay olacağını düşünüyorum, bu yüzden ben de onunla giderdim. Düzenlemeler hakkında daha net bilgi koyacağım
katma yazar Ken Arnold, kaynak
Evet aslında, ancak farklı yöntemlerin hatalarının boyutunu bilmek istiyorum. Bu hassas bir ürün değil, benim bir yan projem. Matematiksel bir işlevi uygulayan hemen hemen tüm (eğer olmasa bile) sayısal sistem için yaklaşık olarak tahminler kaçınılmazdır.
katma yazar Ken Arnold, kaynak

8 cevap

İki temel yöntem matematiksel hesaplama (polinomlarla) ve arama tablolarıdır.

Arduino'nun matematik kütüphanesi (libm, avr-libc'nin parçası) eskiyi kullanıyor. AVR için% 100 montaj dili ile yazıldığından ve bunun ne yaptığını takip etmek neredeyse imkansız olduğundan (sıfır yorum da vardır). En iyi duruma getirilmiş saf şamandıra uygulama beyinleri bizimkilerden çok daha üstün olacak olsa da emin olabilirsiniz.

Ancak, anahtar float . Kayan nokta içeren Arduino üzerinde herhangi bir şey, saf tamsayıya göre ağır olacak ve sadece 0 ile 90 derece arasında tamsayılar talep ettiğiniz için basit bir arama tablosu, en basit ve en etkili yöntemdir.

91 değerden oluşan bir tablo size 0 ile 90 arasında herşeyi verecektir. Bununla birlikte, eğer 0,0 ve 1,0 arasında bir kayan nokta değerleri tablosu yaparsanız, o zaman, floatlarla çalışmanın verimsizliğine sahip olursunuz (floatlarla günah hesaplanırken verimsiz olarak verilir), dolayısıyla sabit bir nokta değeri depolanır. bunun yerine çok daha verimli olurdu.

Bu, 1000 ile çarpılan değerin saklanması kadar basit olabilir, bu yüzden 0 ile 1000 arasında, 0,0 ve 1,0 arasında bir değere sahip olursunuz (örneğin, sin (30), 0.5 yerine 500 olarak depolanır). Değerlerin, örneğin her bir değerin (bit) 1.0/65536'nın 1.0 olduğunu gösteren bir Q16 değeri olarak saklanması daha verimli olacaktır. Bu Q16 değerleri (ve ilgili Q15, Q1.15, vb.), Çalışmaktan nefret ettikleri on-güçler yerine, bilgisayarların çalışmayı sevdiği ikisinden birine sahip olduğunuzdan, çalışmak için daha etkilidir.

sin() fonksiyonunun radyanları beklediğini de unutmayın, bu yüzden önce integer derecelerinizi kayan noktalı radyan değerine dönüştürmeniz gerekir. Böylece sin() tamsayı derece değeriyle doğrudan çalışabilen bir arama tablosuna kıyasla daha da verimsiz.

Bununla birlikte, iki senaryonun bir kombinasyonu mümkündür. Doğrusal enterpolasyon , iki tamsayı arasında bir kayan nokta açısına yaklaşmanızı sağlar. Arama tablosundaki iki nokta arasındaki mesafeyi ölçmek ve iki değerin o mesafesine göre ağırlıklı ortalama oluşturmak kadar basit. Örneğin, 23.6 derecesindeyseniz (günlüğe [23] * (1-0,6)) + (günlüğe [24] * 0,6) alırsınız. Temel olarak sinüs dalganız düz çizgilerle birleştirilen bir dizi ayrık noktaya dönüşür. Hız için ticaretin doğruluğu.

8
katma
Kütüphaneden daha hızlı olan bir günah/cos için bir Taylor polinomunu kullanan bir kütüphane yazdım. Verilen, her ikisi için giriş olarak kayan noktalı radyan kullanıyordum.
katma yazar tuskiomi, kaynak

Burada bazı iyi cevaplar var, ancak daha önce değinilmemiş, gömülü sistemlerde trigonometrik fonksiyonların hesaplanması için çok uygun bir yöntem eklemek istedim ve bu CORDIC tekniği. Buraya Wiki Girişi Yalnızca vardiyaları ve eklemeleri ve küçük bir arama tablosu kullanarak trig işlevlerini hesaplayabilir.

Burada C.'de ham bir örnek var. Aslında, CORDIC kullanarak C kütüphanelerinin atan2() fonksiyonunu uygular (yani, iki ortogonal bileşen verilen bir açı bulun.) Bu, kayan nokta kullanır, ancak sabit nokta aritmetiği ile kullanılmak üzere uyarlanabilir.

/*
 * Simple example of using the CORDIC algorithm.
 */

#include 
#include 

#define CORDIC_TABLE_SIZE  16

double cordic_table[CORDIC_TABLE_SIZE];

void init_table(void);
double angle(double I, double Q);

/*
 * Given a sine and cosine component of an
 * angle, compute the angle using the CORIDC
 * algoritm.
 */
double angle(double I, double Q)
{
    int L;
    double K = 1;
    double angle_acc = 0;
    double tmp_I;

    if (I < 0) {
        /* rotate by an initial +/- 90 degrees */
        tmp_I = I;
        if (Q > 0.0) {
            I = Q;           /* subtract 90 degrees */
            Q = -tmp_I;
            angle_acc = -90;
        } else {
            I = -Q;          /* add 90 degrees */
            Q = tmp_I;
            angle_acc = 90;
        }
    } else {
        angle_acc = 0;
    }

    /* rotate using "1 + jK" factors */
    for (L = 0, K = 1; L <= CORDIC_TABLE_SIZE; L++) {
        tmp_I = I;
        if (Q >= 0.0) {
            /* angle is positive: do negative roation */
            I += Q * K;
            Q -= tmp_I * K;
            angle_acc -= cordic_table[L];
        } else {
            /* angle is negative: do positive rotation */
            I -= Q * K;
            Q += tmp_I * K;
            angle_acc += cordic_table[L];
        }
        K /= 2.0;
    }
    return -angle_acc;
}

void init_table(void)
{
    int i;
    double K = 1;

    for (i = 0; i < CORDIC_TABLE_SIZE; i++) {
        cordic_table[i] = 180 * atan(K)/M_PI;
        K /= 2.0;
    }
}
int main(int argc, char **argv)
{
    double I, Q, A, Ar, R, Ac;

    init_table();

    printf("# Angle,    CORDIC Angle,  Error\n");
    for (A = 0; A < 90.0; A += 0.5) {

        Ar = A * M_PI/180; /* convert to radians for C's sin & cos fn's */

        R = 5; //Arbitrary radius

        I = R * cos(Ar);
        Q = R * sin(Ar);

        Ac = angle(I, Q);
        printf("%9f, %9f,   %12.4e\n", A, Ac, Ac-A);
    }
    return 0;
}

Ama önce yerli Arduino trig fonksiyonlarını deneyin - yine de yeterince hızlı olabilirler.

5
katma
Geçmişte benzer bir yaklaşım attım, st8. iki adımı alır: 1) günah (x) ve cos (x) 'yi günah (2x)' den hesaplayın ve sonra 2) sin (x +/- x/2) 'yi günah (x)' dan hesaplayın, sin (x/2) , cos (x) ve cos (x/2) -> yineleme ile hedefinize yaklaşabilirsiniz. Benim durumumda, 45 derece (0.707) ile başladım ve hedefe doğru yoluma çıktım. standart IAR sin() işlevinden oldukça yavaştır.
katma yazar dannyf, kaynak

Üzerinde bilgisayar sinüs ve kosinüsleri ile biraz oynuyorum. Sabit nokta polinom yaklaşımlarını kullanarak Arduino. İşte benim karşılaştırılan ortalama yürütme süresi ve en kötü durum hatası, avr-libc'den standart cos() ve sin() ile:

function    max error   cycles   time
-----------------------------------------
cos_fix()   9.53e-5     108.25    6.77 µs
sin_fix()   9.53e-5     110.25    6.89 µs
cos()       2.98e-8     1720.8   107.5 µs
sin()       2.98e-8     1725.1   107.8 µs

It's based on a 6th degree polynomial computed with only 4 multiplications. The multiplications themselves are done in assembly, as I found that gcc implemented them inefficiently. The angles are expressed as uint16_t in units of 1/65536 of a revolution, which makes the arithmetic of angles naturally work modulo one revolution.

Bunun faturanıza uygun olacağını düşünüyorsanız, kod şu şekildedir: Sabit nokta trigonometri . Üzgünüm, bu sayfayı Fransızca çevirmemiştim, ama sen denklemleri ve kodu (değişken isimleri, yorumları ...) anlayabilir İngilizcedir


Edit: Since the server seems to have vanished, here is some info on the approximations I found.

İkili sabit noktalarda, çeyrek birimlerde açı yazmak istedim (ya da eşdeğer olarak, sırayla). Ve ben de bir çift kullanmak istedim polinom, bunlar rasgele göre hesaplamak için daha verimlidir polinomları. Başka bir deyişle, bir polinom P ()

cos (π/2 x) x P (x 2 ) x ∈ için [0,1]

I also required the approximation to be exact at both ends of the interval, to ensure that cos(0) = 1 and cos(π/2) = 0. These constraints led to the form

P (u) = (1 - u) (1 + uQ (u))

Q() keyfi bir polinomdur.

Ardından, en iyi çözümü aradım. Q() ve şunu buldum:

        Q(u)             │ degree of P(x²) │ max error
─────────────────────────┼─────────────────┼──────────
          0              │         2       │  5.60e-2
       −0.224            │         4       │  9.20e-4
−0.2335216 + 0.0190963 u │         6       │  9.20e-6

Yukarıdaki çözümler arasından seçim, bir hız/doğruluk oranıdır. Üçüncü çözüm, 16 bit ile elde edilenden daha fazla doğruluk sağlar ve 16 bitlik uygulama için seçtiğim şey.

5
katma
@TLW: cevaba bunu ekledi.
katma yazar Sprogz, kaynak
@TLW: Q (u) 'nun keyfi olduğu bir formda (1 x x²) (1 + x²Q (x²)) sınırlanan bazı “güzel” özelliklere (örneğin cos (0) = 1) sahip olmasını isterdim. polinom (sayfada açıklanmıştır). Birinci derece Q (sadece 2 katsayı) aldım, yaklaşık katsayıları uygunluğa göre buldum, sonra optimizasyonu deneme yanılma yöntemiyle el ile ayarladı.
katma yazar Sprogz, kaynak
Bu harika, @Edgar.
katma yazar SDsolar, kaynak
Polinomu bulmak için ne yaptın?
katma yazar ThomasX, kaynak
@EdgarBonet - ilginç. Önbelleğe alınmış çalışmalar olsa da, sayfanın benim için yüklenmediğini unutmayın. Bu cevap için kullanılan polinomu ekleyebilir misiniz?
katma yazar ThomasX, kaynak

Bir arama tablosu, sines'i bulmanın en hızlı yolu olacaktır. Sabit nokta sayıları ile rahat bir hesaplama yapıyorsanız (ikili noktası bit-0'ın sağında başka bir yerde bulunan tam sayılar), sines ile yapacağınız diğer hesaplamalar da çok daha hızlı olacaktır. Bu tablo, daha sonra RAM alanından tasarruf etmek için muhtemelen Flash'ta bir sözcük tablosu olabilir. Matematikte, büyük ara sonuçlar için uzun kullanmanız gerekebilir.

2
katma

Belirli bir açının sin() ve cos() değerini belirlemek için doğrusal yaklaşımı kullanan birkaç işlev oluşturabilirsiniz.

Böyle bir şey düşünüyorum:
doğrusal yaklaşım
Her biri için sin() ve cos() 'nın 3 bölüm halinde grafiksel temsilini kırdım ve bu bölümün doğrusal bir yaklaşımını yaptım.

Fonksiyonunuz ideal olarak ilk olarak meleğin menzilinin 0 ile 90 arasında olduğunu kontrol eder.
Sonra, ait olduğu 3 bölümün ne olduğunu belirlemek için ifelse deyimini kullanır ve sonra ilgili doğrusal hesaplamayı yapar (yani output = mX + c ).

2
katma
Şart değil. Bunu elde edebilirsiniz, böylece çıktı 0-1 yerine 0-100 arasında ölçeklenir. Bu sayede tamsayılarla uğraşıyorsunuz, kayan nokta değil. Not: 100 keyfi oldu. Çıkışı 0-128 veya 0-512 veya 0-1000 veya 0-1024 arasında ölçekleyememenizin bir nedeni yoktur. Birden fazla 2 kullanarak, sonucu geri ölçeklendirmek için doğru vardiyaları yapmanız yeterlidir.
katma yazar Yoni Baciu, kaynak
Oldukça zeki, @sa_leinad. Oyla. Bunu transistörlerin önyargılarıyla çalışırken hatırlıyorum.
katma yazar SDsolar, kaynak
Bu kayan nokta çarpmasını içermez mi?
katma yazar Ken Arnold, kaynak

Cos() ve sin() 'ye yaklaşan diğer insanları aradım ve bu cevaba rastladım:

dtb'nin "Öntanımlı bir çeviri dizisini kullanarak Hızlı Sin/Cos" yanıtı

Temel olarak, matematik kitaplığındaki math.sin() işlevinin, bir arama tablosu tablosundan daha hızlı olduğunu hesaplamıştır. Ama anlatabildiğimden, bu bir bilgisayar üzerinde hesaplandı.

Arduino, sin() ve cos() öğelerini hesaplayabilen bir matematik kütüphanesine sahiptir.

2
katma
PC'lerde, bunları hızlı hale getiren FPU'lar vardır. Arduino yapmaz ve bu onu yavaşlatır.
katma yazar Majenko, kaynak
Cevap ayrıca, dizi sınır denetimi gibi şeyler yapan C# için de geçerlidir.
katma yazar Longdaysjourneyintocode, kaynak

generally, look-up table > approximation -> calculation. ram > flash. integer > fixed point > floating point. pre-calclation > real time calculation. mirroring (sine to cosine or cosine to sine) vs. actual calculation/look-up....

her birinin artıları ve eksileri vardır.

Başvurunuz için en uygun olanı görmek için her türlü kombinasyonu yapabilirsiniz.

düzenleme: Hızlı bir kontrol yaptım. 8 bitlik tamsayı çıktısını kullanarak, 1024 sin değerlerini arama tablosuyla hesaplamak, 0,6ms, ve 133ms, floaters veya 200x daha yavaştır.

1
katma

OP için simet bir soru vardı. Ben sinüs fonksiyonunun ilk çeyreğini 0x8000'den 0xffff'e başlayarak işaretsiz 16 bit tam sayı olarak hesaplamak için bir LUT tablosu yapmak istedim. Ve bunu eğlence ve kar için yazmayı bitirdim. Not: Eğer 'if' ifadelerini kullanırsam bu daha verimli çalışır. Ayrıca çok doğru değil, ancak ses sentezleyicide sinüs dalgası için yeterince doğru olur

void sin_lut_ctor(){

//Make a Look Up Table for 511 terms of the sine function.
//Plugin in some polynomials to do some magic
//and you get an aproximation for sines up to π/2.
//

//All sines yonder π/2 can be derived with math

const uint16_t uLut_d = 0x0200; //maximum LUT depth for π/2 terms. 
uint16_t uLut_0[uLut_d];        //The LUT itself.
//Put the 2 above before your void setup() as global variables.
//This coefficients will only work for uLut_d = 511.

uint16_t arna_poly_0 = 0x000a;//11
uint16_t arna_poly_1 = 0x0001;//1
uint16_t arna_poly_2 = 0x0007;//7
uint16_t arna_poly_3 = 0x0001;//1   Precalculated Polynomials
uint16_t arna_poly_4 = 0x0001;//1   
uint16_t arna_poly_5 = 0x0007;//7
uint16_t arna_poly_6 = 0x0002;//2
uint16_t arna_poly_7 = 0x0001;//1

uint16_t Imm_UI_0 = 0x0001;             // Itterator
uint16_t Imm_UI_1 = 0x007c;             // An incrementor that decreases in time

uint16_t Imm_UI_2 = 0x0000;             // 
uint16_t Imm_UI_3 = 0x0000;             //             
uint16_t Imm_UI_4 = 0x0000;              //
uint16_t Imm_UI_5 = 0x0000;              //
uint16_t Imm_UI_6 = 0x0000;             // Temporary variables
uint16_t Imm_UI_7 = 0x0000;              //
uint16_t Imm_UI_8 = 0x0000;              //
uint16_t Imm_UI_9 = 0x0000;              //
uint16_t Imm_UI_A = 0x0000;
uint16_t Imm_UI_B = 0x0000;

uint16_t Imm_UI_A = uLut_d - 0x0001;    // 510

uLut_0[0x0000] = 0x8000;        //Assume that the middle point is 32768 (0x8000 hex)
while (Imm_UI_0 < Imm_UI_A) //Construct a quarter of the sine table
  {
Imm_UI_2++;                                   //Increase temporary variable by 1

Imm_UI_B = Imm_UI_2/arna_coeff_0;           //Divide it with the first coefficient (note: integer division)
Imm_UI_3 += Imm_UI_B;                         //Increase the next temporary value if the first one has increased up to the 1st coefficient
Imm_UI_1 -= Imm_UI_B;                         //Decrease the incrementor if this is the case
Imm_UI_2 *= 0x001 - Imm_UI_B;                 //Set the first temporary variable back to 0

Imm_UI_B = Imm_UI_3/arna_poly_1;           //Do the same thing as before with the next set of temporary variables
Imm_UI_4 += Imm_UI_B;
Imm_UI_1 -= Imm_UI_B;
Imm_UI_3 *= 0x0001 - Imm_UI_B;

Imm_UI_B = Imm_UI_4/arna_poly_2;           //And again... and again... you get the idea.
Imm_UI_5 += Imm_UI_B;
Imm_UI_1 -= Imm_UI_B;
Imm_UI_4 *= 0x0001 - Imm_UI_B;

Imm_UI_B = Imm_UI_5/arna_poly_3;
Imm_UI_6 += Imm_UI_B;
Imm_UI_1 -= Imm_UI_B;
Imm_UI_5 *= 0x0001 - Imm_UI_B;

Imm_UI_B = Imm_UI_6/arna_poly_4;
Imm_UI_7 += Imm_UI_B;
Imm_UI_1 -= Imm_UI_B;
Imm_UI_6 *= 0x0001 - Imm_UI_B;

Imm_UI_B = Imm_UI_7/arna_poly_5;
Imm_UI_8 += Imm_UI_B;
Imm_UI_1 -= Imm_UI_B;
Imm_UI_7 *= 0x0001 - Imm_UI_B;

Imm_UI_B = Imm_UI_8/arna_poly_6;
Imm_UI_9 += Imm_UI_B;
Imm_UI_1 -= Imm_UI_B;
Imm_UI_8 *= 0x0001 - Imm_UI_B;

Imm_UI_B = Imm_UI_9/arna_poly_7          //the last set won't need to increment a next variable so skip the step where you would increase it.
Imm_UI_1 -= Imm_UI_B;
Imm_UI_9 *= 1 - Imm_UI_B;

uLut_0[Imm_UI_0] = (uLut_0[Imm_UI_0 - 0x0001] + Imm_UI_1); //Set the current value as the previous one increased by our incrementor
Imm_UI_0++;              //Increase the itterator
  }   
  uLut_0[Imm_UI_A] = 0xffff; //Lastly, set the last value to 0xffff

  //And there you have it. A sine table with only one if statement (a while loop)
}

Şimdi değerleri geri almak için, bu işlevi kullanın. 0x0000'den 0x0800'e bir değer kabul eder ve LUT'tan uygun değeri döndürür.

uint16_t lu_sin(uint16_t lu_val0)
{
  //Get a value from 0x0000 to 0x0800. Return an appropriate sin(value)
  Imm_UI_0 = lu_val0/0x0200; //determine quadrant
  Imm_UI_1 = lu_val0%0x0200; //Get which value
  if (Imm_UI_0 == 0x0000)
  {
    return uLut_0[Imm_UI_1];
  }
  if (Imm_UI_0 == 0x0001)
  {
    return uLut_0[0x01ff - Imm_UI_1];
  }
  if (Imm_UI_0 == 0x0002)
  {
    return 0xffff - uLut_0[Imm_UI_1];
  }
  if (Imm_UI_0 == 0x0003)
  {
    return 0xffff - uLut_0[0x01ff - Imm_UI_1];
  }
}// I'm using if statements here but similarly to the above code block, 
 //you can do without. just with integer divisions and modulos

Unutmayın, bu, bu göreve yönelik en etkili yaklaşım değil, sadece uygun bir sonuç elde etmek için taylor serilerinin nasıl sonuçlandığını anlayamadım.

1
katma
Kodunuz derlenmiyor: Imm_UI_A iki kez bildirilir, ; ve bazı değişken bildirimleri eksiktir ve uLut_0 global olmalıdır. Gerekli düzeltmelerle lu_sin() hızlıdır (27 ve 42 CPU döngüsü arasında) ancak çok hatalı (maksimum hata ≈ 5.04e-2). Bu “Arnadathian polinomları” nın noktasını alamıyorum: Oldukça ağır bir hesaplama gibi görünüyor, ancak sonuç neredeyse basit bir karesel yaklaşım kadar kötü. Yöntemin ayrıca büyük bir hafıza maliyeti vardır. Tabloyu PC'nizde hesaplamak ve kaynak koduna bir PROGMEM dizisi olarak koymak daha iyi olacaktır.
katma yazar Sprogz, kaynak