Exact arithmetic with quadratic irrationals

[H. S. Teoh via Digitalmars-d]

On Thu, Apr 20, 2017 at 02:01:20AM +0200, Timon Gehr via Digitalmars-d wrote:
[...]
> Yes, there is in fact a beautifully simple way to do better. :)
> 
> Assume we want to compute some power of x. With a single
> multiplication, we obtain x². Multiplying x² by itself, we obtain x⁴.
> Repeating this a few times, we get:
> 
> x, x², x⁴, x⁸, x¹⁶, x³², etc.
> 
> In general, we only need n operations to compute x^(2ⁿ).
> 
> To compute xʸ, it basically suffices to express y as a sum of powers
> of two (i.e., we write it in binary).
> 
> For example, 22 = 16 + 4 + 2, and x²² = x¹⁶·x⁴·x².
> 
> My last post includes an implementation of this algorithm. ;)

Ahh, so *that's* what it's all about. I figured that's what I was
missing. :-D  Thanks, I'll include this in QRat soon.


> In particular, this leads to multiple ways to compute the n-th
> Fibonacci number using O(log n) basic operations. (One way is to use
> your QRat type, but we can also use the matrix (1 1; 1 0).)

True, though I'm still jealous that with transcendental functions like
with floating-point, one could ostensibly compute that in O(1).


> > Another module I'm thinking about is an extension of QRat that
> > allows you to mix different radicals in the same expression. For
> > example, (√3+√5)/√7 and so forth. ...
> > 
> 
> That would certainly be nice. Note that QRat is basically already
> there for different quadratic radicals, the only reason it does not
> work already is that we cannot use a QRat as the base field instead of
> ℚ (because ℚ is hardcoded).

Oh?  I didn't try it myself, but if QRat itself passes isArithmeticType,
I'd venture to say QRat!(n, QRat!m) ought to work... There are some
hidden assumptions about properties of the rationals, though, but I
surmise none that couldn't be replaced by prerequisites about the
relative linear dependence of the mixed radicals over Q.

What I had in mind, though, was a more direct approach that perhaps may
reduce the total number of operations, since if the code is aware that
multiple radicals are involved, it could potentially factor out some
commonalities to minimize recomputations.

Also, the current implementation of QRat fixes the radical at
compile-time; I wanted to see if I could dynamically handle arbitrary
radicals at runtime. It would have to be restricted by only allowing
operations between two QRats of the same extension, of course, but if
the code could handle arbitrary extensions dynamically, then that
restriction could be lifted and we could (potentially, anyway) support
arbitrary combinations of expressions involving radicals. That would be
far more useful than QRat, for some of the things I'd like to use it
for.


> This is the relevant concept from algebra:
> https://en.wikipedia.org/wiki/Splitting_field
> 
> 
> All your conjectures are true, except the last one. (Galois theory is
> not an obstacle, because here, we only need to consider splitting
> fields of particularly simple polynomials that are solvable in
> radicals.)

That's nice to know. But I suppose Galois theory *would* become an
obstacle if I wanted to implement, for example, Q(x) for an arbitrary
algebraic x?


> You can even mix radicals of different degrees.

Yes, I've thought about that before. So it should be possible to
represent Q(r1,r2,...rn) using deg(r1)*deg(r2)*...*deg(rn)+1
coefficients?


> To get the formula for multiplicative inverses, one possible algorithm is:
> https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Polynomial_extended_Euclidean_algorithm
[...]

Thanks, will look into this at some point. :-)


T

-- 
Some ideas are so stupid that only intellectuals could believe them. -- George Orwell