Najszybszy sposób na uzyskanie liczby całkowitej 10 i liczby całkowitej 10?

Jeśli sprzęt nie obsługuje operacji modułu lub podziału, potrzeba więcej cykli procesora, aby zasymulować moduł / podział przez oprogramowanie. Czy istnieje szybszy sposób obliczenia podziału i modułu, jeśli operandem jest 10?

W moim projekcie często muszę obliczać moduł całkowity 10. W szczególności pracuję nad PIC16F i muszę pokazać liczbę na wyświetlaczu LCD. Obsługiwane są 4 cyfry, więc są 4 wywołania funkcji modułu i podziału (implementacja oprogramowania). To znaczy, jak poniżej:

digit = number % 10;    // call to an expensive function
number /= 10;           // call to an expensive function
somehow_lit_segments();

digit = number % 10;    // call to an expensive function
number /= 10;           // call to an expensive function
somehow_lit_segments();

digit = number % 10;    // call to an expensive function
number /= 10;           // call to an expensive function
somehow_lit_segments();

digit = number % 10;    // call to an expensive function
number /= 10;           // call to an expensive function
somehow_lit_segments();

Istnieją inne obszary, które używają podobnego kodu.

Oto algorytm binarny do BCD, którego użyłem kilka lat temu w oparciu o jeden znaleziony tutaj . Użyłem zewnętrznego sterownika wyświetlacza BCD do 7-segmentowego, aby wynik mógł zostać zapisany w odpowiednich portach bezpośrednio jako spakowany BCD dla wyjścia.

Jest to dość szybkie, jeśli masz PIC mnożnik sprzętowy, użyłem PIC18F97J60. Jeśli nie masz mnożnika sprzętowego na swoim PIC, rozważ użycie kombinacji shift + add do mnożenia.

To pobiera 16-bitową liczbę całkowitą bez znaku i zwraca zapakowany BCD z 5 cyframi, można go zmodyfikować i przyspieszyć dla 4 cyfr. Wykorzystuje shift + dodatki do przybliżonego dzielenia przez 10, ale biorąc pod uwagę ograniczony zakres wejściowy, jest to dokładne do tego zastosowania. Możesz również spakować wynik w inny sposób, aby dopasować go do sposobu jego wykorzystania.

void intToPackedBCD( uint16_t n, uint8_t *digits ) {

    uint8_t d4, d3, d2, d1, d0, q;  //d4 MSD, d0 LSD

    d1 = (n>>4)  & 0xF;
    d2 = (n>>8)  & 0xF;
    d3 = (n>>12) & 0xF;

    d0 = 6*(d3 + d2 + d1) + (n & 0xF);
    q = (d0 * 0xCD) >> 11;
    d0 = d0 - 10*q;

    d1 = q + 9*d3 + 5*d2 + d1;
    q = (d1 * 0xCD) >> 11;
    d1 = d1 - 10*q;

    d2 = q + 2*d2;
    q = (d2 * 0x1A) >> 8;
    d2 = d2 - 10*q;

    d3 = q + 4*d3;
    d4 = (d3 * 0x1A) >> 8;
    d3 = d3 - 10*d4;

    digits[0] = (d4<<4) | (d3);
    digits[1] = (d2<<4) | (d1);
    digits[2] = (d0<<4);
}

Zakładając, że liczby całkowite bez znaku, dzielenie i mnożenie mogą być tworzone na podstawie przesunięć bitów. Z podziału i mnożenia (liczb całkowitych) można wyprowadzić modulo.

Aby pomnożyć przez 10:

y = (x << 3) + (x << 1);

Dzielenie przez 10 jest trudniejsze. Znam kilka algorytmów podziału. Jeśli dobrze pamiętam, istnieje sposób szybkiego podzielenia przez 10 przy użyciu przesunięć bitowych i odejmowania, ale nie pamiętam dokładnej metody. Jeśli to nieprawda, to jest to algorytm dzielenia, który zarządza <130 cyklami . Nie jestem pewien, jakiej mikrofonu używasz, ale możesz z niego korzystać w jakiś sposób, nawet jeśli musisz go przenieść.

EDYCJA: Ktoś mówi podczas przepełnienia stosu , jeśli możesz tolerować trochę błędów i mieć duży rejestr tymczasowy, to zadziała:

temp = (ms * 205) >> 11;  // 205/2048 is nearly the same as /10

Zakładając, że masz dzielenie i mnożenie, modulo jest proste:

mod = x - ((x / z) * z)

Możesz konwertować z binarnego na spakowany BCD bez żadnego podziału za pomocą algorytmu podwójnego dabble . Używa tylko shift i dodaje 3 .

Na przykład konwertuj 243 ₁₀ = 11110011 ₂ na binarne

0000 0000 0000   11110011   Initialization
0000 0000 0001   11100110   Shift
0000 0000 0011   11001100   Shift
0000 0000 0111   10011000   Shift
0000 0000 1010   10011000   Add 3 to ONES, since it was 7
0000 0001 0101   00110000   Shift
0000 0001 1000   00110000   Add 3 to ONES, since it was 5
0000 0011 0000   01100000   Shift
0000 0110 0000   11000000   Shift
0000 1001 0000   11000000   Add 3 to TENS, since it was 6
0001 0010 0001   10000000   Shift
0010 0100 0011   00000000   Shift
   2    4    3
       BCD

Ten algorytm jest bardzo wydajny, gdy nie jest dostępny dzielnik sprzętowy. Więcej niż tylko lewe przesunięcie o 1 jest używane, więc jest szybkie, nawet gdy przerzutka lufy nie jest dostępna

W zależności od wymaganej liczby cyfr możesz użyć metody brutalnej siły ( d- numer wejściowy, t- wyjściowy ciąg ASCII):

t--;
if (d >= 1000) t++; *t = '0'; while (d >= 1000) { d -= 1000; *t += 1; }
if (d >= 100) t++; *t = '0'; while (d >= 100) { d -= 100; *t += 1;}
if (d >= 10) t++; *t = '0'; while (d >= 10) { d -= 10; *t += 1;}
t++; *t = '0' + d;

Możesz także zmienić wiele ifs w pętlę, z mocami dziesięciu uzyskanymi przez mnożenie lub tablicę odnośników.

Ta nota aplikacyjna opisuje algorytmy arytmetyki BCD, w tym konwersję z binarnej na BCD i odwrotnie. Przypis autorstwa Atmel, czyli AVR, ale opisane algorytmy są niezależne od procesora.

Nie mam dobrej odpowiedzi, ale na naszej siostrzanej stronie Stack Overflow znajduje się świetna dyskusja na ten sam temat podziału i optymalizacji modulo.

Czy masz wystarczająco dużo pamięci, aby zaimplementować tabelę odnośników?

Hackers Delight ma artykuł na temat optymalnych algorytmów podziału.

Czy zastanawiałeś się przez cały czas nad utrzymywaniem tej wartości jako BCD (przy użyciu prostych specjalnych procedur „przyrostu BCD” i „dodawania BCD”), zamiast utrzymywania tej wartości w formie binarnej i konwertowania do BCD w razie potrzeby (przy użyciu trudniejszej do zrozumienia „konwersji” z „podprogramu binarnego na BCD”)?

Pewnego razu wszystkie komputery zapisywały wszystkie dane jako cyfry dziesiętne (dziesięciopozycyjne koła zębate, dwie z pięciu lamp próżniowych z kodem, BCD itp.), A to dziedzictwo wciąż trwa do dziś. (patrz Dlaczego chipy zegara czasu rzeczywistego używają BCD ).

The PICList jest niesamowitym źródłem informacji dla osób programowania procesorów PIC.

Konwersja BCD

Czy zastanawiałeś się nad użyciem gotowego i sprawdzonego podprogramu binarnego do BCD specjalnie zoptymalizowanego dla PIC16F?

W szczególności ludzie na PICList spędzili dużo czasu na optymalizacji konwersji binarnej na BCD na PIC16F. Procedury te (każda zoptymalizowana ręcznie dla określonego rozmiaru) zostały podsumowane w „Metodach matematycznych konwersji mikrokontrolera PIC” http://www.piclist.com/techref/microchip/math/radix/index.htm

dzielenie liczb całkowitych i mod

W procesorach takich jak PIC16F podprogram specjalizujący się w dzieleniu przez stałą jest często znacznie szybszy niż procedura ogólnego przeznaczenia „dziel zmienną A przez zmienną B”. Możesz umieścić swoją stałą (w tym przypadku „0,1”) w „Generowaniu kodu dla stałego mnożenia / dzielenia” http://www.piclist.com/techref/piclist/codegen/constdivmul.htm lub sprawdź konserwowane procedury w pobliżu http://www.piclist.com/techref/microchip/math/basic.htm .

Biorąc pod uwagę mnożnik sprzętowy 8x8, można obliczyć divmod-10 o dowolnym rozmiarze, używając procedury, która oblicza go dla liczby 12-bitowej w zakresie 0-2559 za pomocą procedury:

1. Załóż oryginalny numer w OrigH: OrigL
2. Podziel oryginalny numer przez dwa i zapisz go w TempH: TempL
3. Dodaj MSB z TempL * 51 do LSB z TempH * 51. To jest przybliżony iloraz
4. Pomnóż przybliżony iloraz przez 10, odrzucając MSB wartości.
5. Odejmij LSB tego wyniku od LSB pierwotnego numeru.
6. Jeśli ta wartość wynosi 10 lub więcej (maks. Będzie to 19), odejmij 10 i dodaj 1 do przybliżonego ilorazu

Sugerowałbym napisanie procedury divmod, w której MSB liczby będzie w W, a LSB wskazane przez FSR; procedura powinna przechowywać iloraz w FSR z pomniejszeniem i pozostawić resztę w W. Aby podzielić 32-bitową długość przez 10, należy użyć czegoś takiego:

  movlw 0
  lfsr 0, _number + 3; Wskaż MSB
  wywołaj _divmod10_step
  wywołaj _divmod10_step
  wywołaj _divmod10_step
  wywołaj _divmod10_step

Krok divmod-6 byłby bardzo podobny, z wyjątkiem użycia stałych 85 i 6 zamiast 51 i 10. W obu przypadkach spodziewałbym się, że divmod10_step wyniesie 20 cykli (plus cztery dla wywołania / powrotu), więc krótki divmod10 będzie wynosić będzie około 50 cykli, a długi divmod10 wyniesie około 100 (jeśli jeden przypadek specjalny pierwszego kroku, można zapisać kilka cykli).

to może nie być najszybszy, ale jest to prosty sposób.

 a = 65535;

    l = 0;
    m = 0;
    n = 0;
    o = 0;
    p = 0;

    while (a >= 10000)
    {   a -= 10000;
        l += 1;
    }
     while (a >= 1000)
    {   a -= 1000;
        m += 1;
    }
     while (a >= 100)
    {   a -= 100;
        n += 1;
    }
     while (a >= 10)
    {   a -= 10;
        o += 1;
    }
     while (a > 0)
    {   a -= 1;
        p += 1;
    }