fixedpoint.jp




2016/07/06

浮動小数点数を近似するための連分数の応用: LibreOfficeの場合

任意の実数を表現する方法の1つとして、連分数が知られています。有理数であれば有限連分数で表すことができ(表現が2通りある場合がありますが)、無理数であれば無限連分数で一意に表せます。

有理数のうちでも限られた範囲しか取らない浮動小数点数を扱うアルゴリズムにおいても、しばしば連分数が利用されます。今回はLibreOfficeのコードに新たに採用された、与えられた浮動小数点数のfractional partを分数で近似するアルゴリズムを紹介します。

具体的には、分母の大きさに制限を加えた形での書式化に利用されているコードです。例えば、Calcのセルの書式設定において分数を指定した場合などに用いられます。従来はファレイ数列を使って計算されていたところを、best rational approximationにしたがって連分数による近似列を生成することで解くようになりました:

https://cgit.freedesktop.org/libreoffice/core/commit/?id=051329101dc249535dd09eeb34caf1c21719064f

このコミットのコメントに書かれているように、従来よりコードが簡潔になると同時に、分母の10進桁数が3桁より大きい場合には近似精度が向上し、さらに速度性能も向上するそうです。おそらくこの変更はLibreOffice 5.3でリリースされるはずです。

参考

#permalink

Archives

2016: Mar / Feb / Jan

2015: Dec / Oct / Sep / Jul / May / Mar / Feb

2014: Dec / Nov / Oct / Aug / Apr / Mar / Feb / Jan

2013: Dec / Nov / Oct / Sep / Aug / Jun / May / Apr / Mar

2012: Nov / Oct / Sep / Jul / Jun / May / Mar / Feb / Jan

2011: Dec / Nov / Oct / Sep / Jul / Jun / Apr / Mar / Feb / Jan

2010: Dec / Nov / Oct / Sep / Aug / Jul / Jun / May / Apr / Mar / Feb / Jan

2009: Dec / Nov / Oct / Sep / Aug / Jul / Jun / May / Apr / Mar / Feb / Jan

2008: Dec / Nov / Oct / Sep / Aug / Jul / Jun / May / Apr / Mar / Feb / Jan

2007: Dec / Nov / Oct / Sep / Aug / Jul / Jun / May / Apr / Mar / Feb / Jan

2006: Dec / Nov / Oct / Sep


© 2006-2016 fixedpoint.jp