Cで基数10の大きな基数256配列を印刷します

標準 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 ライブラリをサポートしている場合のみ)。何か差し上げます。

その前に、少し理論を。基本的な数値理論 (モジュラー算術レベル) には、1 つの解にたどり着くように促すアルゴリズムがあります。 乗算とパワー a^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 は 2 進数表現の N から 1 を引いた桁数であり、n_i は i 2 進数です。例 (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

結果を確認するには、直接出力 as を使用し、bc に入力します。簡単なシェル スクリプト:

#!/bin/bash


select S in ` awk -F '==' '{print $1 " == " $2 }' | bc`;
do
    0;
done;

echo "Test Finished!";

unsigned int (4 バイト) の配列があり、配列の各 int に 9 桁の数字 ( % 1000000000UL ) を格納します。したがって、num[0] は最初の 9 桁、num[1] は 10 から 18 の数字、num[2] です...私は従来のメモリを使用して動作しますが、改善により動的メモリでそれを行うことができます。わかりましたが、配列の長さはどのくらいですか? (または、割り当てる必要があるメモリの数は?)。 bc 計算機 (mathlib を使用した bc -l) を使用して、数字が何桁であるかを判断できます。

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 定数で何が起こるかを試してください)。より多くのメモリを確保し、より多くのステップを実行する必要があります。 10^9 は、32 ビットの unsigned int と 64 ビットの unsigned long long int のキー定数です。

このコードには、乗算 (簡単) と 2 乗 (より難しい) の 2 つの部分があります。乗算は単なる乗算とスケーリングであり、整数オーバーフローを伝播します。逆原理を正確に行うには、数学の連想特性の原理が必要です。したがって、k(A + B + C) の場合、kA + kB + kC が必要です。ここで、数値は k*A*10^18 + k*B*10 になります。 ^9 + kC。明らかに、k C 演算は 999 999 999 より大きい数を生成できますが、0xFF FF FF FF FF FF FF FF より大きいことはありません。 C は 32 ビットの符号なし整数であり、k は 16 ビットの符号なし short であるため、乗算では 64 ビットを超える数値は発生しません。麦汁の場合、次の番号になります:

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 kB の後に、C の最後の乗算から 0x FF FE を追加する必要があります ( B =k B + (C / モジュール) ) など (正しい値を保証するのに十分な 18 ビットの算術オフセットがあります)。

累乗はより複雑ですが、本質的には同じ問題 (乗算と加算) であるため、コードの累乗についていくつかのトリックを示します。

  • データ型は重要、非常に重要
  • 符号なし整数を符号なし整数で乗算しようとすると、別の符号なし整数が得られます。明示的なキャストを使用して unsigned long long int を取得し、データを失わないようにします。
  • 常に unsigned 修飾子を使用してください。忘れないでください!
  • 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 を計算する bucle 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。 ...)


まだ解決策が必要かどうかはわかりませんが、この問題について記事を書きました。これは、基数 X の任意の長い数値を対応する基数 Y に変換するために使用できる非常に単純なアルゴリズムを示しています。アルゴリズムは Python で記述されていますが、実際には数行の長さであり、Python を使用していません。マジック。 C 実装にもそのようなアルゴリズムが必要でしたが、2 つの理由から Python を使用して記述することにしました。 1 つ目は、疑似プログラミング言語で書かれたアルゴリズムを理解している人なら誰でも Python を非常に読みやすいことです。2 つ目は、C バージョンを投稿することは許可されていません。一見すると、この問題が一般的にいかに簡単に解決できるかがわかります。 C での実装は簡単なはずです...