Dela med 10 utan matte-bibliotek

[bearing]

Ja, jag menade med det syntax som används i C. '0' är ASCII-koden av ASCII-siffran 0.

[TomasL]

He he, jo, men det var ju inte så tydligt i ditt inlägg att det var det du avsåg

Ja, men för att omvandla ett heltal till en textsträng så måste du först omvandla talet till BCD.

Nej, det behöver du inte, det går alldeles utmärkt att omvandla till text utan att gå via BCD.

[Nerre]

Visa mig ett exempel på sån kod.

[bearing]

sprintf (buffer, "%d", a);

[TomasL]

Hittade denna lilla roliga kod:

Kod: Markera allt

int x;
char output[5];
output[4] = 0;
x = 1023;
output[3] = '0' + DivideByTenReturnRemainder(&x);
output[2] = '0' + DivideByTenReturnRemainder(&x);
output[1] = '0' + DivideByTenReturnRemainder(&x);
output[0] = '0' + x;

samt

int DivideByTenReturnRemainder(int * p)
{
/* This code has been tested for an input range of 0 to 1023. */
int x;
x = *p;
*p = ((x << 4) + (x << 3) + x + (x >> 1) + (x >> 3)) >> 8;
return x - ((*p << 3) + (*p << 1));
}

Enligt uppgift funkar denna i området 0-1023

[Icecap]

Intressant - eller inte! Jag har testat lite av dessa koder, de behöver dels en massa RAM för allt shiftande, det blir väldigt med bytes att addera och 0-1023? Vilken nytta har man av det? Som minst ska den klara en full WORD utan fel och är den skalbar uppåt är det bra.

Jag har räknat på den typ av funktion och det blir orimligt mycket bytes som ska shiftas och adderas, Double dabble vinner lätt! Och pratar vi long är Double dabble vinnaren sedan länge.

Så nej, tyvärr är den länk lika usel som de många andra med samma innehåll som florerar i tråden.

[bearing]

Ja, antagligen går det snabbare att med några loopar subtrahera 10000, 1000, 100, 10 istället för alla dessa shiftningar. Ifall processorn hade haft barrell-shift kanske skiftmetoden gått snabbare. Men då har den å andra sidan sannolikt även mul, och kanske till och med div.

Det känns dock som att Double-dabble blir grymt mycket slöare ifall man skriver den i C jämfört med assembler, eftersom att man inte har tillgång till Carry-flaggorna och roteringsinstruktionerna.

[Nerre]

Svårigheten med en effektiv double-dabble är väl det här med att man ska addera 3 till de nibbles som är högre än 4.

Men som jag ser det borde man kunna göra det med maskning för att slippa barrel rotation eller långa skift. Om man har tre nibbles, så istället för att skifta ner så maskar man och jämför med större värde.

aaaabbbbcccc

Maska med 111100000000
Kolla om värdet är större än 010000000000, i såna fall addera 001100000000

Maska med 000011110000
Kolla om värdet är större än 000001000000, i såna fall addera 000000110000

Maska med 000000001111
Kolla om värdet är större än 000000000100, i såna fall addera 000000000011

[bearing]

Man kan också strunta i den höga nibbeln, och bara spara siffror i den låga nibbeln. Tar lite mer plats (1 byte per siffra), men gör jämförelsen med 4, och BCD-ASCII-konverteringen enklare. Man får väl prova lite för att se vad som blir bäst. Ofta finns det ju ett sätt som tar minst ram, ett som tar minst FLASH, och ett tredje som tar minst antal klockcykler.

[Nerre]

Fast skift-operationerna blir väl svårare då?

[bearing]

Ja precis, det blir en avvägning. Får testa lite och se vilket sätt som blir snabbast, eller vad man nu önskar. Sen kanske det ändras också beroende på vilken processor koden kompileras för.

[gkar]

Vill du verkligen dividera snabbt och har en snabb mul så kan du göra det med en multiplikation istället i lämpliga intervall.

a = (a * 6554) >> 16;
Ta ARM tex som saknar HW division men har en mycket snabb multiplikation, då rockar detta!


Ännu mycket mer tokfort är att använda en tabell.
Skapa en tabell som innehåller alla tal du vill skicka.

Låt data lite Motorola 68020+ idag för omväxlingsskull.

; Lägg data i d0.w
snabbprint:
lea tab(pc,d0.w*8),a0 ; Ta adressen på tabellen relativt PC, lägg på PC, ta d0.w och multiplicera med 8 och lägg ihop allt i a0. *2 eller *4 för småtabeller.
bsr.s uart_send_null_termed_string ;a0 innehåller adressen att skriva ut från.
rts

Vad är formlerna för att komma fram till dessa konstanter t.ex 6554 och antal skiftningar osv?

Enkel huvudräkning. Kåden är ingenting jag filat på, utan bara hur jag skulle lösa det direkt, om jag hade behovet.
2^16 = 65536. 65536/10 avrundat uppåt-> 6554.

Någon får gärna komma med ett snabbare förslag!

[bearing]

Jag satt och testade att implementera Double-dabble för 8-bitars tal på en ATtiny igår kväll. Kom på att man kan strunta i dom fyra första skiftningarna, så sparar man en nibble, vilket gör implementationen lättare/snabbare i C, eftersom att man kan köra hela algoritmen i en uint16. Samt att man så klart sparar 4 skiftningar á 2 cykler. Man kan även strunta i att shifta helt och hållet, och bara flytta masken/jämförelsen/additionen en bit åt höger för varje steg. Dock tog det längre tid i min implementation, eftersom att masken ofta hamnar "över byte-gränserna", som gör att jämförelsen behöver göras i 16-bitar, istället för 8 bitar i det första fallet.

Dock verkar det som att man inte vinner så mycket med Double-dabble med 8 bitar, jämfört med min sendDec8() som finns tidigare i tråden. Själva binär-till-BCD-omvandlingen i sendDec8 tar 50-100 cykler. Double-dabble funktionerna nedan har jag skrivit inline, utan loopar, för att det ska gå så snabbt som möjligt. Det bästa jag fick till var ca 60-cykler för double_dabble8. Den är alltså ca 20% snabbare än sendDec8 i snitt, och då har jag inte kollat ifall sendDec går att förbättra. Jag hade väntat mig större skillnad.

Ni får gärna skriva ifall ni ser något sätt att förbättra koden. Ifall man deklarerar funktionen static, så att den körs inline, tar den ca 12 cykler kortare tid. Dock innebär ju det att programmet tar mycket större plats ifall funktionen anropas ofta.

Kod: Markera allt

/* 57-61 cycles */
uint16_t double_dabble8(uint8_t input)
{
    uint16_t bcds;
        
    bcds = input;
    if ((bcds & 0x00FF) >= 0x00A0) bcds += 0x0060;  //Shift 1 2 3 nibble check/add
    if ((bcds & 0x00FF) >= 0x0050) bcds += 0x0030;  //Shift 4 nibble check/add
    bcds <<= 1;                                     //Shift 5
    if ((bcds & 0x00FF) >= 0x0050) bcds += 0x0030;  //Nibble check/add
    bcds <<= 1;                                     //Shift 6
    if ((bcds >> 8)     >= 0x0005) bcds += 0x0300;  //Nibble check/add
    if ((bcds & 0x00FF) >= 0x0050) bcds += 0x0030;  //Nibble check/add
    bcds <<= 1;                                     //Shift 7
    if ((bcds & 0x0F00) >= 0x0500) bcds += 0x0300;  //Nibble check/add
    if ((bcds & 0x00FF) >= 0x0050) bcds += 0x0030;  //Nibble check/add
    bcds <<= 1;                                     //Shift 8
    
    return bcds;
}

/* 73-74 cycles */
uint16_t double_dabble8_noshift(uint8_t input)
{
    uint16_t bcds;
    
    bcds = input;
    if (bcds >=  (5 << 5)) bcds += (3 << 5);           //Shifts 1 2 3 nibble check/add
    if ((bcds & (0xF << 4)) >= (5 << 4)) bcds += (3 << 4);  //Shift 4 nibble check/add
    if ((bcds & (0xF << 3)) >= (5 << 3)) bcds += (3 << 3);  //Shift 5 nibble check/add
    if ((bcds & (0xF << 6)) >= (5 << 6)) bcds += (3 << 6);  //Shift 6 nibble check/add
    if ((bcds & (0xF << 2)) >= (5 << 2)) bcds += (3 << 2);  //Shift 6 nibble check/add
    if ((bcds & (0xF << 5)) >= (5 << 5)) bcds += (3 << 5);  //Shift 7 nibble check/add
    if ((bcds & (0xF << 1)) >= (5 << 1)) bcds += (3 << 1);  //Shift 7 nibble check/add

    return bcds;
}

Utöver binär-bcd-omvandlingen ska ju bcd omvandlas till ASCII, och det verkar ta ca 15 cykler till.

[Icecap]

Har nu lekt lite med Double dabble, det har varit ganska sporadisk pga. jobb. Känns ibland för jävligt att man inte kan göra roliga saker bara för att man ska jobba...

Kod: Markera allt

typedef unsigned long DWORD;
typedef unsigned short WORD;
typedef unsigned char BYTE;

void Double_Dabble(DWORD Value)
  {
  BYTE Ctr, Index;
  union
    {
    BYTE  Bytes[4];
    DWORD Long;
    } Result;
  Result.Long = 0;
  for(Ctr = 0; Ctr < sizeof(DWORD)*8; Ctr++)
    {
    Index = 4;
    while(Index)
      {
      Index--;
      if((Result.Bytes[Index]       ) > 0x4F) Result.Bytes[Index] += 0x30;
      if((Result.Bytes[Index] & 0x0F) > 0x04) Result.Bytes[Index] += 0x03;
      }
    Result.Long <<= 1;
    if(*((BYTE*)&Value+1) & 0x80) Result.Bytes[0] |= 0x01;
    Value <<= 1;
    }
  // The printout section comes here:
  Send_UART_1_Byte((Result.Bytes[2] & 0x0F) + '0');
  Send_UART_1_Byte((Result.Bytes[1]   >> 4) + '0');
  Send_UART_1_Byte((Result.Bytes[1] & 0x0F) + '0');
  Send_UART_1_Byte((Result.Bytes[0]   >> 4) + '0');
  Send_UART_1_Byte((Result.Bytes[0] & 0x0F) + '0');
  }

Fungerar utmärkt på en PIC. Funderar på om jag ska bygga ut det hela till att kunde skriva ut negativa tal också.

[bearing]

Går det snabbare jämfört med andra metoder? typ att loopa 10 varv per siffra?

Även om själva omvandlingen blir lite långsammare med loop*10 kanske hela funktionen går snabbare, eftersom att man skickar en siffra i taget, och därmed kör UART parallellt med beräkningarna.

Negativa tal borde ju vara enkelt. Bara göra en koll i början ifall invärdet är negativt, och då skriva ut ett minustecken, och vända på talet.