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()). В последней строке убрать ведущие нули, в остальных - сохранить.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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