最大79桁の数字の扱い方

Question

問題

正整数 n ( 0 < n < 80 ) に対して, n桁以内の最大の３のベキ乗数を左詰めで書き出すプログラムを作れ。

【入力】
正整数 n ( 0 < n < 80 ) １つ。

【出力】
１行として書き出す（末尾に改行を書き出すこと）。

【例】
入力１
1
出力１
9

入力２
6
出力２
531441

質問内容

下記のように計算したら実行時間がオーバーしてしまいました。

コード

#include<stdio.h>
int main(void){
	int n;
	scanf("%d",&n);
	int order[80]={9};
	int flag[80]={0};
	int i;
	while(order[n]==0&&order[n+1]==0){
		for(i=0;i<n;i++){
			order[i]*=3;
			order[i]+=flag[i];
			flag[i]=0;
			if(order[i]>9){
				flag[i+1]+=order[i]/10;
				order[i]%10;
			}
		}
		i++;
	}

	for(i=n-1;i>=0;i--){
		printf("%d",order[i]);
	}
	printf("\n");
	return 0;

}

Answer 1

定義

正の実数 a, b, c において、a の b 乗が c である時、a を底、b を指数、c を冪と呼ぶことにします。この時、架空の関数 p は p(a, b) において c を返すものとします。さらに架空の関数 l は、l(a, c) において b を返します。この時、a を底、c を真数、b を対数と呼びます。

3 の累乗である n 桁の最大値を求める

3 の累乗である n 桁の最大値 x は 3 を底とする冪なので、p(3, t) で表すことができます。また、これを 10 を底とする冪と考えると、p(10, d) で表すこともできます。x = p(3, t) = p(10, d) です。

なぜ 10 を底とする冪を考えるかというと、これで 10 進数における桁数が求められるからです。例えば 1 は p(10, 0) であり、10 は p(10, 1) であり、100 は p(10, 2) です。よって、冪が一桁である時、指数は 0 以上 1 未満となり、二桁である時、1 以上 2 未満、三桁である時、2 以上 3 未満となります。たとえば二桁の数 50 が冪の時、指数は約 1.69897000433602 となり、p(10, 1.69897000433602) ≒ 50, l(10, 50) ≒ 1.69897000433602 となります。

話を戻して x = p(3, t) = p(10, d) ですが、ここで 10 = p(3, l(3, 10)) なので、これを代入すると x = p(3, t) = p(p(3, l(3, 10)), d) となります。

冪乗の指数法則より、p(3, t) = p(3, l(3, 10) * d) が成り立つため、t = l(3, 10) * d となります。ここで l(3, 10) は定数約 2.09590327428938 であり、d = t / l(3, 10) が成り立ちます。ここで d に n を代入することにより、t = n * 2.09590327428938 で求めることができます。

結論として、実数 a の小数点以下を切り捨てる架空の関数 int を考えた時、求める数は p(3, int(n * 2.09590327428938)) です。

n = 79 の時の 3 の累乗の最大値

p(3, int(79 × 2.09590327428938)) = p(3, 165) = 5308930362839928667688049530226627139643793175493798707037516219525092562313843

が答えになります。

時間短縮

多倍長演算を用いて 3 を 165 回乗算すれば解は求まるわけですが、これを更に短縮しましょう。例えば p(3, 4) は真正直に 3 を 4 回乗算しなくても、p(p(3, 2), 2) で求められます。指数法則をうまく使って答えを導き出してください。

指数法則 - Wikipedia

追記

多倍長演算の乗算は必要ないかもしれません。3 は 2 進数で 11 なので、何かに 3 をかけるということは、その数を左に 1 ビットシフトしたものとその数自身を足したものに等しくなります。ビットシフトと加算を 165 回繰り返すだけなので、十分高速に結果が求まると思います。また、3 にビットシフトを 164 回繰り返すと 166 ビットなので、そこに加算した繰上りを入れても 167 ビットつまり 21 バイトに収まります。バッファは計算しながら動的に確保しなくても、21 バイト固定で間に合うはずです。後の問題はそれを 10 進数に直す際の除算ですね。しかしここまで十分高速に計算できているので、間に合いそうな気がします。

Comments

[退会済みユーザー]

どうも数学やアルゴリズム系弱いので、こういうの頭の中でパパっと出てこないですね…興味深いです

[Zuishin]

途中自分で作った関数の引数の順番がわからなくなって間違えていました。
5308930362839928667688049530226627139643793175493798707037516219525092562313843 は 3 の冪乗数だしこれに 3 をかけると 80 桁になるので合っているんじゃないかなとは思いますが。n = 1, 2, 3, 4, 5 の時も合っているようです。後は確かめていません。

[grape_ll]

数学的にみればこのようなアルゴリズムで解くことが出来るのですね。
参考になります。

Answer 2

正解を書こうと思えば書けますが、なんか学校の課題っぽいので、その実現方法を考えるのがテーマだと思いますよ。
（一般的には、大きい数を扱える多倍長演算ライブラリ等を使いますが）

考え方のヒントとしては、例えば一発で79桁を計算するのは無理でも、
・計算可能な桁数（例えば5桁づつ）ごと配列に分けて計算する
・桁上がりを自力で処理する
・べき乗は単純な掛け算の繰り返しである（ループで処理できる）
というように、細かい要素に分けてやれば可能ですよね。

---

参考例として。
ちなみに、C#で適当に書くとこんなんなります。（速度とか効率はとりあえず置いときます）

int n = 79; //とりあえずnの最大を与える
int powX = 3; 
int powY = 1;
BigInteger val = powX; //出力する数を格納する変数

while (true)
{
    //次のBigIntegerの桁数を計算する
    //Log10(valNext)+1=80(桁数80)に達した時点で、valに79桁の最大の数が格納されている
    var valNext = BigInteger.Pow(powX, powY);
    if (((int)BigInteger.Log10(valNext) + 1) > n)
    {
        break;
    }
    val = valNext;
    powY++; //べき乗する値を加算
}

//コンソールに文字列を出力
Console.WriteLine(val.ToString());

C#なんて判らん！となるでしょうが、これをC言語の機能に置き換えると、
0. 大きい数を扱う構造体（BigIntegerを置き換える）
0. 上記構造体をべき乗（乗算）する関数（BigInteger.Powを置き換える）
0. 上記構造体の桁数を計算する関数（BigInteger.Log10+1を置き換える）
0. 上記構造体を文字列に変換する関数（val.ToString()を置き換える）

を用意すると、同等の機能を実現できます。

typedef struct BigInt
{
    int Values[20];
} BigInt;

int main()
{
    char buf[100];
    int n = 79;
    int powX = 3;
    int powY = 1;
    BigInt val = { powX };

    while (true)
    {
        BigInt valNext = BigPow(powX, powY);
        if (BigIntLength(valNext) > n)
        {
            break;
        }
        val = valNext;
        powY++;
    }

    BigIntToString(buf, val);
    printf("%s\r\n", buf);
    return 0;
}

Comments

[grape_ll]

一つの変数に入らない時点で思考が止まってしまっていたので，考え方のヒントをくださるだけでとても助かります。これらのヒントをもとに考えてみます。

[grape_ll]

5けたずつだと桁数の判定が難しいかと考え，1桁ずつでやってみたのですが実行時間がオーバーしてしまいました。このことを考えるとまとめる桁数を上げた方がいいのだろうという結論に至るのですが、まとめた場合にどう止めればいいのかを教えていただけると助かります。
#include<stdio.h>
int main(void){
int n;
scanf("%d",&n);
int order[80]={9};
int flag[80]={0};
int i;
while(order[n]==0&&order[n+1]==0){
for(i=0;i<n;i++){
order[i]*=3;
order[i]+=flag[i];
flag[i]=0;
if(order[i]>9){
flag[i+1]+=order[i]/10;
order[i]%10;
}
}
i++;
}

for(i=n-1;i>=0;i--){
printf("%d",order[i]);
}
printf("\n");
return 0;

}

[退会済みユーザー]

条件にうまく掛からずに、どこかで無限ループしてるのではないですか。
変数の値が期待通りに変化しているか、デバッガで止めて変数の値を見たり、printf等で変数の値を出力したりして確認しましょう。

[grape_ll]

問題が分かりました。
for文でnを含んでいなかったので無限ループしていたみたいです。
下記のコードで大丈夫でした。
ありがとうございました。
#include<stdio.h>
int main(void){
int n;
scanf("%d",&n);
int order[80]={9};
int flag[80]={0};
int ans[80];
int i,j;
while(order[n]==0&&order[n+1]==0){
for(i=0;i<=n;i++){
ans[i]=order[i];
order[i]*=3;
order[i]+=flag[i];
flag[i]=0;
printf("(%d,%d)\n",order[i],i);
if(order[i]>9){
flag[i+1]+=order[i]/10;
order[i]%=10;
}
}

}

for(i=n-1;i>=0;i--){
printf("%d",ans[i]);
}
printf("\n");
return 0;

}

Answer 3

79桁なので1桁ずつの計算でよいと思います。
（ぱっと見、order[i]%10;の行がおかしいです。）

参考
int型での計算をもとに、多倍長整数(8桁ごと)での計算に書き換えたコードです。
多倍長整数の計算部分を関数化すると、mainはint型での計算と同じように書けます。

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

#define SIZE 10
#define DIG 8
#define NUM 100000000 /* 10^8 */

int my_log10(int* val);
void my_mul(int* val, int n);
void my_print(int* val);

int main(void) {
	int n;
	scanf("%d", &n);
	// 参考：int型での計算
	if (n <= DIG) {
		int result = 1; // 最初の値
		int next = 3; // 次の値
		while ((int)log10(next) < n) { // 次の値がn桁を超えるまで
			result = next; // 次の値を結果に設定
			next *= 3; // 次の値に3をかける
		}
		printf("%d\n", result); // 結果を出力
	}
	// 多倍長整数での計算
	else {
		int result[SIZE] = { 1 }; // int result = 1;
		int next[SIZE] = { 3 }; // int next = 3;
		while (my_log10(next) < n) { // while ((int)log10(next) < n)
			memcpy(result, next, sizeof(result)); // result = next;
			my_mul(next, 3); // next *= 3;
		}
		my_print(result); // printf("%d\n", result);
	}
	return 0;
}

//桁数
int my_log10(int* val) {
	int i;
	for (i = SIZE - 1; val[i] == 0 && i > 0; i--);
	return (int)log10(val[i]) + DIG * i;
}

//かけ算
void my_mul(int* val, int n) {
	int i;
	int tmp = 0;
	for (i = 0; i < SIZE; i++) {
		tmp = val[i] * n + tmp;
		val[i] = tmp % NUM;
		tmp /= NUM;
	}
	return;
}

//出力
void my_print(int* val) {
	int i;
	for (i = SIZE - 1; val[i] == 0 && i > 0; i--);
	printf("%d", val[i]);
	for (i--; i >= 0; i--) {
		printf("%0.*d", DIG, val[i]);
	}
	printf("\n");
	return;
}

Comments

[grape_ll]

コードのご指摘ありがとうございます。%=に直してみました。しかしこれだけではまだループが終わっていないようだったので、他の原因も探してみようと思います。

また，参考のコードもありがとうございます。
ですが、ひとまずは自分のコードを仕上げてみようと思います。

まだほかにも指摘等がありましたらぜひ教えてください。よろしくお願いいたします。

[grape_ll]

for文の条件がだめな原因だったみたいです。
無事解決しました。ありがとうございました。
#include<stdio.h>
int main(void){
int n;
scanf("%d",&n);
int order[80]={9};
int flag[80]={0};
int ans[80];
int i,j;
while(order[n]==0&&order[n+1]==0){
for(i=0;i<=n;i++){
ans[i]=order[i];
order[i]*=3;
order[i]+=flag[i];
flag[i]=0;
printf("(%d,%d)\n",order[i],i);
if(order[i]>9){
flag[i+1]+=order[i]/10;
order[i]%=10;
}
}

}

for(i=n-1;i>=0;i--){
printf("%d",ans[i]);
}
printf("\n");
return 0;

}

Answer 4

たかだか 79 パターンの入力しかない上に、連続した自然数ということは、事前に全てのnに対応する
答えを配列に突っ込んでおけばO(1)で答えを書き出せますね。

・・・これだけだと怒られそうなので、下記の手順を追加提示しておきます。

A.元の数字の文字列sourceの桁数nを数える／例：source="386" → n=3
B.要素数n+1の配列tempを作る／例：temp[4]。temp={0,0,0,0}
C.tempの各桁にsourceの各桁の3倍の数字を入れてまわる／例：temp={0,9(33),24(83),18(6*3)}
D.tempに対して繰り上がり処理を行う
／例：temp={0,9,25(24+1),8} → temp={0,11(9+2),5,8} → temp={1,1,5,8}
E.配列tempから文字列answerに変換／例：answer="1158"（※最上位桁が0なら詰める）

Comments

[grape_ll]

ここでいう最初のもとの数字とはどのことを示していますでしょうか。
そこから先の進行はなんとなくわかるのですが、そこが分からないので最後のanswerが何を表しているのかが予想できていません。4桁ならば1158*3だと思うのですが。
よろしくお願いいたします。

[himazin.blm]

「最初のもとの数字」は「3倍したい数字」です。上の例だと386のことですね。この手順で3の乗数を80桁になるまで全部計算しておいて、答えの配列に突っ込む数をそこから拾えば良い、という話です。

Answer 5

学校の課題か何かだと思うので、敢えて捻くれた回答をします。

この課題文中では、アウトプットフォーマットについて指定がありません。（出力例はあくまでも例です。）また、「n桁」という指定はありますが、これは10進数における桁数とは書かれておりません。これを利用し、「アウトプットフォーマットとして3進数を採用する」という旨を断り書きすれば、簡単に回答できます。

3のベキ乗数は、3進数では100000・・・というキリ番となります。

したがって、3のベキ乗数は桁数毎に一つずつしか存在しません。しかも、それぞれ0の数が違うだけです。

例

入力:5　
出力:10000（3進数として表示）

入力:10
出力:1000000000（3進数として表示）

入力:20
出力:10000000000000000000（3進数として表示）

カンマ区切りにすると読みやすいかもしれません。

Answer 6

himazin.blm さんの目から鱗な発想

たかだか 79 パターンの入力しかない上に、連続した自然数ということは、事前に全てのnに対応する

答えを配列に突っ込んでおけばO(1)で答えを書き出せますね。

を参考に、Cのプログラムを作るRubyのプログラムを作ってみました。

n = 1
list = 80.times.map do |i|
  n *= 3 while n < 10**i
  n / 3
end

puts '#include <stdio.h>'
print 'static char *list[] = {'
print list.map{|i| "\"#{i}\""}.join(",")
puts '};int main(void){int n;if(scanf("%d",&n)!=1||n<=0||n>=80)return 1;printf("%s\n",list[n]);return 0;}'

計算量O(1)とは素晴らしいです。

Comments

[grape_ll]

申し訳ございません。私の知識不足でRubyの書き方はまったくわかりません。
しかし、この質問を見た他の人にはわかるかもしれません。
ご回答ありがとうございました。

Answer 7

小学生の算数の計算のように、一桁ずつchar型配列に入れて計算してみてはいかがですか？
理屈が分かれば、long型配列にして効率的に計算することもできます。

　　４５６
＊　　　３
ーーーーー
＋　　１８
＋　１５
＋１２
ーーーーー
＝１３６８

radianさんのコメントに書かれたコードを改良してみました。

#include <stdio.h>

int main(void) {
    int n;
    scanf("%d", &n);
    int value[80] = {9};
    int answer[80];
    int carry = 0;
    while (carry == 0) {
        for (int i = 0; i < n; i++) {
            answer[i] = value[i];  // copy last value to answer
            carry += value[i] * 3;
            value[i] = carry % 10;
            carry /= 10;
        }
    }
    for (int i = n - 1; i >= 0; i--) {
        printf("%d", answer[i]);
    }
    printf("\n");
    return 0;
}

Comments

[grape_ll]

数を分離するやり方で考えてみようと思います。
ご助言ありがとうございます。

[shiracamus]

改良コードを追記しました。

[grape_ll]

ご丁寧にどうもありがとうございます。
参考にさせていたきますね。
今後とも機会があればぜひよろしくお願いいたします。