25

私は100を計算しようとしています！(つまり、100 の階乗)。

Cを使用してこれを達成する最も簡単な方法を探しています。読み回しましたが、具体的な答えは見つかりませんでした。

ご存知のとおり、私は Mac os X の Xcode でプログラミングしています。

4

4 に答える 4

29

単純なライブラリを探しているなら、libtomath (libtomcrypt から) がおそらく必要なものです。

自分で単純な実装を作成しようとしている場合 (学習演習として、または bigint 機能の非常に限られたサブセットのみが必要であり、大規模なライブラリへの依存関係や名前空間の汚染などに取り組みたくない場合)。 、それから私はあなたの問題に対して次のことを提案するかもしれません:

に基づいて結果のサイズを制限できるため、結果を保持するために必要なサイズの のn配列を事前に割り当てるだけです。結果を出力uint32_tしたいと思うので、2 のべき乗ではなく、10 のべき乗 (つまり、1000000000 の底) を使用するのが理にかなっています。つまり、配列の各要素は許可されています。 0 から 999999999 までの値を保持します。

この数値に (通常の、大きくnない) 整数を掛けるには、次のようにします。

uint32_t carry=0;
for(i=0; i<len; i++) {
    uint64_t tmp = n*(uint64_t)big[i] + carry;
    big[i] = tmp % 1000000000;
    carry = tmp / 1000000000;
}
if (carry) big[len++] = carry;

100 (またはその他の小さな数) よりも大きくならないことがわかっnていて、64 ビットの範囲に入ることを避けたい場合 (または 64 ビット プラットフォームを使用uint64_tしていて、bigint 配列に使用したい場合)、乗算結果が常に型に収まるように、基数を 10 の累乗にします。

ここで、結果を印刷すると次のようになります。

printf("%lu", (long)big[len-1]);
for(i=len-1; i; i--) printf("%.9lu", (long)big[i-1]);
putchar('\n');

10 のべき乗ではなく、2 のべき乗を基数として使用する場合、乗算ははるかに高速になります。

uint32_t carry=0;
for(i=0; i<len; i++) {
    uint64_t tmp = n*(uint64_t)big[i] + carry;
    big[i] = tmp;
    carry = tmp >> 32;
}
if (carry) big[len++] = carry;

ただし、結果を 10 進数で出力するのはあまり快適ではありません... :-) もちろん、結果を 16 進数で表示したい場合は簡単です。

printf("%lx", (long)big[len-1]);
for(i=len-1; i; i--) printf("%.8lx", (long)big[i-1]);
putchar('\n');

お役に立てれば！他のこと (加算、2 つの bigint の乗算など) の実装は、演習として残します。小学校で 10 進数の加算、乗算、除算などをどのように学んだかを思い出して、コンピューターにその方法を教えてください (ただし、代わりに 10 進数の 9 進数または 2 進数の 32 進数で)。問題ありません。

于 2010-07-27T07:05:43.343 に答える
9

ライブラリの実装を使用する場合、標準のものはGMPのようです

mpz_t out;
mpz_init(out);
mpz_fac_ui(out,100);
mpz_out_str(stdout,10,out);

100 を計算する必要があります。ドキュメントを見ることから。

于 2010-07-27T03:44:23.737 に答える
2

あなたはこれを行う最も簡単な方法を求めました。それで、ここに行きます：

#include <gmp.h>
#include <stdio.h>

int main(int argc, char** argv) {
    mpz_t mynum;
    mpz_init(mynum);
    mpz_add_ui(mynum, 100);
    int i;
    for (i = 99; i > 1; i--) {
        mpz_mul_si(mynum, mynum, (long)i);
    }
    mpz_out_str(stdout, 10, mynum);
    return 0;
}

このコードをテストしたところ、正しい答えが得られました。

于 2010-07-27T03:44:58.637 に答える
2

OpenSSL bnも使用できます。Mac OS X にはすでにインストールされています。

于 2010-07-27T03:50:59.477 に答える