6

Доброго времени суток!
Возник вопрос: как очень большое десятичное число(количество десятичных знаков ~10^4) быстро перевести в двоичную систему счисления?
P.S. так как ни один тип такое число не уместит, то число считывается в строку, ну или на лету обрабатывать нужно
P.P.S сторонние либы использовать нельзя

11
  • 1
    Я правильно понимаю: вы умеете перевести медленно, и вам нужно оптимизировать алгоритм?
    – VladD
    17 окт 2013 в 15:20
  • 2
    GMP попробуйте. Правда не знаю насколько будет быстро.
    – dzhioev
    17 окт 2013 в 15:33
  • @dzhioev к сожалению, сторонние либы использовать нельзя.
    – miramentis
    17 окт 2013 в 15:39
  • ну тогда как в школу учили, дели на 2 и записывай=)
    – spirit
    17 окт 2013 в 15:41
  • 2
    Алгоритмы есть, скопирую комментарий из другого вопроса: > Вам нужна глава 4.4 «Искусства программирования» Кнута (это второй том). --- Почему не айс? Нормальный такой себе способ.
    – VladD
    17 окт 2013 в 15:53

4 ответа 4

2

В общем, решил я так:
Из второго тома Д.Кнута алгоритм(спасибо @VladD за то что указал где искать): для числа, имеющего M+1>1 разрядов: alt text

    ENT1  M-1         j ← m-1
    LDA   INPUT+M     U ← u_m
2H  MUL   =10=
    SLAX  5
    ADD   INPUT,1     U ← 10U + u_j
    DEC1  1
    J1NN  2B          Повторять при m > j ≥ 0

и мой код на C:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
using namespace std;
int main() {
//обрабатываем случай, когда у числа всего 1 десятичный разряд
char first = getc(stdin), second = getc(stdin);
ungetc(second,stdin); ungetc(first,stdin);
if(second=='\n')  ungetc('0',stdin);
//выделяем память "с запасом" под худший случай - 10^10000 десятичных знаков ~=32кб
bool* arr = (bool*)malloc(sizeof(bool)*34000);
bool* arr1;
int end = 0;
for(int i=0;i<34000;i++,arr[i]=false);
int a=(int)getc(stdin)-48;
//записываем самый старший разряд числа "как в школе учили" делением на 2
do{
    arr[end]=(bool)(a&1);
    a>>=1;
    end++;
}while(a);
a=(int)getc(stdin)-48;
//обрабатываем остальные разряды
while(a!=-38){
    //реализуем умножение текущего накопленного значения на 10:
    //x*10 = x*8 + x*2 == x<<3 + x<<1
    arr1 = (bool*)malloc(sizeof(bool)*(end+4));
    arr1[0]=false;
    //записываем число сдвинутое на 1
    memcpy(arr1+1,arr,end+3);
    //сдвигаем само число на 3
    memmove(arr+3,arr,end);
    arr[0]=false;arr[1]=false;arr[2]=false;
    end+=3;
    //суммируем выше полученные числа
    bool nextOverhead,overhead=false;
    for(int i=1;i<=end;i++){
        nextOverhead=((arr[i]&&arr1[i]) || (arr[i]&&overhead) || (arr1[i]&&overhead));
        arr[i]^=arr1[i]^=overhead;
        overhead=nextOverhead;
    }
    if(arr[end])end++;
    //прибавляем следующий разряд
    overhead=false;
    for(int i=0;a || nextOverhead;i++){
        nextOverhead=((arr[i] && ((bool)(a&1))) || 
                                  (arr[i] && overhead)    || 
                                (((bool)(a&1)) && overhead));
        arr[i]^=overhead^=((bool)(a&1));
        overhead=nextOverhead;
        a>>=1;
    }
    if(arr[end])end++;
    a=(int)getc(stdin)-48;
    free(arr1);
}
for(int i=end-1;i>=0;i--)
    printf("%d",arr[i]);
return 0;

}

14
  • @miramentis, какие-то странные маипуляции у Вас с ungetc(). Если я правильно понял, Вы каждый бит (двоичный разряд) в храните в одном байте и работаете с ними?
    – avp
    23 окт 2013 в 12:00
  • так как указатель arr имеет тип bool, то и индексирование будет побитовое, а не побайтовое. 34000 ячеек, так как при N=10^10000 нам потребуется lb(10^10000)~=33220 (я округлил в коде)ячеек - худший случай. согласен, не рационально выделять под любые числа такой объем памяти, хотя с другой стороны это ~4кб оперативной памяти... при желании, полагаю, можно модифицировать для более рационального выделения памяти
    – miramentis
    23 окт 2013 в 18:06
  • 1
    Ваши действия с ungetc() как-то вводят в заблуждение. Вы бы просто словами описали формат своих данных. Наверное для начала проще всего сделать одну длинную строку десятичных цифр. И читать ее, пока цифра. Тогда никаких ungetc() вообще не нужно. -- По поводу упаковки. Если Вы хотите манипулировать битами в массиве байт по индексу бита, то можно так #define CLRBIT(s,i) ({ int _i = (i); (s)[_i >> 3] &= ~(1 << (_i & 7)); }) #define SETBIT(s,i) ({ int _i = (i); (s)[_i >> 3] |= (1 << (_i & 7)); }) #define TSTBIT(s,i) ({ int _i = (i); (s)[_i >> 3] & (1 << (_i & 7)); })
    – avp
    23 окт 2013 в 21:25
  • 1
    @miramentis, а что, теперь все вроде нормально. Я бы тоже делал с распакованными (1 бит на байт). Только malloc() в цикле убрал. Просто завел бы 2 массива по максимуму и сделал функцию, суммирующую 3 числа. Т.е. получилось бы что-то такое char a1[N], a2[N], a[4], *res, *p_res; int n, curbits = 1; memset(a1, 0, sizeof(a1)); memcpy(a2, a1, sizeof(a1)); res = a1 + 3; p_res = a2 + 3; while ((n = getdbits(a, stdin)) > 0) { curbits = add3(res, p_res - 3, curbits + 3, p_res - 1, curbits + 1, a, n); memcpy(p_res, res, curbits); } все
    – avp
    24 окт 2013 в 12:18
  • 1
    В одном комментарии не помещается. -- Также убираем memmove(), "моделируем" сдвиг на 1 и 3, передавая адреса перед реальными битами числа, зная что фиктивные начальные биты это нули. Думаю это несколько ускорит программу. -- Ну, и чтобы не запутывать основную идею, напишем функцию, которая читает очередную десятичную цифру и возвращает массив ее бит и и их количество. Она же возвращает, скажем ноль, когда закончатся десятичные цифры. Остается распечатать res (в обратном порядке и скорректировав curbits, чтобы старший бит был 1).
    – avp
    24 окт 2013 в 12:28
0

@miramentis, ловите.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>

int
getdecbits (char arr[])
{
  int end = -1, a;

  if (isdigit(a = getchar())) {
    end = 0;
    a -= '0';
    do {
      arr[end++] = a & 1;
    } while ( a >>= 1 );
  }

  return end;
}

// вычисление y = x * 10 + d как  x >> 3 + x >> 1 + d
// складывает x3[], x1[] и d[] 
//  (двоичные, один бит в байте, старшие справа)
//  (в x3[] и x1[] д.б. досаточно старших нулевых бит)
// Returns длину результата >= max(l1, l2, l3)
int 
add3 (char res[], char x3[], int l1, 
       char x1[], int l2, char d[], int l3)
{
  int i, s = 0;
  for (i = 0; i < l3; i++) {
    s += x3[i] + x1[i] + d[i];
    res[i] = s & 1;
    s >>= 1;
  }
  for (; i < l2; i++) {
    s += x3[i] + x1[i];
    res[i] = s & 1;
    s >>= 1;
  }
  for (; i < l1 && s; i++) {
    s += x3[i];
    res[i] = s & 1;
    s >>= 1;
  }
  if (s)
    do {
      res[i++] = s & 1;
    } while ( s >>= 1 );
  else for (; i < l1; i++)
         res[i] = x3[i];

  return i;
}

int
correct_nbits (char a[], int l)
{
  while (l > 0 && !a[l])
    l--;
  return l + 1;
}

#define N (64 * 1024)

int 
main ()
{
  char array1[N], array2[N], a[4], *res, *prev_res;
  int nbits, curbits = 1;

  memset(array1, 0, sizeof(array1));
  memcpy(array2, array1, sizeof(array1));
  res = array1 + 3;
  prev_res = array2 + 3;
  while ((nbits = getdecbits(a)) > 0) {
    curbits = add3(res, prev_res - 3, curbits + 3, 
                      prev_res - 1, curbits + 1, a, nbits);
    memcpy(prev_res, res, curbits);
  }

  printf("Result: (%d bits)\n", curbits = correct_nbits(res, curbits));
  for (int i = curbits - 1; i >= 0; i--)
  //  for (int i = 0; i < curbits; i++)
    putchar(res[i] + '0');
  puts("");

  return puts("End") == EOF;
}

avp@avp-ubu1:~/hashcode$ gcc -std=gnu99 bigdec-bin.c 
avp@avp-ubu1:~/hashcode$ ./a.out
15
Result: (4 bits)
1111
End
avp@avp-ubu1:~/hashcode$ ./a.out
32
Result: (6 bits)
100000
End
avp@avp-ubu1:~/hashcode$ 
avp@avp-ubu1:~/hashcode$ gcc -std=gnu99 bigdec-bin.c -O3
avp@avp-ubu1:~/hashcode$ ./mkdigs 30
367535629127093606261879202375
avp@avp-ubu1:~/hashcode$ ./mkdigs 3 | ./a.out
Result: (9 bits)
101101111
End
avp@avp-ubu1:~/hashcode$ time ./mkdigs 10000 | ./a.out >/dev/null

real    0m0.288s
user    0m0.284s
sys     0m0.000s
avp@avp-ubu1:~/hashcode$

В исходника размер массивов 64КБ, достаточно для преобразования

avp@avp-ubu1:~/hashcode$ time ./mkdigs 19700 | ./a.out >/dev/null

real    0m0.890s
user    0m0.892s
sys     0m0.000s
avp@avp-ubu1:~/hashcode$

примерно 19700 десятичных цифр. А вот исходника ./mkdigs не сохранилось, но он тривиален, на основе rand() % 10.

1
  • @miramentis, смотрите, какая идея пришла в голову. Можно вообще избавиться от копирования в while(...). Достаточно установить res и prev_res не на начало массивов, а отступив 3/4 его размера и после каждой цифры сдвигать указатели на 3 к началу и обменивать их содержимое. Т.е. получаемое двоичное число будет строиться одновременно влево и вправо (за счет битов переноса), в четных итерациях в array1[], а в нечетных в array2[]. -- Обдумайте, все должно получиться. (2 недели я не буду отвечать, отъезжаю).
    – avp
    5 ноя 2013 в 21:13
0

Ребята, которые 10 триллионов знаков пи вычислили как-то сделали за O(n*log(n)^2). Можно скачать их исходники и попытаться понять, как. Или спросить. http://www.numberworld.org/y-cruncher/#Algorithms

Возможно, они делят с остатком исходное число на 10^N, где N - такое, чтобы количество цифр в целом и остатке было одинаковым. А далее - рекурсивно для полученных половинок.

Upd: если вам не интересен алгоритм O(n*log(n)^2), пристойный алгоритм O(n^2) -

static const int bitsInCell = 28;
unsigned int data[32000 / bitsInCell + 10];
int i, dataLen = 1;
char ch;

memset(data, 0, sizeof(data));
for (i = 0; i < 8; i++)
{
    ch = getc(stdin);
    if (!isdigit(ch))
        break;
    data[0] = data[0] * 10 + ch - '0';
}

if (isdigit(ch))
    while (true)
    {
        ch = getc(stdin);
        if (!isdigit(ch))
            break;

        // Умножаем на 10
        data[0] = data[0] * 10 + ch - '0';

        for (i = 0; i < dataLen; i++)
        {
            unsigned int carryValue = data[i] / (1U << bitsInCell);

            data[i] %= 1U << bitsInCell;
            data[i + 1] = data[i + 1] * 10 + carryValue;
        }
        if (data[dataLen] > 0)
             dataLen++;
    }

// Вывод битов из data
0
  1. Перевести исходное число в систему счисления с основанием 109 (можно по Кнуту, можно через sscanf()). "Цифры" хранить в 32-битовом целом формате.
  2. Перевести "уголком" полученное число в систему счисления с основанием 232, при делении использовать расширенные умножения и сдвиги. Запись остатков-"цифр" в массив результата идёт в обратном порядке.
  3. Перевести каждую новую "цифру" в 32-символьную двоичную строку, начиная с последней (например, через sprintf()). В последней строке убрать ведущие нули, в остальных - сохранить.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.