C言語関係掲示板

過去ログ

No７２１　10000!（1万の階乗）を求めるプログラム

[戻る]　[ホームページ]
No.8760
!10000（1万の階乗）を求めるプログラム
投稿者---Kazu(2003/08/01 23:50:33)


!10000を求めるプログラムを考えてみたのですが、
行き詰まりいろいろ調べた結果以下のソースコードを見つけました。
ちなみにもともとのコードでは

#define MAX 500

程度になっていたので!10000が計算できるよう現在のように変更しました。
このコードを実行すると結果的にはおそらく正確な値が計算されていると思うのですが、
アルゴリズムが私にとっては複雑でなぜこの方法で階乗が計算できるのか
理解できません。(特に18行目〜30行目)
よろしかったらどなたか教えていただけないでしょうか？


#include <stdio.h>
#define RADIX 10
#define MAX 40000

int f[MAX], carry, tmp;
int n = -1, keta, i, j;

int main(void) {
  for(i = 0; i < MAX; i++) f[i] = 0;
  f[0] = 1;
  while(1) {
    printf("n = ");
    scanf("%d", &n);
    if(n >= 0) break;
    printf("ERR: n must be zero or positive.");
  }

  for(j = n; j >= 1; j--) {
    for(i = 0; i < MAX; i++) f[i] = f[i] * j;
    carry = 0;
    for(i = 0; i < MAX; i++) {
      tmp = f[i] + carry;
      f[i] = tmp % RADIX;
      carry = tmp / RADIX;
    }
    if(carry > 0) {
      printf("overflow\n");
      return(-1);
    }
  }

  for(i = MAX - 1; i >= 0; i--) {
    if(f[i] != 0) {
      keta = i + 1;
      break;
    }
  }

  for(i = keta - 1, j = 1; i >= 0; i--, j++) {
    if((j % 70) == 0) printf("\n");
    printf("%d", f[i]);
  }
  return(0);
}

No.8761
Re:!10000（1万の階乗）を求めるプログラム
投稿者---水也(2003/08/02 10:04:28)


このプログラムは、階乗を求める際のかけ算を筆算の要領でやっていますね。
例えば33×25なら、
    33
x   75
------
   165   ---> tmp = 165になり、tmp % RADIX が 5, tmp / RADIX が16
+ 231    ---> tmp = 247になり、tmp % RADIX が 7, tmp / RADIX が24
         ---> tmp = 24になり、 tmp % RADIX が 4, tmp / RADIX が2
         ---> tmp = 2になり、  tmp % RADIX が 2, tmp / RADIX が0
------                                       ↑
  2475                                     乗算結果

となるように、乗数を１桁ずつ被乗数にかけ、１桁ずつ横にずらして足して
いく考え方と同じです。その際足し算した時に桁上げが起こることがありま
すが、変数carryはその桁上げに相当します。

このプログラムでは19行目〜29行目で階乗計算におけるひとつのかけ算が行
われ、それをn〜1まで繰り返しています。
（26行目からは計算結果が配列の要素数を超える桁になったときのオーバー
フローの検知）

文章で詳しく説明するのは難しいんですが、考え方を頭に入れた上で配列を
ざっと書き並べてみて、実際の実行の流れを追ってみれば、たぶん理解でき
ると思います。
No.8762
Re:!10000（1万の階乗）を求めるプログラム
投稿者---あかま(2003/08/02 11:10:16)


"多倍長"というやつです。詳しく知りたければ詳しいサイトを検索してみてください。
このプログラムで、できるだけ処理を早くしたいときは、
#define RADIX 10
#define MAX 40000
RADIXを10倍単位で大きくして、MAXをできるだけ小さくすることですね。

で、少し速く処理ができるようにしてみました。10000以上の入力は計算できませんが。

#include <stdio.h>
#define RADIX 10000

#define MAX 10000

int f[MAX], carry;
int n = -1, keta=0, i, j;
long tmp;

int main(void) {
  for(i = 0; i < MAX; i++) f[i] = 0;
  f[0] = 1;
  while(1) {
    printf("n = ");
    scanf("%d", &n);
    if(n >= 0) break;
    printf("ERR: n must be zero or positive.");
  }

  for(j = 2; j <= n; j++) {
  	carry = 0;
    for(i = 0; i <= keta; i++){
      tmp =  f[i] * j + carry;
      f[i] = tmp % RADIX ;
      carry = tmp / RADIX;
    }
	if(carry) f[++keta] = carry;
    if(keta >= MAX) {
      printf("overflow\n");
      return(-1);
    }
  }
  printf("%d",f[keta]);
  for(i = keta-1; i >= 0; i--) {
    printf("%04d", f[i]);
  }
  return(0);
}

No.8763
Re:!10000（1万の階乗）を求めるプログラム
投稿者---Kazu(2003/08/02 23:02:10)


ありがとうございます。

多倍長って言うんですね、これ。しっかり勉強します。
しかも動作の速度のことまで考えていただいて、ほんとありがとうございました。