C言語関係掲示板

過去ログ

No.1006 20!を表現できるビット数

[戻る] [ホームページ]
No.969

階乗について
投稿者---seven(2004/01/12 06:22:55)


1〜20の数値を入力してその階乗した値を出力させたいのですが、
うまくいかないのでどなたかご教授よろしくお願いします。

#include<stdio.h>

int main(void)
{
    int cnt,num,ans;

    while(1)
    {
        printf("\n数値入力 : ");
        scanf("%d",&num);

        if(num >= 2 && num <= 20)
        {
            break;
        }
        printf("\n 2〜20を入力してください\n");
    }
    for(ans = 0,cnt = num-1; cnt >= 2;cnt--)
    {
        ans *= cnt;
    }
    printf("\n階乗結果は%sです\n",ans);
    return 0;
}


No.970

Re:階乗について
投稿者---たか(2004/01/12 11:54:17)


>1〜20の数値を入力してその階乗した値を出力させたいのですが、
>うまくいかないのでどなたかご教授よろしくお願いします。

0掛ける整数は、0ですね。ans = 1 からスタートしてみては?

for(ans = 0,cnt = num-1; cnt >= 2;cnt--)
{
ans *= cnt;
}


No.971

Re:階乗について
投稿者---RAPT(2004/01/12 22:33:23)


ソース修正点が、3箇所ほど。

> for(ans = 0,cnt = num-1; cnt >= 2;cnt--)
for(ans = 1,cnt = num; cnt >= 2;cnt--)

> printf("\n階乗結果は%sです\n",ans);
printf("\n階乗結果は%dです\n",ans);


そもそも、20!はint型では表現できない値では?
私の環境では、16!までは正常に処理できましたが、
17!ではオーバーフローしました。

Windows2000sp4/VC++6.0sp5


No.972

Re:階乗について
投稿者---RAPT(2004/01/12 23:37:05)


追記。20!を表現するには、32bitでも表現できず、64bit必要となります。

No.973

たかさん、RAPTさん返信ありがとうございました。
投稿者---seven(2004/01/13 00:25:39)


無事、解決しました。
丁寧な説明ありがとうございました。

No.974

Re:階乗について
投稿者---かずま(2004/01/13 01:00:00)


> そもそも、20!はint型では表現できない値では?
> 私の環境では、16!までは正常に処理できましたが、
> 17!ではオーバーフローしました。

符号を除くと 31ビットしか精度がない int では、12 ! までしか表現できません。


> 追記。20!を表現するには、32bitでも表現できず、64bit必要となります。

20 ! を表現するには、62ビット必要ですが、
20 ! は 220 を因数に持っているので、精度が 53ビットの double でも表現できます。
#include <stdio.h>
#include <math.h>

int main(void)
{
    int i = 0, a = 1;  double b = 1;

    while (i <= 23) {
        printf("%2d! = %11d  %.30g  %.1f\n", i, a, b, log(b)/log(2));
        i++; a *= i; b *= i;
    }
    return 0;
}


No.975

Re:階乗について
投稿者---たいちう(2004/01/13 10:45:38)


処理系に依存しているのかもしれませんが、
かずまさんのプログラムを実行したところ、
このような結果が得られました。
(WindowsXP-Pro + VC6.0 SP5)

22! =  11 2400 0727 7776 0770 0000 (doubleで計算) 
23! = 258 5201 6738 8849 7800 0000 (doubleで計算)

Excelでちまちま計算してみると、
(「=MOD(B1*$A2+INT(C1*$A2/10000),10000)」こんな感じで。)
                         
22! =  11 2400 0727 7776 0768 0000 (Excelで計算)
23! = 258 5201 6738 8849 7664 0000 (Excelで計算)

となりました。

静的な精度が十分でも演算の精度が十分ではない例だと思います。



No.976

Re:階乗について
投稿者---かずま(2004/01/13 11:28:59)


> 静的な精度が十分でも演算の精度が十分ではない例だと思います。

この例からいきなり演算の精度に結論付けることは無理があります。

22 ! は 70ビット、23 ! は 75ビットで表現できますが、ともに 219 の倍数ですから、
下位19ビットはゼロです。したがって、上位の有効桁数は 51ビット、56ビットとなります。
このため、22 ! は double で正しい値を持てますが、23 ! は double では正しい値を
表現できません。

では、22 ! が printf で正確に表示できないのはなぜかという問題ですが、
内部表現が正しい値を保持しているといっても、53ビットの精度の末尾 2ビット
にゼロを持つだけで、残りの 17個のゼロは持っていません。

処理系が備えている浮動小数点数10進変換は、double の仮数の右側の存在しない
部分をゼロだとは解釈せずに、何があるかわからないものを表示しても意味がない
とし、10進17桁あるいは18桁で表示を打ち切るようになっています。

もしろん、これは処理系依存で、確か、Solaris の C コンパイラの printf は、
存在しない部分をゼロと解釈し、10進50桁かそれ以上を表示していたと思います。
今はどうか知りませんが。


訂正:
20 ! は 220を因数に持っていると発言しましたが、218 の間違いでした。

No.977

Re:階乗について
投稿者---かずま(2004/01/13 13:48:49)


> 処理系が備えている浮動小数点数10進変換は、double の仮数の右側の存在しない
> 部分をゼロだとは解釈せずに、何があるかわからないものを表示しても意味がない
> とし、10進17桁あるいは18桁で表示を打ち切るようになっています。

VC++ は 17桁、BCC は 19桁のようです。gcc はないものはゼロだとするようです。
int main(void)
{
    double a = 1;  int i;
    for (i = 1; i <= 100; i++) printf("%3d: %33.1f\n", i, a *= 2);
    return 0;
}


No.979

Re:階乗について
投稿者---たいちう(2004/01/13 14:38:32)


> > 静的な精度が十分でも演算の精度が十分ではない例だと思います。
> 
> この例からいきなり演算の精度に結論付けることは無理があります。

printfの精度が問題だったわけですね。

22! の内部表示
01000100 01001110 01110111 01010010 01100001 01011001 11110000 01101100
は、誤差なく 11 2400 0727 7776 0768 0000 を表していることも確認できました。
(今度も「=MOD(H49*2+INT(I49*2/10000),10000)」こんな感じで。)

納得しました。解説ありがとうございました。