のPython 2.7 - 連分数展開 -

Question

エラーを理解し、私は有理数の連分数展開を計算するためにこのコードを書かNユークリッドアルゴリズムを使用してきました：

from __future__ import division 

def contFract(N): 
    while True: 
     yield N//1 
     f = N - (N//1) 
     if f == 0: 
      break 
     N = 1/f 

場合は、Nが3.245関数であると言います

[3.0、4.0、12.0、3.0、1.0、247777268231.0、4.0、1.0、2.0、1.0]

：膨張0最初の10件の用語であり等しく決してFと明らかに終わることはありません実際の展開だけであるので、明らかに誤りである

：

[3; 4,12,3,1]または[3; 4,12,4]引き起こして何

ここの問題？何らかの丸め誤差ですか？

Answer 1

問題はf == 0（整数0）をテストしていることです。浮動小数点の場合はほとんどありません。だから、ループは永遠に続く。代わり

、（which can be wrong sometimes）0に等しいいくつかの精度を確認：

>>> from __future__ import division 
>>> 
>>> def contFract(N): 
...  while True: 
...   yield N//1 
...   f = N - (N//1) 
...   if f < 0.0001: # or whatever precision you consider close enough to 0 
...    break 
...   N = 1/f 
... 
>>> 
>>> list(contFract(3.245)) 
[3.0, 4.0, 12.0, 3.0, 1.0] 
>>> 

と負とすることができる場合fには、-0.0001 < f < 0.0001又はabs(f) < 0.0001いずれかを行います。どちらも不正確であると考えられている、リンクされた記事を参照してください。

そして、それは明確だからint(N)の代わりN//1を使用するように私のコメントをWRT - それはわずかあまり効率的である：

>>> import timeit 
>>> timeit.timeit('N = 2.245; N//1', number=10000000) 
1.5497028078715456 
>>> timeit.timeit('N = 2.245; int(N)', number=10000000) 
1.7633858824068103 

Answer 2

どうやらバグが浮い1. 4.0で4.0の整数の除算によるものです浮動小数点表記についての考え方がある場合は、エラーが発生します。実際にはint（4.0）< 4. N // 1は3.0になり、小数部fは0.999999となります。これは決して終わりません。すべての反復でNとfを印刷し、周りを再生します。あなたは気づくでしょう。

Answer 3

ご使用の操作にはfloatが使用されていますが、残念ながら一部の数値はバイナリ形式の数値では表現できません。

この問題を解決するには2つの方法があります。まず、数字が「十分に近い」（新しいPython 3.5.2でもmath.iscloseが導入されている）と仮定するか、浮動小数点数の異なる実装を使用しています。 Decimalあなたは適切な結果を得ることができます。

N.b.これは、すべての金融システムで、誰もフロートを使用していない理由、int/bigintまたはDecimalsのみを使用する理由です。

 In [21] > N = decimal.Decimal('3.245') 

 In [22] > while True: 
    print 'N: %s' % (N//1,) 
    f = N - N//1 
    print 'f: %s' % f 
    if f == 0: 
     break 
    N = 1/f 

N: 3 
f: 0.245 
N: 4 
f: 0.081632653061224489795918367 
N: 12 
f: 0.25000000000000000000000005 
N: 3 
f: 0.999999999999999999999999200 
N: 1 
f: 8.00E-25 
N: 1250000000000000000000000 
f: 0