(1+sqrt(3))^(n+1) の大べき乗を見つけたいと思います。ここで、n は n=1 から n=1000,000,000 まで変化します。二乗によるべき乗剰余は double で機能しますか? どのように？私はたくさん検索しましたが、まだ肯定的な結果はありません.何か助けていただければ幸いです?
1 に答える
2
「2 乗による剰余累乗は double で機能しますか?」という質問に対する答えです。いいえ、私が説明するいくつかの仮定を考えると。
1,000,000,007 を法とする剰余を取るなどの操作は、さまざまな数論計算やその他の整数演算の典型です。したがって、整数精度で結果を計算したいと仮定します。つまり、ある n、0 < n ≤ 10 9に対して (1+sqrt(3))^(n+1) % 1,000,000,007 に最も近い整数を知りたいのです。関数 x n+1を考えてみましょう。x に関する導関数は (n+1)x nです。x が 1+sqrt(3) で n が 10 9の場合、導関数は約 4.65•10 436488780です。これは、4.65•10 436488780の約 1 分の x の変化が x n+1の値を変化させることを意味します。約 1 で、もちろん剰余も約 1 変化します。したがって、望ましい精度で剰余を計算するには、実際には、1+sqrt(3) の値を小数点以下 4 億 3600 万以上まで計算する必要があります。
これは、最新のコンピューターの double 型によって提供される精度を大幅に超えています。したがって、答えはノーです。double 型は必要な精度で計算できないため、どのアルゴリズムも希望する答えを返すことができません。
技術的には、倍精度演算を使用して拡張精度演算を構築できます。(したがって、上記の答えは、通常の方法で倍精度演算を使用する場合に対処されます。)したがって、特別な手法を使用して、倍精度演算から必要な計算を作成できます。これを行う方法の議論は、スタック オーバーフローの質問を超えています。一般に、整数演算はそのような作業の大部分に使用されますが、倍精度演算が役割を果たすこともあります。また、GMP (GNU Multiple Precision Arithmetic Library) などの拡張精度演算を提供するソフトウェア パッケージを利用できます。
4 億 3,600 万の小数点以下の桁数を計算して保持すると、コンピューティング リソースに負担がかかる場合があります。最終的な剰余に影響を与えないことを示すことができる情報を破棄することで、必要な計算を削減できる可能性があります。これにより、小数点以下 4 億 3,600 万桁すべてが同時に必要になるわけではありません。ただし、そのような削減によって、拡張精度技術を使用しない倍精度演算で実行可能な計算が生成されるとは思いません。
そして、問題はそれよりも悪いです。x が 4.65•10 436488780の約 1 分の 1 であることを知っていれば、誤差 1 以内で結果を計算するのに役立つかもしれませんが、どの整数が最も近いかはわかりません。(1+sqrt(3)) n+1 % 1,000,000,007 を計算すると、結果が 3.5 に非常に近いことがわかります。結果に最も近い整数が 3 か 4 かを判断するには、結果が 3.5 のどちら側にあるかを特定する必要があります。この関数 (1+sqrt(3)) n+1には、中間位置に非常に近い値が含まれている可能性があり、適切な決定を行うには、それらをさらに正確に計算する必要があります。
于 2012-07-06T14:30:00.837 に答える