Распечатать большой массив 256 в базе 10 в с
У меня есть массив неподписанных символов в c, я пытаюсь напечатать в базе 10, и я застрял. Я думаю, что это будет лучше объяснено в коде, поэтому, учитывая:
unsigned char n[3];
char[0] = 1;
char[1] = 2;
char[2] = 3;
Я хотел бы напечатать 197121.
Это тривиально с небольшими базовыми 256 массивами. Можно просто 1 * 256 ^ 0 + 2 * 256 ^ 1 + 3 * 256 ^ 2.
Однако, если мой массив был размером 100 байт, это быстро становится проблемой. В C нет целочисленного типа размером 100 байт, поэтому для начала я храню числа в массивах без знака.
Как я должен эффективно распечатать этот номер в базе 10?
Я немного растерялся.
5 ответов
Нет простого способа сделать это, используя только стандартную библиотеку C. Вам придется либо написать функцию самостоятельно (не рекомендуется), либо использовать внешнюю библиотеку, такую как GMP.
Например, используя GMP, вы можете сделать:
unsigned char n[100]; // number to print
mpz_t num;
mpz_import(num, 100, -1, 1, 0, 0, n); // convert byte array into GMP format
mpz_out_str(stdout, 10, num); // print num to stdout in base 10
mpz_clear(num); // free memory for num
Когда я увидел этот вопрос, я решил его решить, но в тот момент я был очень занят. В прошлые выходные я мог выиграть несколько призов в свободное время, поэтому я подумал о предстоящем испытании.
Прежде всего, предлагаю вам рассмотреть вышеупомянутый ответ. Я никогда не использую библиотеку GMP, но уверен, что это лучшее решение, чем код ручной работы. Также вас может заинтересовать анализ кода калькулятора bc; он может работать с большими числами, и я использовал, чтобы проверить свой собственный код.
Хорошо, если вы все еще заинтересованы в коде, сделайте это самостоятельно (только с поддержкой языка C и стандартной библиотеки C), возможно, я могу дать вам кое-что.
Прежде всего, немного теории. В базовой числовой теории (модульный арифметический уровень) есть алгоритм, который вдохновляет меня прийти к одному решению; Алгоритм умножения и мощности для решения модуля ^ N m:
Result := 1;
for i := k until i = 0
if n_i = 1 then Result := (Result * a) mod m;
if i != 0 then Result := (Result * Result) mod m;
end for;
Где k - количество цифр, меньшее одной из N в двоичном представлении, а n_i - i двоичная цифра. Например (N - показатель степени):
N = 44 -> 1 0 1 1 0 0
k = 5
n_5 = 1
n_4 = 0
n_3 = 1
n_2 = 1
n_1 = 0
n_0 = 0
Когда мы выполняем операцию модуля как целочисленное деление, мы можем потерять часть числа, поэтому нам нужно всего лишь изменить алгоритм, чтобы не пропустить соответствующие данные.
Вот мой код (позаботьтесь о том, что это специальный код, сильная зависимость от компьютерного арка. В основном я играю с длиной данных языка C, поэтому будьте осторожны, потому что мои данные не могут быть одинаковыми):
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
enum { SHF = 31, BMASK = 0x1 << SHF, MODULE = 1000000000UL, LIMIT = 1024 };
unsigned int scaleBigNum(const unsigned short scale, const unsigned int lim, unsigned int *num);
unsigned int pow2BigNum(const unsigned int lim, unsigned int *nsrc, unsigned int *ndst);
unsigned int addBigNum(const unsigned int lim1, unsigned int *num1, const unsigned int lim2, unsigned int *num2);
unsigned int bigNum(const unsigned short int base, const unsigned int exp, unsigned int **num);
int main(void)
{
unsigned int *num, lim;
unsigned int *np, nplim;
int i, j;
for(i = 1; i < LIMIT; ++i)
{
lim = bigNum(i, i, &num);
printf("%i^%i == ", i, i);
for(j = lim - 1; j > -1; --j)
printf("%09u", num[j]);
printf("\n");
free(num);
}
return 0;
}
/*
bigNum: Compute number base^exp and store it in num array
@base: Base number
@exp: Exponent number
@num: Pointer to array where it stores big number
Return: Array length of result number
*/
unsigned int bigNum(const unsigned short int base, const unsigned int exp, unsigned int **num)
{
unsigned int m, lim, mem;
unsigned int *v, *w, *k;
//Note: mem has the exactly amount memory to allocate (dinamic memory version)
mem = ( (unsigned int) (exp * log10( (float) base ) / 9 ) ) + 3;
v = (unsigned int *) malloc( mem * sizeof(unsigned int) );
w = (unsigned int *) malloc( mem * sizeof(unsigned int) );
for(m = BMASK; ( (m & exp) == 0 ) && m; m >>= 1 ) ;
v[0] = (m) ? 1 : 0;
for(lim = 1; m > 1; m >>= 1)
{
if( exp & m )
lim = scaleBigNum(base, lim, v);
lim = pow2BigNum(lim, v, w);
k = v;
v = w;
w = k;
}
if(exp & 0x1)
lim = scaleBigNum(base, lim, v);
free(w);
*num = v;
return lim;
}
/*
scaleBigNum: Make an (num[] <- scale*num[]) big number operation
@scale: Scalar that multiply big number
@lim: Length of source big number
@num: Source big number (array of unsigned int). Update it with new big number value
Return: Array length of operation result
Warning: This method can write in an incorrect position if we don't previous reallocate num (if it's necessary). bigNum method do it for us
*/
unsigned int scaleBigNum(const unsigned short scale, const unsigned int lim, unsigned int *num)
{
unsigned int i;
unsigned long long int n, t;
for(n = 0, t = 0, i = 0; i < lim; ++i)
{
t = (n / MODULE);
n = ( (unsigned long long int) scale * num[i] );
num[i] = (n % MODULE) + t; // (n % MODULE) + t always will be smaller than MODULE
}
num[i] = (n / MODULE);
return ( (num[i]) ? lim + 1 : lim );
}
/*
pow2BigNum: Make a (dst[] <- src[] * src[]) big number operation
@lim: Length of source big number
@src: Source big number (array of unsigned int)
@dst: Destination big number (array of unsigned int)
Return: Array length of operation result
Warning: This method can write in an incorrect position if we don't previous reallocate num (if it's necessary). bigNum method do it for us
*/
unsigned int pow2BigNum(const unsigned int lim, unsigned int *src, unsigned int *dst)
{
unsigned int i, j;
unsigned long long int n, t;
unsigned int k, c;
for(c = 0, dst[0] = 0, i = 0; i < lim; ++i)
{
for(j = i, n = 0; j < lim; ++j)
{
n = ( (unsigned long long int) src[i] * src[j] );
k = i + j;
if(i != j)
{
t = 2 * (n % MODULE);
n = 2 * (n / MODULE);
// (i + j)
dst[k] = ( (k > c) ? ((c = k), 0) : dst[k] ) + (t % MODULE);
++k; // (i + j + 1)
dst[k] = ( (k > c) ? ((c = k), 0) : dst[k] ) + ( (t / MODULE) + (n % MODULE) );
++k; // (i + j + 2)
dst[k] = ( (k > c) ? ((c = k), 0) : dst[k] ) + (n / MODULE);
}
else
{
dst[k] = ( (k > c) ? ((c = k), 0) : dst[k] ) + (n % MODULE);
++k; // (i + j)
dst[k] = ( (k > c) ? ((c = k), 0) : dst[k] ) + (n / MODULE);
}
for(k = i + j; k < (lim + j); ++k)
{
dst[k + 1] += (dst[k] / MODULE);
dst[k] %= MODULE;
}
}
}
i = lim << 1;
return ((dst[i - 1]) ? i : i - 1);
}
/*
addBigNum: Make a (num2[] <- num1[] + num2[]) big number operation
@lim1: Length of source num1 big number
@num1: First source operand big number (array of unsigned int). Should be smaller than second
@lim2: Length of source num2 big number
@num2: Second source operand big number (array of unsigned int). Should be equal or greater than first
Return: Array length of operation result or 0 if num1[] > num2[] (dosen't do any op)
Warning: This method can write in an incorrect position if we don't previous reallocate num2
*/
unsigned int addBigNum(const unsigned int lim1, unsigned int *num1, const unsigned int lim2, unsigned int *num2)
{
unsigned long long int n;
unsigned int i;
if(lim1 > lim2)
return 0;
for(num2[lim2] = 0, n = 0, i = 0; i < lim1; ++i)
{
n = num2[i] + num1[i] + (n / MODULE);
num2[i] = n % MODULE;
}
for(n /= MODULE; n; ++i)
{
num2[i] += n;
n = (num2[i] / MODULE);
}
return (lim2 > i) ? lim2 : i;
}
Скомпилировать:
gcc -o bgn <name>.c -Wall -O3 -lm //Math library if you wants to use log func
Чтобы проверить результат, используйте прямой вывод как и ввод в bc. Простой командный скрипт:
#!/bin/bash
select S in ` awk -F '==' '{print $1 " == " $2 }' | bc`;
do
0;
done;
echo "Test Finished!";
У нас есть и массив без знака int (4 байта), где мы храним в каждом int массива число из 9 цифр ( % 1000000000UL); следовательно, num[0] у нас будут первые 9 цифр, num[1], у нас будет цифра от 10 до 18, num[2]... Я использую условную память для работы, но улучшение может сделать это с динамической памятью. Хорошо, но какова длина массива? (или сколько памяти нам нужно выделить?). Используя калькулятор bc (bc -l с mathlib), мы можем определить, сколько цифр имеет число:
l(a^N) / l(10) // Natural logarith to Logarithm base 10
Если мы знаем цифры, мы знаем количество целых чисел, которое нам нужно:
( l(a^N) / (9 * l(10)) ) + 1 // Truncate result
Если вы работаете со значением, таким как (2^k)^N, вы можете разрешить его логарифмом с помощью следующего выражения:
( k*N*l(2)/(9*l(10)) ) + 1 // Truncate result
определить точную длину целочисленного массива. Пример:
256^800 = 2^(8*800) ---> l(2^(8*800))/(9*l(10)) + 1 = 8*800*l(2)/(9*l(10)) + 1
Значение 1000000000UL (10 ^ 9) константа очень важно. Константа, такая как 10000000000UL (10^10), не работает, потому что может вызвать переполнение и не выявить его (попробуйте, что случится с константой с номерами 16^16 и 10 ^ 10), а константа еще немного, такая как 1000000000UL (10^8), верна, но нам нужно зарезервировать больше памяти и сделать больше шагов. 10^9 является ключевой константой для unsigned int из 32 битов и unsigned long long int из 64 битов.
Код состоит из двух частей: Умножение (легко) и Мощность на 2 (сложнее). Умножение - это просто умножение, масштабирование и распространение целочисленного переполнения. Принцип ассоциативности в математике требует принципа, обратного принципу, поэтому, если k(A + B + C), мы хотим kA + kB + kC, где число будет k*A*10^18 + k*B*10. ^ 9 + k C. Очевидно, что операция k C может генерировать число больше 999 999 999, но никогда не больше 0xFF FF FF FF FF FF FF FF FF. Число, превышающее 64 бита, никогда не может встречаться при умножении, потому что C - это целое число без знака в 32 бита, а k - это короткое число без знака, равное 16 битам. В случае сусла у нас будет этот номер:
k = 0x FF FF;
C = 0x 3B 9A C9 FF; // 999999999
n = k*C = 0x 3B 9A | 8E 64 36 01;
n % 1000000000 = 0x 3B 99 CA 01;
n / 1000000000 = 0x FF FE;
После Mul k B нам нужно добавить 0x FF FE из последнего умножения C (B = k B + (C / module)) и т. Д. (У нас есть 18-битное арифметическое смещение, достаточное, чтобы гарантировать правильные значения).
Власть сложнее, но в сущности та же проблема (умножение и сложение), поэтому я дам несколько хитростей по поводу мощности кода:
- Типы данных важны, очень важны
- Если вы попытаетесь умножить целое число без знака на целое число без знака, вы получите еще одно целое число без знака. Используйте явное приведение, чтобы получить unsigned long long int и не потерять данные.
- Всегда используйте неподписанный модификатор, не забывайте это!
- Мощность на 2 может напрямую изменить 2 индекса перед текущим индексом
- GDB твой друг
Я разработал другой метод, который добавляет большие числа. Эти последние я не доказываю так много, но я думаю, что это работает хорошо. Не будь жестоким со мной, если есть ошибка.
...и это все!
PD1: разработан в
Intel(R) Pentium(R) 4 CPU 1.70GHz
Data length:
unsigned short: 2
unsigned int: 4
unsigned long int: 4
unsigned long long int: 8
Числа, такие как 256^1024 он тратит:
real 0m0.059s
user 0m0.033s
sys 0m0.000s
Bucle, который вычисляет I ^ I, где я иду к I = 1 ... 1024:
real 0m40.716s
user 0m14.952s
sys 0m0.067s
Для чисел, таких как 65355^65355, потраченное время безумно.
PD2: Мой ответ слишком поздний, но я надеюсь, что мой код будет полезным.
PD3: Извините, объясните мне по-английски, это один из моих худших недостатков!
Последнее обновление: у меня только что возникла идея, что с тем же алгоритмом, но с другой реализацией, улучшается отклик и уменьшается объем используемой памяти (мы можем использовать полностью биты беззнакового целого). Секрет: n^2 = n * n = n * (n - 1 + 1) = n * (n - 1) + n. (Я не буду делать этот новый код, но если кому-то интересно, может быть после экзаменов...)
Я не знаю, нужно ли вам еще решение, но я написал статью об этой проблеме. Он показывает очень простой алгоритм, который можно использовать для преобразования произвольного длинного числа с основанием X в соответствующее число основания Y. Алгоритм написан на языке Python, но на самом деле он занимает всего несколько строк и не использует Python. магия. Мне также требовался такой алгоритм для реализации на Си, но я решил описать его с помощью Python по двум причинам. Во-первых, Python хорошо читается любым, кто понимает алгоритмы, написанные на языке псевдопрограммирования, и, во-вторых, мне не разрешено публиковать C-версию, потому что я сделал это для своей компании. Просто посмотрите, и вы увидите, как легко эта проблема может быть решена в целом. Реализация в C должна быть прямой...
Вот функция, которая делает то, что вы хотите:
#include <math.h>
#include <stddef.h> // for size_t
double getval(unsigned char *arr, size_t len)
{
double ret = 0;
size_t cur;
for(cur = 0; cur < len; cur++)
ret += arr[cur] * pow(256, cur);
return ret;
}
Это выглядит отлично читаемым для меня. Просто передайте unsigned char * массив, который вы хотите конвертировать и размер. Обратите внимание, что это не будет идеально - для произвольной точности я предлагаю заглянуть в библиотеку GNU MP BigNum, как уже предлагалось.
В качестве бонуса, мне не нравится, что вы храните свои числа в порядке с прямым порядком байтов, так что вот вариант, если вы хотите хранить числа с базовым 256 в порядке с прямым порядком байтов:
#include <stddef.h> // for size_t
double getval_big_endian(unsigned char *arr, size_t len)
{
double ret = 0;
size_t cur;
for(cur = 0; cur < len; cur++)
{
ret *= 256;
ret += arr[cur];
}
return ret;
}
Просто вещи для рассмотрения.
Это может быть слишком поздно или слишком неуместно, чтобы сделать это предположение, но не могли бы вы сохранить каждый байт в виде двух основных 10 цифр (или одной базовой 100) вместо одной базовой 256? Если вы еще не реализовали деление, то это означает, что у вас есть только сложение, вычитание и, возможно, умножение; это не должно быть слишком трудно конвертировать. Как только вы это сделаете, распечатать это будет тривиально.
Поскольку меня не удовлетворили другие предоставленные ответы, я решил сам написать альтернативное решение:
#include <stdlib.h>
#define BASE_256 256
char *largenum2str(unsigned char *num, unsigned int len_num)
{
int temp;
char *str, *b_256 = NULL, *cur_num = NULL, *prod = NULL, *prod_term = NULL;
unsigned int i, j, carry = 0, len_str = 1, len_b_256, len_cur_num, len_prod, len_prod_term;
//Get 256 as an array of base-10 chars we'll use later as our second operand of the product
for ((len_b_256 = 0, temp = BASE_256); temp > 0; len_b_256++)
{
b_256 = realloc(b_256, sizeof(char) * (len_b_256 + 1));
b_256[len_b_256] = temp % 10;
temp = temp / 10;
}
//Our first operand (prod) is the last element of our num array, which we'll convert to a base-10 array
for ((len_prod = 0, temp = num[len_num - 1]); temp > 0; len_prod++)
{
prod = realloc(prod, sizeof(*prod) * (len_prod + 1));
prod[len_prod] = temp % 10;
temp = temp / 10;
}
while (len_num > 1) //We'll stay in this loop as long as we still have elements in num to read
{
len_num--; //Decrease the length of num to keep track of the current element
//Convert this element to a base-10 unsigned char array
for ((len_cur_num = 0, temp = num[len_num - 1]); temp > 0; len_cur_num++)
{
cur_num = (char *)realloc(cur_num, sizeof(char) * (len_cur_num + 1));
cur_num[len_cur_num] = temp % 10;
temp = temp / 10;
}
//Multiply prod by 256 and save that as prod_term
len_prod_term = 0;
prod_term = NULL;
for (i = 0; i < len_b_256; i++)
{ //Repeat this loop 3 times, one for each element in {6,5,2} (256 as a reversed base-10 unsigned char array)
carry = 0; //Set the carry to 0
prod_term = realloc(prod_term, sizeof(*prod_term) * (len_prod + i)); //Allocate memory to save prod_term
for (j = i; j < (len_prod_term); j++) //If we have digits from the last partial product of the multiplication, add it here
{
prod_term[j] = prod_term[j] + prod[j - i] * b_256[i] + carry;
if (prod_term[j] > 9)
{
carry = prod_term[j] / 10;
prod_term[j] = prod_term[j] % 10;
}
else
{
carry = 0;
}
}
while (j < (len_prod + i)) //No remaining elements of the former prod_term, so take only into account the results of multiplying mult * b_256
{
prod_term[j] = prod[j - i] * b_256[i] + carry;
if (prod_term[j] > 9)
{
carry = prod_term[j] / 10;
prod_term[j] = prod_term[j] % 10;
}
else
{
carry = 0;
}
j++;
}
if (carry) //A carry may be present in the last term. If so, allocate memory to save it and increase the length of prod_term
{
len_prod_term = j + 1;
prod_term = realloc(prod_term, sizeof(*prod_term) * (len_prod_term));
prod_term[j] = carry;
}
else
{
len_prod_term = j;
}
}
free(prod); //We don't need prod anymore, prod will now be prod_term
prod = prod_term;
len_prod = len_prod_term;
//Add prod (formerly prod_term) to our current number of the num array, expressed in a b-10 array
carry = 0;
for (i = 0; i < len_cur_num; i++)
{
prod[i] = prod[i] + cur_num[i] + carry;
if (prod[i] > 9)
{
carry = prod[i] / 10;
prod[i] -= 10;
}
else
{
carry = 0;
}
}
while (carry && (i < len_prod))
{
prod[i] = prod[i] + carry;
if (prod[i] > 9)
{
carry = prod[i] / 10;
prod[i] -= 10;
}
else
{
carry = 0;
}
i++;
}
if (carry)
{
len_prod++;
prod = realloc(prod, sizeof(*prod) * len_prod);
prod[len_prod - 1] = carry;
carry = 0;
}
}
str = malloc(sizeof(char) * (len_prod + 1)); //Allocate memory for the return string
for (i = 0; i < len_prod; i++) //Convert the numeric result to its representation as characters
{
str[len_prod - 1 - i] = prod[i] + '0';
}
str[i] = '\0'; //Terminate our string
free(b_256); //Free memory
free(prod);
free(cur_num);
return str;
}
Идея, лежащая в основе всего этого, основана на простой математике. Для любого числа с основанием 256 его представление с основанием 10 можно рассчитать как:num[i]*256^i + num[i-1]*256^(i-1) + (···) + num[2]*256^2 + num[1]*256^1 + num[0]*256^0
который расширяется до:(((((num[i])*256 + num[i-1])*256 + (···))*256 + num[2])*256 + num[1])*256 + num[0]
Итак, все, что нам нужно сделать, это шаг за шагом умножить каждый элемент числового массива на 256 и добавить к нему следующий элемент, и так далее... Таким образом мы можем получить число с основанием 10.