JuliaLang/julia

Faster Rational-like type

オープン

#11,522 opened on 2015/06/01

 (47 件のコメント) (1 件のリアクション) (0 人の担当者)Julia (5,773 件のフォーク)batch import
help wantedmathsperformancerationals

Repository metrics

Stars
 (48,709 個のスター)
PR merge metrics
 (平均マージ 20d 6h) (30d で 157 merged PRs)

説明

Over in https://github.com/tlycken/Interpolations.jl/pull/36#issuecomment-106895591 and https://github.com/tlycken/Interpolations.jl/pull/37 it was discovered that doing computations with Rational is slow, because basically every usage calls gcd and div. The advantage of calling gcd and div is that it makes the type much less vulnerable to overflow, and that is a Good Thing. But as we discovered, certain computations may not need that kind of care, so there may be room for a faster variant. Switching to a stripped down variant provided an approximate 50-fold speed boost.

I suspect certain computations may demand an implementation that is as minimalistic as that Ratio type. There may also be an area of intermediate interest, where a Rational-like object is represented in terms of pre-factorized numbers, perhaps numerator and denominator each being a Dict{Int,Int} representing the base and power of the factors.

コントリビューターガイド