Доброго времени суток!
Возник вопрос: как очень большое десятичное число(количество десятичных знаков ~10^4) быстро перевести в двоичную систему счисления?
P.S. так как ни один тип такое число не уместит, то число считывается в строку, ну или на лету обрабатывать нужно
P.P.S сторонние либы использовать нельзя
-
1Я правильно понимаю: вы умеете перевести медленно, и вам нужно оптимизировать алгоритм?– VladD17 окт 2013 в 15:20
-
2GMP попробуйте. Правда не знаю насколько будет быстро.– dzhioev17 окт 2013 в 15:33
-
@dzhioev к сожалению, сторонние либы использовать нельзя.– miramentis17 окт 2013 в 15:39
-
ну тогда как в школу учили, дели на 2 и записывай=)– spirit17 окт 2013 в 15:41
-
2Алгоритмы есть, скопирую комментарий из другого вопроса: > Вам нужна глава 4.4 «Искусства программирования» Кнута (это второй том). --- Почему не айс? Нормальный такой себе способ.– VladD17 окт 2013 в 15:53
4 ответа
В общем, решил я так:
Из второго тома Д.Кнута алгоритм(спасибо @VladD за то что указал где искать):
для числа, имеющего M+1>1 разрядов:
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;
}
-
@miramentis, какие-то странные маипуляции у Вас с ungetc(). Если я правильно понял, Вы каждый бит (двоичный разряд) в храните в одном байте и работаете с ними?– avp23 окт 2013 в 12:00
-
так как указатель arr имеет тип bool, то и индексирование будет побитовое, а не побайтовое. 34000 ячеек, так как при N=10^10000 нам потребуется lb(10^10000)~=33220 (я округлил в коде)ячеек - худший случай. согласен, не рационально выделять под любые числа такой объем памяти, хотя с другой стороны это ~4кб оперативной памяти... при желании, полагаю, можно модифицировать для более рационального выделения памяти 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)); })– avp23 окт 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); } все– avp24 окт 2013 в 12:18 -
1В одном комментарии не помещается. -- Также убираем
memmove()
, "моделируем" сдвиг на 1 и 3, передавая адреса перед реальными битами числа, зная что фиктивные начальные биты это нули. Думаю это несколько ускорит программу. -- Ну, и чтобы не запутывать основную идею, напишем функцию, которая читает очередную десятичную цифру и возвращает массив ее бит и и их количество. Она же возвращает, скажем ноль, когда закончатся десятичные цифры. Остается распечататьres
(в обратном порядке и скорректировавcurbits
, чтобы старший бит был 1).– avp24 окт 2013 в 12:28
@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
.
-
@miramentis, смотрите, какая идея пришла в голову. Можно вообще избавиться от копирования в while(...). Достаточно установить res и prev_res не на начало массивов, а отступив 3/4 его размера и после каждой цифры сдвигать указатели на 3 к началу и обменивать их содержимое. Т.е. получаемое двоичное число будет строиться одновременно влево и вправо (за счет битов переноса), в четных итерациях в array1[], а в нечетных в array2[]. -- Обдумайте, все должно получиться. (2 недели я не буду отвечать, отъезжаю).– avp5 ноя 2013 в 21:13
Ребята, которые 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
- Перевести исходное число в систему счисления с основанием 109 (можно по Кнуту, можно через sscanf()). "Цифры" хранить в 32-битовом целом формате.
- Перевести "уголком" полученное число в систему счисления с основанием 232, при делении использовать расширенные умножения и сдвиги. Запись остатков-"цифр" в массив результата идёт в обратном порядке.
- Перевести каждую новую "цифру" в 32-символьную двоичную строку, начиная с последней (например, через sprintf()). В последней строке убрать ведущие нули, в остальных - сохранить.