C:大きな数の計算方法,オーバーフロー回避

Question

C言語で3^80の計算をしたいのですが、数が大きすぎてオーバーフローしてしまいます。各桁ごとに配列を置けばいいのかとも思いましたが、いまいちよくわかりません。
解決方法が分かる方いらっしゃいましたらよろしくお願いします。

Answer 1

多倍長整数演算のライブラリを使うのも一つの手段です。
たとえば、多倍長整数演算ライブラリ (GNU MP)などを参考にしてください。

「多倍長演算 Cライブラリ」でググればいくつか出てくると思います。

Answer 2

GCCであれば拡張で__int128を使えます。3^80 < 2^127-1なのでそのまま計算できます。ただし、__int128はprintfでそのまま表示できないため、表示が必要な場合はそこも作り込む必要があります。

#include <stdio.h>
#include <stdbool.h>

#define INT10_19 10000000000000000000ULL

static inline void print_int128_in(__int128 n) {
        __int128 d = n / INT10_19;
        unsigned long long m = (unsigned long long)(n % INT10_19);
        if (d != 0) {
                print_int128_in(d);
                printf("%019llu", m);
        } else {
                printf("%llu", m);
        }
}

static inline void print_int128(__int128 n)
{
        if (n == 0) {
                printf("%d", 0);
                return;
        } else if (n < 0) {
                printf("-");
                n *= -1;
        }
        print_int128_in(n);
}


int main(void)
{
        __int128 x = 1;
        __int128 b = 3;
        int e = 80;
        while (true) {
                if (e % 2) {
                        x *= b;
                }
                e /= 2;
                if (e == 0) {
                        break;
                }
                b *= b;
        }
        print_int128(x);
        printf("\n");
}

コンパイル時はgcc -std=gnu11等とGNU拡張を有効にしてください。冪乗計算は2乗したものを掛けていくという方法である程度高速化しています。なお、x86_64のCPUでは、128bit整数なんてものを扱える命令は存在しないため、__int128をhighとlowにそれぞれわけて計算しており、通常の整数値演算よりも遅いです。

Answer 3

log(3^80)/log(256)≒15.85なので、16バイトあれば十分に表現できることがわかります。
乗数（この場合は3）と限られた小さな値の場合、乗算は比較的簡単にできます。

確認のため、3^1, 3^2…と順に十進化および表示をしていますが、3^80だけ十進化および表示をすれば、速くなりますね。

1桁をunsigned charとしましたが、unsigned shortやunsigned longにすれば、さらに高速化が計れます。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


#define TRUE  (0 == 0)
#define FALSE (0 != 0)
#define FIGURES 16
#define DECIMAL_FIGURES (1 + (int)(8 * FIGURES * 0.30102999566398119521373889472449))


/*
 * 掛け算をする
 * 戻り値:繰上げ
 * product:積 (要素FIGURESの配列)
 * multiplicand:被乗数 (要素FIGURESの配列)
 * multiplier:乗数
 */
unsigned char multiply(unsigned char *product, unsigned char *multiplicand, unsigned char multiplier)
{
	int i;
	unsigned char carry = 0;

	for (i = 0; i < FIGURES; i++) {
		unsigned short sh_product = (unsigned short)multiplicand[i] * (unsigned short)multiplier + carry;
		product[i] = (unsigned char)sh_product;
		carry = (unsigned char)(sh_product >> 8);
	}

	return carry;
}


/*
 * 割り算をする
 * 戻り値:余り
 * quotient:商 (要素FIGURESの配列)
 * dividend:被除数 (要素FIGURESの配列)
 * divisor:除数
 */
unsigned char divide(unsigned char *quotient, unsigned char *dividend, unsigned char divisor)
{
	int i;
	unsigned short remainder = 0;

	for (i = FIGURES - 1; i >= 0; i--) {
		unsigned short sh_dividend = (remainder << 8) + (unsigned short)dividend[i];
		quotient[i] = (unsigned char)(sh_dividend / divisor);
		remainder = sh_dividend % divisor;
	}

	return (unsigned char)remainder;
}


/*
 * 数が0か否かを判定する
 * 戻り値:TRUE:0／FALSE:0以外
 * digit:数 (要素FIGURESの配列)
 */
int is_zero(unsigned char *digit)
{
	int i;

	for (i = 0; i < FIGURES; i++) {
		if (digit[i] != 0) {
			return FALSE;
		}
	}

	return TRUE;
}


/*
 * 数を十進法文字列に変換する
 * 戻り値:decimal_stringと同じ
 * decimal_string:十分な領域がある文字列バッファ
 * digit:数 (要素FIGURESの配列)
 */
char *to_decimal(char *decimal_string, unsigned char *digit)
{
	unsigned char dividend[FIGURES];
	unsigned char remainder;
	char decimal[2];
	int length = 0;

	memcpy(dividend, digit, FIGURES);
	decimal_string[0] = '\0';

	do {
		remainder = divide(dividend, dividend, 10);
		sprintf(decimal, "%u", remainder);

		/* 1文字をdecimal_stringの左に追加する */
		memmove(& decimal_string[1], & decimal_string[0], ++length);
		decimal_string[0] = decimal[0];
	} while (! is_zero(dividend));

	return decimal_string;
}


int main(void) 
{
	int exponential;
	unsigned char product[FIGURES] = { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; /* = 1 */
	char decimal_string[DECIMAL_FIGURES + 1];
	
	for (exponential = 1; exponential <= 80; exponential++) {
		printf("3^%2d = ", exponential);
		if (multiply(product, product, 3) > 0) {
			printf("overflow!\n");
			return 1;
		}
		printf("%s\n", to_decimal(decimal_string, product));
	}
	
	return 0;
}

Answer 4

計算結果を文字列に直すんだろうと思いますが、定数ならあらかじめ計算してデータとして持っておけばいいと思います。

Answer 5

計算結果をどのように利用するかにもよりますが、
そんなサンプルプログラムはたくさんネットで出ています。

【参考URL】
http://7ujm.net/play/dcalc.html

Answer 6

違う観点から回答します。

UNIX/Linux系の環境であれば、
「bc」コマンドを呼び出す手もあります。