Question

У меня есть массив неподписанных символов в 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?

Я немного растерялся.

saxi · Answer 1 · 08 июня 2009

Когда я увидел этот вопрос, я решил его решить, но в тот момент я был очень занят. В прошлые выходные я мог выиграть несколько призов в свободное время, поэтому я подумал о предстоящем испытании.

Прежде всего, предлагаю вам рассмотреть вышеупомянутый ответ. Я никогда не пользуюсь библиотекой GMP, но уверен, что это лучшее решение, чем код ручной работы. Также вас может заинтересовать анализ кода калькулятора bc; он может работать с большими числами, и я тестировал свой собственный код.

Хорошо, если вы все еще заинтересованы в коде, сделайте это самостоятельно (только с поддержкой языка C и стандартной библиотеки C), возможно, я могу дать вам кое-что.

Прежде всего, немного теории. В базовой числовой теории (модульный арифметический уровень) есть алгоритм, который вдохновляет меня прийти к одному решению; Умножение и Power алгоритм для решения ^ 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 - это константа ключа для 32-разрядного целого без знака и длинного длинного целого без знака из 64 бит.

Код состоит из двух частей: Умножение (легко) и Мощность на 2 (сложнее). Умножение - это просто умножение, масштабирование и распространение целочисленного переполнения. Принцип ассоциативного свойства в математике требует в точности обратного принципа, поэтому, если k (A + B + C), мы хотим kA + kB + kC, где число будет k * A * 10 ^ 18 + k * B * 10. ^ 9 + к С. Очевидно, что операция k C может генерировать число больше 999 999 999, но никогда не больше 0xFF 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-битное арифметическое смещение, достаточно чтобы гарантировать правильные значения).

Power более сложный, но по сути, та же проблема (умножение и сложение), поэтому я дам несколько хитростей по поводу мощности кода:

Типы данных важны, очень важны
Если вы попытаетесь умножить целое число без знака на целое число без знака, вы получите еще одно целое число без знака. Используйте явное приведение, чтобы получить 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

Бык, который вычисляет i ^ i, куда я перехожу к i = 1 ... 1024:

real    0m40.716s
user    0m14.952s
sys    0m0.067s

Для чисел, таких как 65355 ^ 65355, потраченное время безумно.

PD2: Мой ответ слишком поздний, но я надеюсь, что мой код будет полезным.

PD3: Извините, объясните мне по-английски, это один из моих худших недостатков!

Последнее обновление: Мне только что пришла в голову мысль, что с помощью того же алгоритма, но с другой реализацией, улучшается отклик и уменьшается объем используемой памяти (мы можем использовать полностью биты без знака int). Секрет: n ^ 2 = n * n = n * (n - 1 + 1) = n * (n - 1) + n. (Я не буду делать этот новый код, но если кому-то интересно, может быть после экзаменов ...)

Adam Rosenfield · Answer 2 · 11 мая 2009

Нет простого способа сделать это, используя только стандартную библиотеку 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

Jonny Dee · Answer 3 · 28 мая 2011

Я не знаю, нужно ли вам еще решение, но я написал статью об этой проблеме. Он показывает очень простой алгоритм, который можно использовать для преобразования произвольного длинного числа с основанием X в соответствующее число основания Y. Алгоритм написан на языке Python, но на самом деле он занимает всего несколько строк и не использует Python. магия. Мне также требовался такой алгоритм для реализации на Си, но я решил описать его с помощью Python по двум причинам. Во-первых, Python хорошо читается любым, кто разбирается в алгоритмах, написанных на псевдопрограммном языке, и, во-вторых, мне не разрешается публиковать C-версию, потому что я сделал это для своей компании. Просто посмотрите, и вы увидите, как легко эта проблема может быть решена в целом. Реализация в C должна быть прямой ...

Chris Lutz · Answer 4 · 11 мая 2009

Вот функция, которая делает то, что вы хотите:

#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;
}

Просто вещи для рассмотрения.

Mark Ransom · Answer 5 · 08 июня 2009

Возможно, будет слишком поздно или слишком неуместно сделать это предположение, но не могли бы вы сохранить каждый байт в виде двух десятичных цифр (или одной базовой 100) вместо одной базовой 256? Если вы еще не реализовали деление, то это означает, что у вас есть только сложение, вычитание и, возможно, умножение; это не должно быть слишком сложно конвертировать. Как только вы это сделаете, распечатать это будет тривиально.

Распечатать большой массив 256 в базе 10 в с

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

Ответы [ 5 ]

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Распечатать большой массив 256 в базе 10 в с

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

Ответы [ 5 ]

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Похожие темы