JuliaLang/julia

Faster Rational-like type

开放

#11,522 创建于 2015年6月1日

 (47 条评论) (1 个反应) (0 位负责人)Julia (5,773 个派生)batch import
help wantedmathsperformancerationals

仓库指标

星标
 (48,709 个星标)
PR 合并指标
 (平均合并 20天 6小时) (30 天内合并 157 个 PR)

描述

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.

贡献者指南