c に unsigned char の配列があり、基数 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 バイトの整数型はありません。そのため、最初から unsigned char 配列に数値を格納しています。
この数値を基数 10 で効率的に出力するにはどうすればよいですか?
私は少し迷っています。
この質問を見たとき、私はそれを解決するつもりでしたが、その瞬間はとても忙しかったです. この先週末は、何時間かの自由時間を得ることができたので、保留中の課題を検討しました。
まず、上記の対応を検討することをお勧めします。私は 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 + k C. 明らかに、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 k B の後、C の最後の乗算 ( B = k B + (C / モジュール) ) から 0x FF FE を追加する必要があります (正しい値を保証するのに十分な 18 ビットの算術オフセットがあります)。
電力はより複雑ですが、本質的に同じ問題 (乗算と加算) であるため、コードの電力についていくつかのトリックを示します。
大きな数を追加する別の方法を開発しました。これらの最後のものはあまり証明されていませんが、うまく機能すると思います。バグがあっても、私と一緒に残酷にならないでください。
...それだけです！
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 = 1 ... 1024 に移動する i^i を計算する bucle:
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を使用して説明することにしました。まず、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;
}
考慮すべきことだけです。
この提案を行うには遅すぎるか、無関係すぎるかもしれませんが、各バイトを 1 つの基数 256 ではなく、基数 10 の 2 つの数字 (または基数 100 の 1 つ) として格納できますか? 除算をまだ実装していない場合は、足し算、引き算、そしておそらく掛け算しかないことを意味します。それらを変換するのはそれほど難しくありません。それができたら、それを印刷するのは簡単です。