Pähkinäkö?

Tuolla kalliilla meinaan tilannetta jossa: M on muunnettava luku, L muunnokseen kuluvat loopit.
M L
----------------
1 1
9 9
10 1
100 1
200 2
900 9
990 18
...
999 27
...
999999999 81

Muuten hyvä.

tosin aika "kallis" kirjoitti:

Tuolla kalliilla meinaan tilannetta jossa: M on muunnettava luku, L muunnokseen kuluvat loopit.
M L
----------------
1 1
9 9
10 1
100 1
200 2
900 9
990 18
...
999 27
...
999999999 81

Muuten hyvä.

Lue lisää

Se sisin looppi on ihan vähennyslaskua rekistereissä (toivottavasti). Jakolasku, toinen vaihtoehto, ei paljoa auta, koska looppikierrosten määrä moninkertaistuisi, vaikka jaetaan vain 10:llä.

Binaarihakukin (ensiksi vähennettäisiin esim. 80000, sitten 40000, 20000, 10000, jne. veisi vähintään saman ajan ylimääräisen logiikan vuoksi.

Pelkkään 32-bittiseen kertolaskuun menee pahimmillaan 32 loopin kierrosta. Jakolaskussa menee jaettavan ja jakajan ekan ykkösbitin hakuun jo kohtuullinen määrä looppeja. Naivisti jakajaa vasemmalle shiftailussakin kestää. Binaarihakujakolasku taas vaatisi 48-bittisen rekisterin toteuttamisen. Eli ≤≤16 -≥ ≤≤ 24/ ≤≤ 8, jne. Tai sitten pitäisi rajoittaa jakaja 16 bittiin. 14 bittiset luvut voi tietysti jakaa 10:llä nopsasti vaikka "tmp = (x≤≤3) (x≤≤2); tmp = (tmp≤≤8) (tmp≤≤4) x; x = tmp≥≥15;", mutta mitäpä tuokaan auttaa ilman nopeaa tapaa laskea 10 jakojäännös... Tietysti voisi kertoa 10 (x≤≤3) x x ja vähentää sen jaettavasta... ja mikrokontrollerin aikaa palaa.

Onko siinä prossussa muuten 32 shift left/right immediate argumentilla? Eli x≤≤7, vai tekeekö se 7 kertaa x≤≤1. En tietysti tarkoita x≤≤y.

Jos nopeus on tärkeää, cacheta vaikka 10 viimeisintä lukua. Koodaa konekielellä. Huijaa. Esim. laskurin saa nopeiten manipuloimalla itse numeron ASCII-merkkijonoa! Käsittele numeroita konekielellä *vain* BCD-aritmetiikalla (melkein kaikki taskulaskimet tekevät näin).

#include ≤stdio.h≥
#include ≤stdlib.h≥
#include ≤stdint.h≥

char * tulostaLuku(uint32_t x, char * buf)
{
…uint32_t jaettu10;
…uint32_t jakojaannos;
…*buf--=0;
…if(x)
…while(x≥0)
…{
……/* 32-bit: toimii alle 1301720 */
……/* 64-bit: toimii alle 4194309 */
……jaettu10 = (x≤≤2) (x≤≤3);
……jaettu10 = (jaettu10≤≤8) (jaettu10≤≤4) jaettu10 (((jaettu10≤≤4) x jaettu10)≥≥8);
……jaettu10 ≥≥= 15;

……/* 32-bit: alle 81920
……… 64-bit: alle 262149
……*/
/*
……jaettu10 = (x≤≤2) (x≤≤3);
……jaettu10 = (jaettu10≤≤4) jaettu10 (((jaettu10≤≤4) jaettu10 x)≥≥8);
……jaettu10 ≥≥= 11;
*/
……/* 32/64-bit: 16389 */
/* jaettu10 = (x≤≤2) (x≤≤3);
……jaettu10 = (jaettu10≤≤8) (jaettu10≤≤4) x;
……jaettu10 ≥≥= 15;
*/
……jakojaannos = x - jaettu10 -jaettu10 - (jaettu10≤≤3);
……*buf-- = '0' jakojaannos;
……x=jaettu10;
…}
…else
…{
……*buf='0';
……return buf;
…}
…return buf;
}

int main()
{
…char buf[32];
…char checkbuf[32];
…uint64_t i;
…char *buffer = buf 16;
…char *retbuf;
…for(i=0; i≤300000000; i )
…{
……sprintf(checkbuf, "%lu", i); //itoa(i, checkbuf);
……retbuf = tulostaLuku(i, buf);
……if(strcmp(checkbuf, retbuf))
……{
………printf("virhe %lu (%s)\n", i, retbuf);
………break;
……}
…}
}