Распечатайте большую основу 256 массивов в основе 10 в 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 с основанием? Если вы еще не реализовали деление, это означает, что все, что у вас есть, - это сложение, вычитание и, возможно, умножение; их не должно быть слишком сложно преобразовать. После того, как вы это сделаете, распечатать его будет тривиально.

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

Прежде всего, я предлагаю вам рассмотреть вышеупомянутый ответ. Я никогда не использую библиотеку 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] ...

#!/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] ...

#!/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-битных беззнаковых int и 64-битных unsigned long long int

. Код состоит из двух частей: Умножение (легко) и Степень на 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-битное арифметическое смещение, достаточно чтобы гарантировать правильные значения).

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

• Типы данных важны, очень важны
• Если вы попытаетесь умножить беззнаковое целое с беззнаковым целым, вы получите еще одно беззнаковое целое. Используйте явное приведение, чтобы получить unsigned long long int и не потерять данные.
• Всегда используйте беззнаковый модификатор, не забывайте его!
• Power by 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 переходит в i = 1 ... 1024:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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