問題タブ [continued-fractions]

より多くのSICPを読んで、私は演習1.3.8で立ち往生しています。私のコードは1/phiを近似するために正しく機能しますが、e-2を近似するためには機能しません。

e-2で.7blahblah blahを取得する代わりに、.5blahblah何かを取得しています。理由がわかりません。「eulers-e-2」関数で「d」が正しく定義されていると確信しています。

編集：みんなありがとう、私はそれを逆に計算していました。これが修正されたコードです。

（編集：不機嫌そうなコメントに応えて、いいえ、宿題ではありません。私はピッチ検出に取り組んでおり、潜在的な高調波ピークの配列を取得し、基本周波数の候補を構築しようとしています。したがって、実際には非常に実用的な質問です。 ）。

分母の増加順に並べられた、（たとえば）円周率の最良の分数近似を検討してください：3 / 1、22 / 7、355 / 113、..。

課題：特定のフロートに対してn番目の商近似a / bを生成し、不一致も返す、きちんとしたCアルゴリズムを作成します。

calcBestFrac（float frac、int n、int * a、int * b、float * err）{...}

私が信じる最高のテクニックは連分数です

円周率の小数部分を取り除くと、3が得られ
ます。これで、余りは0.14159 ... = 1/7.06251になります。

したがって、次善の有理数は3 + 1/7 = 22/7
です。7.06251から7を取り除くと、0.06251になります。おおよそ1/15.99659。

それを16と呼ぶと、次善の近似は
3 + 1 /（7 + 1/16）=355/113です。

ただし、これをクリーンなCコードに変換するのは簡単ではありません。何か整頓されたら投稿します。その間、誰かが頭の体操としてそれを楽しむかもしれません。

先日、Wolfram ブログに 13 歳の少年 Neil Bickfordに関する記事が掲載されました。彼は、 から始まる pi の単純連分数表現の最初の 4 億 5,800 万項を計算しました[3; 7, 15, 1, 292, ...]。Bickford は彼のブログで彼の業績を説明し、Bill Gosper のアルゴリズムを引用さえしましたが、私はそのアルゴリズムを解明することができませんでした。

私が知っていることの 1 つは、連分数に関するウィキペディアの記事に記載されている方法を使用して、pi の 10 進表現を連分数に変換する方法です。しかし、それには十分な桁数の pi の 10 進表現が必要であり、確かに Bickford は彼の計算を裏付ける数百万桁の pi を持っていませんでした。

ビックフォードが計算に使ったアルゴリズムについて、かなり詳しく説明してくれませんか?

Project euler Problem 57 (このサイトが大好き!) に取り組んでいます。この問題では、有限連分数と通常の分数の間の変換が必要です。基本的にリストの最後の数字の逆数を取り、それを最後から 2 番目の数字に追加し、最後の分数が残るまで継続するアルゴリズムを考案しました。問題 67 では見事に機能しましたが、今回は 2 回目の反復後に機能しなくなりました (複数の連続した分数に対してアルゴリズムを実行する必要があります)。

これはコードの一部です（外部モジュール、つまりsympyを使用しました）：

私は基本的に、すべての最終分数を取得するかどうかをテストし、関数からの出力が返される前に答えを返しますが、値を sqrt_eval に割り当てた後の出力は None を出力します。ここにテスト実行があります：

私は答えを徹底的に探してきましたが、まったく見つけることができません。可能であれば、コードをあまり変更せずに、これをデバッグするのを手伝ってください。

n桁の精度を得るために黄金比が必要な項数mを計算するMatlab関数を作成しようとしています。ここに私がこれまでに持っているものがありますが、出力は0のままです。

これは、数論を学んでいる人や、Matlab を学び始めたばかりの人によくある質問だと思います。何かアドバイス？ありがとう！

そこで、二次整数と有理数のサブセットを処理するための連分数ライブラリを実装しています。連分数項は符号なし整数で表されます。連分数を扱うとき、次の一般的なパターンに気付きました。

1. ほとんどの用語は 1 桁の小さな数字で、1 が最も一般的です。
2. 一部の用語は非常に大きくなる可能性があり、私のアプリケーションで可能な最大値は 366 ビットですが、これらは非常にまれです。
3. 大きな項は、特に優れた数の近似を表します。これは、通常、大きな分数に対して全体的に少ない項があることを意味します。
4. 連分数の最悪の可能性は黄金比であり、366 ビットの精度での有理近似は、約 525 個の 1 の連続に相当します。
5. 乱数の有理数は、通常、同じ数の大きな連続はありませんが、2 つから 4 つ連続して存在する場合があり、1 が最も一般的です。

そのため、用語の数と用語のサイズの両方に制限があり、用語の数はそれらのサイズにほぼ反比例します。したがって、これらの項を機械語またはバイト単位で格納することは通常、スペースを非常に浪費し、最悪の場合でも複数語の演算を処理する必要があります。項のサイズと項の数の間のほぼ逆の関係 (どちらも分数の分子と分母のサイズにも依存します) を考えると、無駄にならないように、適切な圧縮スキームを見つけようとしてきました。整数項を格納する非常に多くのスペース。

エンコードとデコードの速度が優れているため、 Huffman encodingを検討しましたが、コード値の確率をどのように計算するかわかりません。連分数と直接的な関係を持つ二分木であるため、スターン-ブロコ木がヒントになるかもしれないという漠然とした直感があります。

同じ数の実行が通常短い（ただし、まれに長くなる可能性がある）ときどき巨大なものを使用して、多数の小さな数を処理するための優れた圧縮アプローチを知っている人はいますか? 特に、かなり高速にエンコードおよびデコードできる必要があり (たとえば、O(n*lg(n)) は私が許容できる最悪の速度であり、O(n) またはそれ以上の速度が望ましい)、個々のタームの位置を調べて、どのターム番号 (第 4 ターム、第 5 タームなど) で操作しているかがわかるようにします。

また、サードパーティの実数または連分数ライブラリの使用には興味がありません。私はいくつかを見てきましたが、それらは私のニーズに対して不十分かやり過ぎであり、私自身の啓発のためにこれを自分でコーディングする経験が欲しいです.

アップデート

また、0 と 1 の間で一様に分布する乱数の特定の連分数項の確率分布を与えるガウス クズミン分布についても学びました。k

P(k) = -lg(1.0 - 1.0/((k + 1.0)**2)Python 疑似コードでは、lg は 2 を底とする対数です。これはk無限に近づく限界であるため、私のケースはやや制限されています2**366(まだ巨大ですが)。Linas Vepstas による「連分数のエントロピー」は、ガウス クズミン分布の (情報) エントロピーを約 3.43 ビットとして提供します。私の分母の最大値は十分に大きいので、連分数の情報エントロピーはおそらくその限界に近くなりますが、リンクされた記事のグラフは限界に非常にゆっくりと近づいていることを示しており、分母が比較的小さい場合は異なります。

私は Python を初めて使用し、入力を非負の整数 n として受け取り、連分数の最初の n + 1 項を使用して e の値の近似値を計算するプログラムを作成するように依頼されました。

質問を解読しようとしましたが、質問のすべてを正確に理解することはできません。正確な答えを探しているわけではありませんが、途中で役立つ例を期待しています。

これは正確な質問
です。以下は、以前に連分数で行ったコードです。

私は現在、Project Euler の Probelm 57 で作業しています。

https://projecteuler.net/problem=57

私の問題は、正しい答えが与えられていると信じていますが、桁数のカウントが正しくないように見えることです。エラーが何であるかはわかりません。コードをより明確にするために、コメントを含めました。

私のコードは 1393/985 の分数を正しく認識しますが、約 i=30 を過ぎると、うまくいかないようです (どこかでオーバーフローする可能性がありますか?)。

前もって感謝します！

PSどうやら答えは153ですが、253になります