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

Question

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

typedef struct {
    uint64_t low, high;
} uint128;

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

Теперь я хочувыведите такое значение в базе 10, используя printf.Вероятно, мне нужно деление на 10, но деление пока не реализовано.

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

РЕДАКТИРОВАТЬ: Мне нравятся все решения, которые вы придумали.Вы великолепны.

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").

РЕДАКТИРОВАТЬ: вот пример (он напечатает 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.Поскольку наибольшее 64-разрядное число имеет длину 20 цифр, это означает, что все 19-разрядные десятичные числа могут быть напечатаны таким образом, но поскольку наибольшее 128-разрядное число имеет длину 39 цифр, мы не можем разбить его только на 2 части., поскольку есть вероятность, что мы можем получить 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 и300Е36 границы.Напишите цифру и вычтите ближайшую меньшую границу.НапримерЕсли число 234.6776E36, то ближайшая меньшая граница - 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-й цифры оправдана, потому что если вы умножите число рядом с ним, вы получите переполнение, если остаток больше 34E36.