編集履歴

回答編集履歴

修正

2020/05/23 15:41

投稿

スコア28669

test CHANGED Viewed

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

追記

2020/05/23 15:40

投稿

Zuishin

スコア28669

test CHANGED Viewed

@@ -51,3 +51,11 @@
 [指数法則 - Wikipedia](https://ja.wikipedia.org/wiki/%E5%86%AA%E4%B9%97#%E6%8C%87%E6%95%B0%E6%B3%95%E5%89%87)
+### 追記
+多倍長演算の乗算は必要ないかもしれません。3 は 2 進数で 11 なので、何かに 3 をかけるということは、その数を左に 1 ビットシフトしたものとその数自身を足したものに等しくなります。ビットシフトと加算を 165 回繰り返すだけなので、十分高速に結果が求まると思います。また、3 にビットシフトを 164 回繰り返すと 165 ビットなので、そこに加算した繰上りを入れても 166 ビットつまり 21 バイトに収まります。バッファは計算しながら動的に確保しなくても、21 バイト固定で間に合うはずです。後の問題はそれを 10 進数に直す際の除算ですね。しかしここまで十分高速に計算できているので、間に合いそうな気がします。

修正

2020/05/23 15:39

投稿

Zuishin

スコア28669

test CHANGED Viewed

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

修正

2020/05/23 14:35

投稿

Zuishin

スコア28669

test CHANGED Viewed

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

修正

2020/05/23 14:33

投稿

Zuishin

スコア28669

test CHANGED Viewed

@@ -18,15 +18,15 @@
-話を戻して x = p(3, t) = p(10, d) ですが、ここで 10 = p(3, l(10, 3)) なので、これを代入すると x = p(3, t) = p(p(3, l(10, 3)), d) となります。
+話を戻して 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(10, 3) * d) が成り立つため、t = l(10, 3) * d となります。ここで l(10, 3) は定数約 0.477121254719662 であり、d = t / l(10, 3) が成り立ちます。ここで t に n を代入することにより、d = n / 0.477121254719662 で求めることができます。
+冪乗の指数法則より、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 / 0.477121254719662)) です。
+結論として、実数 a の小数点以下を切り捨てる架空の関数 int を考えた時、求める数は p(3, int(n * 2.09590327428938)) です。
@@ -34,7 +34,7 @@
-p(3, int(79 / 0.477121254719662)) = p(3, 165) = 5308930362839928667688049530226627139643793175493798707037516219525092562313843
+p(3, int(79 × 2.09590327428938)) = p(3, 165) = 5308930362839928667688049530226627139643793175493798707037516219525092562313843

修正

2020/05/23 11:21

投稿

Zuishin

スコア28669

test CHANGED Viewed

@@ -14,7 +14,7 @@
-なぜ 10 を底とする冪を考えるかというと、これで 10 進数における桁数が求められるからです。例えば 0 は 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 となります。
+なぜ 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 となります。