#математика #c #алгоритм #cpp
Доброго времени суток! Возник вопрос: как очень большое десятичное число(количество десятичных знаков ~10^4) быстро перевести в двоичную систему счисления? P.S. так как ни один тип такое число не уместит, то число считывается в строку, ну или на лету обрабатывать нужно P.P.S сторонние либы использовать нельзя
Ответы
Ответ 1
В общем, решил я так: Из второго тома Д.Кнута алгоритм(спасибо @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#include #include 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; } Ответ 2
@miramentis, ловите. #include#include #include #include 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. Ответ 3
Ребята, которые 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Ответ 4
Перевести исходное число в систему счисления с основанием 109 (можно по Кнуту, можно через sscanf()). "Цифры" хранить в 32-битовом целом формате. Перевести "уголком" полученное число в систему счисления с основанием 232, при делении использовать расширенные умножения и сдвиги. Запись остатков-"цифр" в массив результата идёт в обратном порядке. Перевести каждую новую "цифру" в 32-символьную двоичную строку, начиная с последней (например, через sprintf()). В последней строке убрать ведущие нули, в остальных - сохранить.
Комментариев нет:
Отправить комментарий