On Thu, Apr 20, 2017 at 09:11:56PM +0200, Timon Gehr via Digitalmars-d wrote:
> On 20.04.2017 20:29, H. S. Teoh via Digitalmars-d wrote:
[...]
> > Having said that, I haven't scrutinized the performance characteristics of QRat too carefully just yet -- there is probably room for optimization.
> > 
> 
> Gcd is the problem. [...]
[...]
> If I change the gcd computation in QRat (line 233) from
> 
> auto g = gcd(abs(a), abs(b), c);
> 
> to
> 
> auto g = gcd(abs(a), c, abs(b));
> 
> I get performance that is a lot closer to the matrix version and also beats the linear computation. (This is because if one of the operands is 1, gcd is cheap to compute.)

Fixed, thanks!


[...]
> > The +1 is for the denominator, assuming integer coefficients.  Since having 2^n rational coefficients is equivalent to having 2^n integer coefficients (which are half the size of rational coefficients, computer-representation-wise) + 1 denominator.  ...
> 
> Ah, I see. Personally, I'm more in the one denominator per coefficient camp.  :) I think having a designated ℚ type is cleaner, and it might even be more performant.

It's hard to say without profiling it, I think.  Having one denominator per coefficient does need more storage space, and you do have to separately reduce each rational coefficient to lowest terms per operation. I think some profiling is needed to know for sure.

Besides, Phobos is badly in need of a Rational type that's compatible with both native int types and BigInt. Maybe I should adapt some of the code in QRat for that purpose. :-D  (Since rationals, after all, are a subset of QRats.)


On Thu, Apr 20, 2017 at 09:25:19PM +0200, Timon Gehr via Digitalmars-d wrote:
> On 20.04.2017 21:18, Timon Gehr wrote:
> > On 20.04.2017 21:11, Timon Gehr wrote:
> > > > Update: QRat now supports ^^. :-) Integral exponents only, of course.  I also implemented negative exponents, because QRat supports division and the same algorithm can be easily reused for that purpose.  ...
> > > 
> > > Nice! :)
> > 
> > It does not work with BigInt-based QRats (T(1) does not work, as 1
> > does not implicitly convert to BigInt.)
> 
> I guess the best fix is to templatize the QRat constructor such that it accepts all argument types that can be used to construct the coefficients.

Fixed, thanks!


T

-- 
If the comments and the code disagree, it's likely that *both* are wrong. -- Christopher