C: печать BigInteger в базе 10

Question

Я использую эту структуру для представления 128bit целых чисел:

typedef struct { 
    uint64_t low, high; 
} uint128; 

(Если вы не можете указать мне на быстрые 128bit целочисленных библиотеки я не могу изменить, что)

Теперь я хочу напечатать такое значение в базе 10, используя printf. Для этого мне, вероятно, понадобится деление на 10, но никакого деления еще не реализовано.

Как я могу это сделать? Решение не должно быть суперэффективным, если оно работает.

EDIT: Мне нравятся все решения, с которыми вы столкнулись. Ты обалденный.

Answer 1

void printu128(uint128 n) { 
    int d[39] = {0}, i, j; 
    for (i = 63; i > -1; i--) { 
    if ((n.high >> i) & 1) d[0]++; 
    for (j = 0; j < 39; j++) d[j] *= 2; 
    for (j = 0; j < 38; j++) d[j+1] += d[j]/10, d[j] %= 10; 
    } 
    for (i = 63; i > -1; i--) { 
    if ((n.low >> i) & 1) d[0]++; 
    if (i > 0) for (j = 0; j < 39; j++) d[j] *= 2; 
    for (j = 0; j < 38; j++) d[j+1] += d[j]/10, d[j] %= 10; 
    } 
    for (i = 38; i > 0; i--) if (d[i] > 0) break; 
    for (; i > -1; i--) putchar('0'+d[i]); 
} 

Answer 2

Если вы не хотите реализовать деление на 128-битное значение, вы можете предварительно скопировать несколько (~ 40) 128-битных значений, которые представляют степень 10, и использовать вычитание.

Фактически только более высокий qword обрабатывается таким образом, потому что для нижней части вы можете использовать printf("%I64d").

EDIT: Вот пример (он будет печатать short используя только арифметику на char):

unsigned char pow10[][2] = { 
    {0, 1}, // 1 
    {0, 10}, // 10 
    {0, 100}, // 100 
    {3, 0xE8}, // 1k 
    {0x27, 0x10}}; // 10k == 0x2710 

#define HIGH 0 
#define LOW 1 

void print_dec(unsigned char H, unsigned char L){ 
    unsigned char L1; 
    int pwr = 4, ctr = 0; 
    while (pwr >= 0){ 
     int c = pow10[pwr][LOW] > L; 
     L1 = L - pow10[pwr][LOW]; 
     if (H >= pow10[pwr][HIGH] + c){  
      H -= pow10[pwr][HIGH] + c; 
      L = L1; 
      ctr++; 
     } else { 
      printf("%d", ctr); 
      ctr = 0; 
      pwr--; 
      //here we could add a check for H to be 0, so that we could use 
      //printf() for lower half. we just have to be careful with 
      //leading zeroes in L, the simpliest way is to use printf("%03d",L) 
     }; 
    }; 
    printf("\n"); 
}; 

int main(){ 
    unsigned short n = 12345; 
    printf("%d should be ", n); 
    print_dec((n >> 8) & 0xFF, n & 0xFF); 
    return 0; 
}; 

Вы можете использовать меньшее количество предварительно вычисленных полномочий 10, но он будет делать это медленнее (напр, располагая их с шагом 100 составит ctr находиться в диапазоне 0..99.

Answer 3

Предполагая, что вы уже реализованы функции для выполнения математику на uint128, можно разбить число вверх в 3 части и использовать встроенный в 64-битном возможности печати printf. Поскольку lar gest 64-битное число составляет 20 цифр, это означает, что все 19-значные десятичные числа могут быть напечатаны таким образом, но поскольку наибольшее 128-битное число составляет 39 цифр, мы не можем разбить его на две части, поскольку есть вероятность, что мы получим 20-значное число, большее, чем самое большое 64-битное число.

Это один из способов сделать это, разделив сначала на 10 , чтобы получить коэффициент не более 3,402,823,669,209,384,634. Затем мы разделим остаток (сам по себе не более 10) на 10 , чтобы получить другое частное и остальное каждый менее 10 , которые оба подходят в 64-битовом целое.

void print_uint128(uint128 value) 
{ 
    // First power of 10 larger than 2^64 
    static const uint128 tenToThe20 = {7766279631452241920ull, 5ull}; 
    static const uint128 tenToThe10 = {10000000000ull, 0ull}; 

    // Do a 128-bit division; assume we have functions to divide, multiply, and 
    // subtract 128-bit numbers 
    uint128 quotient1 = div128(value, tenToThe20); 
    uint128 remainder1 = sub128(value, mul128(quotient, tenToThe20)); 
    uint128 quotient2 = div128(remainder1, tenToThe10); 
    uint128 remainder2 = sub128(remainder1, mul128(remainder1, tenToThe10)); 

    // Now print out theresult in 3 parts, being careful not to print 
    // unnecessary leading 0's 
    if(quotient1.low != 0) 
     printf("%llu%010llu%010llu", quotient1.low, quotient2.low, remainder2.low); 
    else if(quotient2.low != 0) 
     printf("%llu%010llu", quotient2.low, remainder2.low); 
    else 
     printf("%llu", remainder2.low); 
} 

Answer 4

Вы можете использовать умножение для печати номера.

1. В 2 о 340E36, в первую очередь определить ведущие цифры, сравнивая число с 100E36, 200E36 и 300E36 границ. Напишите цифру и вычтите ближайшую меньшую границу. E. g. Если число равно 234.6776E36, то ближайший меньший bounary - 200E36, цифра - «2», а после вычитания вы должны получить 34.6776E36.

2. Теперь получите следующую цифру, используя сравнение с цифрами 10E36 ... 90E36. Конечно, это 128-битное сравнение. Напишите цифру и вычитайте меньшую границу, как указано выше. (Для 34.6776E36 выше цифры «3», граница равна 30E36, а остаток - 4.6776E36)

3. Затем умножьте число на 10 и повторите со стадии 2, всего 38 раз, чтобы напечатать каждую цифру. (4.6776E36 -> 46.776E36 ...)

UPD: Добавлено вычитание, которое я пропустил первым. И примеры.

UPD2: Необходимость выделенного шага для 1-й цифры равна jus, потому что, если вы умножаете число рядом с ним, вы должны получить переполнение, если остаток больше 34E36.