java - Javaで無理数の小数点以下の桁数を多数見つける

Question

Javaで小数点以下22/7から10^6桁までの値を求めたいです。短いコンパイル時間でこれを行うことは可能ですか?

Answer 1

ペンと紙を用意して、22/7 を分割してみてください。このようになります

03,142857142857
---
22:7
0
--
22
21
--- < now we calculate fractal part so we will add zeros at the end
 10 # 10 contains 7 only one time -> 1
  7
 ---
  30 # 30 contains 7 four times -> 4
  28 
  ---
   20  ->2
   14
   --- 
    60  ->8
    56
    ---
     40  ->5
     35
     ---
      50  ->7
      49
      ---
       10 # but wee already calculated this state of fractal part
          # so from now on it will repeat again and again and again... 
          # giving ...142857|142857|142857...

だから22/7 = 3,(142857)。周期部分がフラクタル部分の最初の位置から始まり、6 桁が含まれていることがわかっているので、その10th桁は8(周期部分の 4 桁目)、20th位置は4(周期部分の 2 桁目) であると計算できます。周期部分が最初の位置から始まる場合、n 桁目は (n)mod (周期の桁数) になるため10 % 6 = 4、周期部分の 4 桁目は 、周期部分の8220 % 6 = 2桁目は であることに簡単に気付くことができ4ます。

したがって、キャッシュする独自のアルゴリズムを実装することができます (配置されたキー->値のペアの順序を記憶するマップで考えてみましょう)。

• 繰り返し部分を見つけます
• ある時点で (5/4 = 1.250000 のように) フラクタル部分が終了します
• 周期部分を見つけずに数字を計算しますn-th(22/7 の 2 桁目は周期を見つける前に返すことができます)

---

追加情報。minimal value of X%Yピリオドは、 is 0(その場合、除算を停止します) およびmax value of X%Yisであるため、除算に使用した数値よりも長くすることはできませんY-1。したがって、周期部分で使用できるのは 1 から Y-1 の間の数字のみであるため、その最大長はY-1