ソフトウェア開発 C言語

多倍長演算により階乗の0!から100!まで計算する

戻る


多倍長演算により階乗の0!から100!まで計算するコードは、以下の通り。

/* bigfact.c - 多倍長演算により0!から100!まで計算する */
#include <stdlib.h>
#include <stdio.h>
#include <memory.h>

/* 多倍長演算用の構造体 BIGNUM */
typedef struct tagBIGNUM
{
    int size;
    char *digits;
} BIGNUM;
 
/* BIGNUMに符号なし32-bit/64-bit整数を代入 */
BIGNUM BIGNUM_ui(unsigned int ui)
{
    BIGNUM bn;
    int i;
    unsigned int n, carry;
 
    /* 符号なし64-bit整数は最大で20桁 */
    bn.size = 20;
    bn.digits = (char *)malloc(bn.size);
    memset(bn.digits, 0, bn.size);
 
    carry = ui;
    for(i = 0; carry; i++)
    {
        n = carry;
        bn.digits[i] = n % 10;
        carry = n / 10;
    }
    bn.size = i;
    return bn;
}
 
/* BIGNUMを解放 */
void BIGNUM_delete(BIGNUM bn)
{
    if (bn.digits != NULL)
        free(bn.digits);
}
 
/* BIGNUMに符号なし32-bit/64-bit整数を掛け算する */
BIGNUM BIGNUM_mul_ui(BIGNUM bn1, unsigned int ui)
{
    BIGNUM bn;
    int i;
    unsigned int n, carry;
 
    bn.size = bn1.size + 21;
    bn.digits = (char *)malloc(bn.size);
    memset(bn.digits, 0, bn.size);
 
    carry = 0;
    for(i = 0; i < bn1.size || carry; i++)
    {
        n = carry;
        if (i < bn1.size) n += bn1.digits[i] * ui;
        bn.digits[i] = n % 10;
        carry = n / 10;
    }
    bn.size = i;
    return bn;
}
 
/* BIGNUMを表示する */
void BIGNUM_print(BIGNUM bn1)
{
    int i;
    for(i = bn1.size - 1; i >= 0 && bn1.digits[i] == 0; i--) ;
    if (i < 0) putchar('0');
    else for( ; i >= 0; i--) putchar(bn1.digits[i] + '0');
}
 
/* 階乗を計算する */
BIGNUM BIGNUM_fact(unsigned int n)
{
    BIGNUM bn, bn1;
    unsigned int i;
 
    bn = BIGNUM_ui(1);
    for(i = 1; i <= n; i++)
    {
        bn1 = BIGNUM_mul_ui(bn, i);
        BIGNUM_delete(bn);
        bn = bn1;
    }
    return bn;
}
 
int main(void)
{
    unsigned int k;
    BIGNUM bn;
    for(k = 0; k <= 100; k++)
    {
        bn = BIGNUM_fact(k);
        printf("%u! = ", k);
        BIGNUM_print(bn);
        putchar('\n');
        BIGNUM_delete(bn);
    }
    return 0;
}

ソース: bigfact.zip


国内格安航空券サイトe航空券.com

戻る

©片山博文MZ
katayama.hirofumi.mz@gmail.com

inserted by FC2 system