Exact arithmetic with quadratic irrationals

[H. S. Teoh via Digitalmars-d]

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