7

実数があるとします。整数 a と b に対して a+sqrt(b) の形式で近似したいと思います。しかし、a と b の値がわかりません。もちろん、a と b の値を小さくして適切な近似値を得たいと考えています。「良い」と「小さい」が何を意味するのかは、今のところ未定義のままにしましょう。これらの用語の適切な定義は何でも構いません。

それらを見つけるための健全な方法はありますか？小数の分数近似を見つけるための連分数アルゴリズムのようなもの。分数の問題の詳細については、こちらを参照してください。

編集：明確にするために、それは任意の実数です。私が持っているのはその数字の束だけです。したがって、求める近似の程度に応じて、a と b が存在する場合と存在しない場合があります。ブルート フォースは当然、特に優れたアルゴリズムではありません。私が考えることができる最善の方法は、実数に整数を追加し、結果を二乗して、整数に近づくかどうかを確認することです。かなりブルートフォースであり、特に優れたアルゴリズムではありません。しかし、それ以上のものが存在しないとすれば、それ自体が興味深いことです。

編集:明らかに b はゼロまたは正でなければなりません。しかし、a は任意の整数である可能性があります。

4

5 に答える 5

6

連分数は必要ありません。のすべての「小さい」値の平方根を計算しb（まだ十分に「小さい」と思われる値まで）、小数点の前のすべてを削除し、それらをすべて並べ替え/保存します（それbを生成したものと一緒に）。

次に、実数を近似する必要がある場合は、小数部分が実数の小数部分に最も近い根号を見つけます。これによりb、正しいものを選択することaは、単純な引き算の問題になります。

于 2012-12-14T18:49:59.763 に答える
5

これは実際にはコンピューターの問題というよりは数学の問題ですが、質問に答えるには、連分数を使用できるのは正しいと思います。あなたがすることは、最初に連分数として目標数を表すことです。たとえば、円周率（3.14159265）を概算する場合、CFは次のようになります。

3：7、15、1、288、1、2、1、3、1、7、4..。

次のステップは、平方根のCFのテーブルを作成し、テーブル内の値をターゲット値の小数部分（ここでは、7、15、1、288、1、2、1、3、1）と比較します。 7、4 ...）。たとえば、テーブルの平方根が1-99のみであるとします。次に、最も近い一致は7：7,14のCFが繰り返されるsqrt（51）であることがわかります。7,14は、円周率の7,15に最も近い値です。したがって、あなたの答えは次のようになります。

sqrt（51）-4

与えられたab<100に最も近い近似として、0.00016ずれています。より大きなbを許可すると、より良い近似を得ることができます。

CFを使用する利点は、たとえば2倍で作業したり、浮動小数点を使用したりするよりも高速であるということです。たとえば、上記の場合、2つの整数（7と15）を比較するだけでよく、インデックスを使用して、テーブル内の最も近いエントリを非常に高速に見つけることもできます。

于 2012-12-14T18:36:58.530 に答える
1

以前の回答のいくつかは、時間または空間の複雑さO（n）の方法を使用しています。ここで、nは受け入れられる最大の「少数」です。対照的に、次のメソッドは、時間ではO（sqrt（n））、空間ではO（1）です。

正の実数r = x + y、ここでx=floor(r)、0 ≤ y < 1。rいくつかの形式で近似したいと思いa + √bます。その場合、整数オフセットの場合x+y ≈ a+√bは、、および。bを整数にするには、適格なすべてのの小数部分を最小化します。の適格な値は多くてもあります。次のPythonコードとサンプル出力を参照してください。x+y-a ≈ √b√b ≈ h+yhb ≈ (h+y)^2(h+y)^2h√nh

import math, random

def findb(y, rhi):
    bestb = loerror = 1;
    for r in range(2,rhi):
        v = (r+y)**2
        u = round(v)
        err = abs(v-u)
        if round(math.sqrt(u))**2 == u: continue
        if err < loerror:
            bestb, loerror = u, err
    return bestb

#random.seed(123456)     # set a seed if testing repetitively
f = [math.pi-3] + sorted([random.random() for i in range(24)])
print ('    frac     sqrt(b)       error       b')
for frac in f:                   
    b = findb(frac, 12)
    r = math.sqrt(b)
    t = math.modf(r)[0]         # Get fractional part of sqrt(b)
    print ('{:9.5f}  {:9.5f}  {:11.7f}  {:5.0f}'.format(frac, r, t-frac, b))

（注1：このコードはデモ形式です。パラメーターfindb()はy、、の小数部r、およびrhi、最大の少数の平方根です。パラメーターの使用法を変更することをお勧めします。注2：
if round(math.sqrt(u))**2 == u: continue
コードの行findb()はb値b=1を除いて、の完全な二乗値を返します。これは、完全な二乗がb = 1によって提供される精度を向上させることができないためです。）

サンプル出力は次のとおりです。途中で約12行が省略されています。最初の出力行は、この手順がb=51の小数部分を表すことを示していますpi。これは、他のいくつかの回答で報告されている値と同じです。

    frac     sqrt(b)       error       b
  0.14159    7.14143   -0.0001642     51
  0.11975    4.12311    0.0033593     17
  0.12230    4.12311    0.0008085     17
  0.22150    9.21954   -0.0019586     85
  0.22681   11.22497   -0.0018377    126
  0.25946    2.23607   -0.0233893      5
  0.30024    5.29150   -0.0087362     28
  0.36772    8.36660   -0.0011170     70
  0.42452    8.42615    0.0016309     71
   ...
  0.93086    6.92820   -0.0026609     48
  0.94677    8.94427   -0.0024960     80
  0.96549   11.95826   -0.0072333    143
  0.97693   11.95826   -0.0186723    143

プログラムの最後に次のコードを追加すると、以下の出力も表示されます。これは、円周率の小数部分の近似値を示しています。

frac, rhi = math.pi-3, 16
print ('    frac        sqrt(b)         error          b     bMax')
while rhi < 1000:
    b = findb(frac, rhi)
    r = math.sqrt(b)
    t = math.modf(r)[0]         # Get fractional part of sqrt(b)
    print ('{:11.7f}  {:11.7f}  {:13.9f}  {:7.0f}  {:7.0f}'.format(frac, r, t-frac, b,rhi**2))
    rhi = 3*rhi/2

    frac        sqrt(b)         error          b     bMax
  0.1415927    7.1414284   -0.000164225       51      256
  0.1415927    7.1414284   -0.000164225       51      576
  0.1415927    7.1414284   -0.000164225       51     1296
  0.1415927    7.1414284   -0.000164225       51     2916
  0.1415927    7.1414284   -0.000164225       51     6561
  0.1415927  120.1415831   -0.000009511    14434    14641
  0.1415927  120.1415831   -0.000009511    14434    32761
  0.1415927  233.1415879   -0.000004772    54355    73441
  0.1415927  346.1415895   -0.000003127   119814   164836
  0.1415927  572.1415909   -0.000001786   327346   370881
  0.1415927  911.1415916   -0.000001023   830179   833569
于 2012-12-15T00:27:42.193 に答える
1

これは、混合整数二次計画法を使用して非常に効率的に実行できます (ただし、MIQP は NP 完全であるため、実行時の保証はありません)。

定義：

d := the real number you wish to approximate
b, a := two integers such that a + sqrt(b) is as "close" to d as possible
r := (d - a)^2 - b, is the residual of the approximation

目標は最小化することrです。二次計画を次のように設定します。

x := [ s b t ]
D := | 1 0 0 |
     | 0 0 0 |
     | 0 0 0 |
c := [0 -1 0]^T
with the constraint that s - t = f (where f is the fractional part of d) 
and b,t are integers (s is not)

が半正定であるため、これは凸 (したがって最適に解ける) 混合整数二次計画D法です。

が計算されたら、s,b,tを使用して答えを導出するだけで、無視できます。b=bs=d-at

あなたの問題はNP完全である可能性があります。そうであれば、それを証明することは興味深いでしょう。

于 2012-12-14T20:53:46.583 に答える
0

この種の問題に標準的なアルゴリズムがあるかどうかはわかりませんが、興味をそそられるので、必要な近似を見つけるアルゴリズムを開発する試みをここに示します。

問題の実番号に電話してrください。次に、最初にそれが負になる可能性があると仮定します。その場合、問題を減らすことができ、の小数部がの小数部の適切な近似であるようなものaを見つけるだけで済みます。ここで、整数と小数部分のように記述しましょう。bsqrt(b)rrr = x.yxy

Now:
b = r^2
  = (x.y)^2
  = (x + .y)^2
  = x^2 + 2 * x * .y + .y^2
  = 2 * x * .y + .y^2 (mod 1)

私たちは今、 （おおよそ）xそのようなものを見つける必要があるだけです。0 = .y^2 + 2 * x * .y (mod 1)

x上記の式にそれを入力すると、次のようにb計算できます。（もちろん、これらの計算はすべて慎重に丸める必要があります。）aa = r - b

さて、当分の間、xブルートフォースなしでこれを見つける方法があるかどうかはわかりません。しかし、それでも、単純なループを使用して、x十分なものを見つけることができます。

私はこのようなものを考えています（半擬似コード）：

max_diff_low = 0.01 // arbitrary accuracy
max_diff_high = 1 - max_diff_low
y = r % 1
v = y^2
addend = 2 * y
x = 0
while (v < max_diff_high && v > max_diff_low)
    x++;
    v = (v + addend) % 1
c = (x + y) ^ 2
b = round(c)
a = round(r - c)

さて、このアルゴリズムはかなり効率的だと思いますが、近似の希望する精度を指定することもできます。これをO（1）アルゴリズムに変換するために実行できることのひとつは、すべてを計算xしてルックアップテーブルに入れることです。r（たとえば）の最初の3桁だけを気にする場合、ルックアップテーブルには1000個の値しかありません。これは、メモリの4kbだけです（32ビット整数が使用されていると仮定します）。

これがお役に立てば幸いです。誰かがアルゴリズムに何か問題を見つけた場合は、コメントで知らせてください。修正します。

編集： 振り返ってみると、私は効率性の主張を撤回します。実際、上で概説したアルゴリズムが終了するという保証はありません。たとえ終了したとしてもx、方程式を適切に解く非常に大きなものを見つけるのに長い時間がかかる可能性があります。

これまでに見つかった最良のものを追跡し、x時間の経過とともに精度の限界を緩和して、アルゴリズムが迅速に終了するようにすることができますが、精度が犠牲になる可能性があります。

もちろん、ルックアップテーブルを事前に計算するだけであれば、これらの問題は存在しません。

于 2012-12-14T18:32:18.287 に答える