【ヘキサ星人との遭遇】に関するコメント

解答を公開している問題はコメントを投稿できません

コメント

log()の外側を +1 して floor するという方法もありますが、
log()の内側を +1 して、そのまま ceil するという方法もあります。
後者の方が(N進法において、あくまで整数を扱う限りにおいては) 扱いやすいかもしれませんね。

例：
1000 は十進法で何桁？
log_10(1000+1) = 3.000434...
故に ceil して 4桁

logの値をceilしてはいけないのは単純な話です。
例で示したように、1000 は十進法で4桁の数ですが、log_10(1000) は丁度 3 になってしまいます。表記した際の桁数を正確に示すためには、「対数が丁度 n」の場合は n+1 となる必要があります。
よって、「1を足してfloor」という計算が必要です。

誤差については、↓に示した私の方法では、上の 1 を足して floor するという部分を取り払って計算してしまっています。例えば、以下のような時には問題になります。
　2^2 は2進法では3桁ですが 4進法では何桁？
3 * log(2) / log(4) = 1.5 ですが、1桁ではいけない。答は2桁です。
ただし、少し考えてみましたが、2進から12進への変換で、2^n丁度という数については、これが問題になることは無さそうですね。
(2^n (n>1) が 12^m (m は整数) になることは無いですから)

５６１桁なのは自分の計算と一緒なんすけど、誤差の検証や「logの値をceilするのではなく、実数での植木算的に1を足してfloorする」の部分がイマイチ良く解ってなかったりする。…orz

底が１２の対数取って、携帯の電卓で＝５６０、７１３…。と出てきたので５６１桁！とやったkikki氏でした(´∀｀)。もうちょっと読んでみます…。

kikkiさんによるコメントでの発展出題2題:

　(1)　十二進法 0.ABABABABAB… を十進法の既約分数で表わせ。

　(2)　2^2010 (十進) を、十二進法で表示すると何桁の数になるか？
　　ただし、底を10としてlog2=0.301, log3=0.477 と近似して計算せよ。


この下には私の解答例が書いてあります。

N進表記をした場合の整数Mの桁数とは:
　int(log(M) / log(N) + 1)
ただしここで
　log(x): x の自然対数
　　(上の式の中だけならば自然対数でなくとも、底は何でもいい)
　int(x): x を越えない最大の整数
　　(floor function、あるいはガウス記号とも)

例えば、999、1000 はそれぞれ 10進表記で:
　int(log(999) / log(10) + 1) = int(3.99..) = 3 桁
　int(log(1000) / log(10) + 1) = int(4) = 4 桁

2^10=1024、2^10-1=1023 はそれぞれ、2進表記で:
　int(log(1023) / log(2) + 1) = int(10.99..) = 10 桁
　int(log(1024) / log(2) + 1) = int(11) = 11 桁

(境界領域での正確な桁数を出すには、logの値をceilするのではなく、
実数での植木算的に、1を足してfloorするのがポイント)

上の式において、N = e (自然対数の底) とした場合、 log(N) = 1 となることから明かなように、int(log(M)+1) は基数を e とした場合の桁数を表わしている。

さらに言えば、int(log_N(M)+1) はそのままずばり N進表記での M の桁数である。
(ただしここで log_N(M) は「底をNとしたMの対数」つまり「N^(log_N(M)) = M」)

よって基数表記間での桁数の変換を行うには、対数の世界だけで計算を行うことができる。
(対数の底変換と同じような方法。)

数MのN進からL進への桁数の変換とは、
log_N(M) を log_L(M) へと変換するということである。
N進での桁数をRn、L進での桁数をRlとすると、
　Rn = int(log(M) / log(N) + 1)
　Rl = int(log(M) / log(L) + 1)
ここで境界域を無視してint()と+1をとり除くと
　Rn ≒ log(M) / log(N)
　Rl ≒ log(M) / log(L)
　∴ Rl ≒ Rn * log(N) / log(L)

M は 2^2010 (10進) なので、2進法で 2011 桁。
つまり N = 2 として Rn = 2011。
ここで L = 12 として Rl を求めると:
　Rl = 2011 * log(2) / log(12)

ただし出題の条件は「10を底とした対数にて計算」なので
(以下、10を底とした対数を logd と書く)
　Rl = 2011 * logd(2) / logd(12)
とし 12 = 2 * 2 * 3 から計算すると
　Rl = 2011 * logd(2) / (logd(2) + logd(2) + logd(3))
　　= 2011 * 0.301 / (0.301 + 0.301 + 0.477)
　　= 2011 * 0.279... = 561.069...

なお精度を高めるために2^2010を4進法にして計算してみると
　Rl = 1006 * logd(4) / logd(12)
　　= 2011 * (0.301 + 0.301) / (0.301 + 0.301 + 0.477)
　　= 561.2715...

いずれも 561桁を示しているが、計算順序による誤差積算と
境界域の扱いとについてさらに検証を行う必要がある。

少し間があいてしまって覗いてみてびっくりしました^^
>キョンシーさん
そうです、どんな表現をしようとも 1 は 1 なんです。

>kikkiさん
そんなに変わった方法だったかな？
どんな公式を知らなくても納得してもらいやすい形だったと思いますが。
(ただし無限の概念への納得は必要かもしれませんが)

コメントの順番を考えて、まずは正解から:
　561桁

簡単にですが多倍長精度演算ライブラリーを作りなおして検算したので確かなはずです。
解説し過ぎだということでしたら、削除キー 1234 で削除してください。
また解説に間違いがや、まどろっこしいところがありましたらご指摘ください。
(昼酒飲みながら書いてるんで、どこか間違ってそう^^;)

やっぱり 0.BBBB…=1 なんですね。

若さん＞
そんな方法を使うとは…(^^)　僕は等比級数の公式使うことしか思いつかなかった。

んじゃ次は…２＾２０１０[10]は十ニ進法で表示すると何桁の数になるか？　低を１０として、log2＝0.301　log3＝0.477　と近似して計算せよ。

循環小数の分数表記化についてはやり方いろいろありますが、
比較的よくある簡単な方法で。
(以下、12進法での表記を NNN_(12) と書きます。
ただしここで各Nは12進法のディジット('0'..'B'))

n = 0.ABABAB..._(12) とすると
n × 100_(12) - n = AB.ABABAB..._(12) - 0.ABABAB..._(12)
　= n × BB_(12) = AB_(12)
∴ n = AB_(12) / BB_(12)
　　= 131/143 (in decimal)

0.A1A1A1... だともう一段面白かったかな？

(ノナの問題の kikki さんのコメント内で一箇所…と言おうとしたら、直ってた^^)

＞若さん
朝は有難うございました！
んでは　０、ＡＢＡＢＡＢＡＢＡＢＡＢ…を十進法で…。

＞takaさん
実は僕も最近知りました(^^)。

キョンシーさん＞
ところで「鬼ごっこ問題」の方は^^;？

そういやこんなのありましたね。
ちなみにVisual Studioは最大で36進数（0〜9、A〜Z）までサポートしてるらしいです。
使ったことないですけどｗ

少数表記は親しみが無く、なんとか３発で＾＾；
ありがとうございました。

すちゃっと暗算させてもらいました^^
コンピュータ内での実数表現はほぼ全て2進数による少数表現ですね。
といっても、浮動小数点形式なことと、implicit one (俗にいうケチ表現)が使われていますので、バイナリデータを見てもすぐにピンとは来ないかもしれませんけど。