Vinnigste manier om te skakel binêre om desimale?

Question

Ek het vier unsigned 32-bit heelgetalle wat'n ongetekende 128-bit heelgetal, in klein endian om:

typedef struct {
    unsigned int part[4];
} bigint_t;

Ek wil graag om te skakel hierdie getal in sy desimale string verteenwoordiging en uitvoer dit na'n lêer.

Nou, ek is met behulp van'n bigint_divmod10 funksie te verdeel deur die aantal 10, die behoud van die spoor van die res.Ek noem hierdie funksie herhaaldelik, uitdruk van die res as'n syfer, totdat die nommer is nul.Dit is redelik stadig.Is dit die vinnigste manier om dit te doen?As dit so is, is daar'n slim manier om die uitvoering van hierdie funksie wat ek nie sien nie?Ek het probeer om te kyk na GMP se get_str.c, nie , maar ek vind dit mooi ondeurdringbare.

EDIT:hier is die vinnigste kode ek was in staat om te kom met vir die divmod10 funksie:

static unsigned uint128_divmod10(uint128 *value)
{
    unsigned int a = value->word[3];
    unsigned int b = value->word[2];
    unsigned int c = value->word[1];
    unsigned int d = value->word[0];

    unsigned int diva = a / 5;
    unsigned int divb = b / 5;
    unsigned int divc = c / 5;
    unsigned int divd = d / 5;

    value->word[3] = diva;
    value->word[2] = divb;
    value->word[1] = divc;
    value->word[0] = divd;

    unsigned int moda = a - diva*5;
    unsigned int modb = b - divb*5;
    unsigned int modc = c - divc*5;
    unsigned int modd = d - divd*5;

    unsigned int mod = 0;
    mod += moda;
    unsigned int carryb = mod*858993459;
    mod += modb;
    if (mod >= 5) {
        mod -= 5;
        carryb++;
    }
    unsigned int carryc = mod*858993459;
    mod += modc;
    if (mod >= 5) {
        mod -= 5;
        carryc++;
    }
    unsigned int carryd = mod*858993459;
    mod += modd;
    if (mod >= 5) {
        mod -= 5;
        carryd++;
    }

    uint128_add(value, carryd, 0);
    uint128_add(value, carryc, 1);
    uint128_add(value, carryb, 2);

    if (value->word[0] & 1) {
        mod += 5;
    }
    uint128_shift(value, -1);
    return mod;
}

waar die voeg funksie is gedefinieer as:

static void uint128_add(uint128 *value, unsigned int k, unsigned int pos)
{
    unsigned int a = value->word[pos];
    value->word[pos] += k;
    if (value->word[pos] < a) {
        // overflow
        for (int i=pos+1; i<4; i++) {
            value->word[i]++;
            if (value->word[i]) {
                break;
            }
        }
    }
}

Answer 1

Dit hang af wat anders wat jy doen met die getalle.Jy kan die handel af'n effense verlies in die ruimte doeltreffendheid en'n beskeie verlies in die doeltreffendheid van multiprecision rekenkundige in ruil vir'n baie doeltreffende omskakeling na en van desimale.Die sleutel is om te doen multiprecision rekenkundige met'n basis wat is'n krag van 10, eerder as'n krag van 2.

Byvoorbeeld, jy kan gebruik om die basis 10,000, waar jy pak'n syfer in'n 16-bit woord en jy doen jou rekenkundige op die syfers in die 32-bit heelgetalle.(As jy op'n 64-bit masjien wat jy kan dubbel dat en doen basis 1,000,000,000.) Hierdie soort van die kode is relatief doeltreffende timewise, hoewel nie heeltemal so vinnig as wat die gebruik van die moedertaal krag van die twee, want jy kan nie neem voordeel van die voer bietjie op die hardeware.En jy kan nie verteenwoordig as baie heelgetalle in die dieselfde aantal van stukkies.Maar dit is'n gefluit by die omskakeling na en van desimale, want jy kry om te sit die individuele syfers sonder enige lang-afdeling.

As jy nodig het om te verteenwoordig die volle omvang van die getalle van nul tot ((1 << 128) - 1), jy kan nog steeds doen, maar voeg'n ekstra syfer, so jou nommers sal groter wees.

As dit blyk uit wat jy regtig nodig het om die ekstra ruimte/spoed (miskien is jy besig met'n baie van die kriptografiese 128-bit berekeninge) dan is die metode van simultanous div/mod deur 10 is die vinnigste metode wat ek weet.Die enigste ander truuk is dat as klein heelgetalle is algemeen, jy kan hanteer hulle spesiaal.(Dit is, as die drie belangrikste 32-bit woorde is almal nul, net gebruik maak van die inheemse afdeling te skakel.)

Is daar'n slim manier om die uitvoering van hierdie funksie wat ek nie sien nie?

Dave Hanson se C Koppelvlakke en Implementering het'n lang hoofstuk op multiprecision rekenkundige.Die verdeling van'n groot aantal deur'n enkele syfer is'n spesiale geval dat het hierdie doeltreffende implementering:

int XP_quotient(int n, T z, T x, int y) {
    int i;
    unsigned carry = 0;
    for (i = n - 1; i >= 0; i--) {
        carry = carry*BASE + x[i];
        z[i] = carry/y;
        carry %= y;
    }
    return carry;
}

Vir die volle begrip, dit regtig help om die boek, maar die bron-kode is nog steeds'n baie makliker om te verstaan as die GNU bron-kode.En jy kan maklik aanpas om dit te gebruik basis 10,000 (dit gebruik tans basis 256).

Opsomming:as jou prestasie knelpunt is die omskakeling van desimale, te implementeer multiprecision rekenkundige met'n basis wat is'n krag van 10.As jou masjien se moedertaal woord grootte is 32 en jy is met behulp van C-kode, gebruik 10,000 in'n 16-bit woord.

Answer 2

As jou waardes is meestal minder as ULLONG_MAX (18446744073709551615) Ek sal probeer om gebruik te maak vir hulle sprintf(buf,"%llu",ullong_val). Ek is seker dit is nogal goed geoptimaliseer in standaard biblioteek, maar die ontleding van formaat sal 'n paar siklusse neem al.

Anders Ek sal 'n bigint_divmod1000000000 (of beter naam mod10to9) funksie en gebruik dit skep. Dit sou nodig 9 keer minder verdeel as bigint_divmod10.

Answer 3

Soek tafel van 8 stukkies. Jy kan 4 lookup tafels van 256 nommers. Eerste is 0-256 vir LSB grepe, Tweede tafel is eerste tafel vermenigvuldig met 256 en so aan.

So wanneer jy jou nommer som nommers van lookup tafel nodig het. Wanneer jy die toevoeging van wat jy kan byvoeg as bunary en gaan later 'n keer oor elke byte te fix owerflows.

Voorbeeld aantal 0x12345678 In die eerste lookup tafel is daar onder adres (0x78 = 120) so 0x010200 is eerste getal in die tweede tabel onder (0x56 = 87) is 0x0202000106 (0x56 in Desember is 22.016) in die derde tabel wat jy wil hou 0x03040007080702 het en onder verlede etiket op 0x12 jy 0x030001090809080808 (hierdie pas nie in 32 bit rekenkundige, maar dat jy allredy know)

som dan op hierdie nommers (as binêre bumbers) en gaan 'n keer, byte deur byte vir oorloop kode in vir lus is iets soos

s=carry+val[i];
val[i]=val[i]&10
carry=s/10; 
//you can put last two operations in table

As ons tel bedrywighede wat nodig is vir hierdie.

1. (soek in tabelle en die toevoeging van) 4 lookup tafels. 16 toevoegings (hou in gedagte dat wanneer jy nie nodig het om uit te voer oor owerflow, becuase hulle kan nie ocur)
2. 'n keer in elke stap 3 operatins 16 stappe om te slaag.

passimistic boonste gebind 6 * 16 = 100 operasies.

EDIT:

Hier is c ++ kode, en is 30% vinniger as naïef implementering.

#include <iostream>
#include <stdint.h>
#include <array>

static uint64_t lu[4][256];

constexpr uint64_t lookup_value(uint64_t n) {
  uint64_t r = 0;
  uint64_t t = 1;
  while (n) {
    uint64_t rem = n % 10;
    n /= 10;
    r += rem * t;
    t *= 256;
  }
  return r;
}

void make_lu() {
  uint64_t step = 1;
  for (int j = 0; j < 4; ++j) {
    uint64_t n = 0;
    for (int i = 0; i < 256; ++i) {
      lu[j][i] = lookup_value(n);
      n += step;
    }
    step *= 256;
  }
}

struct DivMod {
  uint8_t div;
  uint8_t rem;
};

static DivMod dm[256];

void make_dm() {
  for (int i = 0; i < 256; ++i) {
    dm[i].div = i / 10;
    dm[i].rem = i % 10;
  }
}

void init() {
  make_lu();
  make_dm();
}

uint64_t b2d(uint64_t n) {
  uint64_t r = 0;
  for (int i = 0; i < 4; ++i) {
    r += lu[i][(n >> (i * 8)) & 0xff];
  }
  uint64_t r2 = 0;
  uint64_t of = 0;
  for (int i = 0; i < 8; ++i) {
    uint64_t v = ((r >> (i * 8)) & 0xff) + of;
    DivMod &x = dm[v];
    of = x.div;
    r2 += uint64_t(x.rem) << (i * 8);
  }
  return r2;
}

int main() {
  init();
  uint64_t n;
  std::cin >> n;
  std::cout << std::hex << b2d(n) << "\n";
  return 0;
}

Answer 4

Vir verdere navrae, in plaas van die implementering van 'n uint128 tipe, ek het net gebruik die karakters van Die string direk. Dit blyk te wees baie vinniger wees as om uit string na uint128 en terug.

Answer 5

Die mees onmiddellike speedup sal kom uit lining die omskakeling, eerder as 'n beroep funksies; dit kan so eenvoudig wees soos die nasien bigint_divmod10() inline , of met behulp van profiel gelei optimalisering as wat aangebied word deur jou samesteller.

Answer 6

Ek weet hierdie vraag is oud, maar ek wil bydra as niemand sit 'n manier vermy die afdeling siklus. Hierdie een gebruike pow2, ek het nie die maatstaf getoets, maar in teorie moet vinniger wees as enige ander, en ook kan tweaked in die pow funksie sowel.

#include <iostream>
#include <cmath>
using namespace std;

#define MathBintodec(arr,len)({int dec=0;int ci_;for(ci_=len;ci_--;)dec+=arr[ci_]*pow(2,len-ci_-1);dec;})

int main(){
    int r[]={1,0,0,1,0,0};
    cout<<MathBintodec(r,6)<<endl;
}

Uitgawe: 36