Exact arithmetic with quadratic irrationals

Timon Gehr via Digitalmars-d digitalmars-d at puremagic.com
Thu Apr 20 05:51:12 PDT 2017


On 20.04.2017 03:00, H. S. Teoh via Digitalmars-d wrote:
> 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. :)
>> ...
>
> 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).
> ...

BTW, you are right that with std.bigint, computation using a linear 
number of additions is actually faster for my example (100000th 
Fibonacci number). The asymptotic running time of the version with pow 
on QRats is lower though, so there ought to be a crossover point. (It is 
Θ(n^2) vs. O(n^log₂(3)·log(n)). std.bigint does not implement anything 
that is asymptotically faster than Karatsuba.)

For computations over field extensions of (small) finite fields, pow is 
a lot faster though.

>
>>> 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.
> ...

The issue is that gcd does not work on QRats. If QRat had two 
coefficients from an arbitrary (possibly ordered) field instead of 
encoding rationals explicitly, I think it would work.


> 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.
> ...

This is probably the case.

> 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.
> ...

What applications do you have in mind? Computational geometry?


>
>> 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?
> ...

All that the result about the quintic really says is that you will not, 
in general, be able to express x using field operations on radicals. It 
is still possible to compute the roots to arbitrary precision.
Computing the field operations in ℚ(x) will actually still be quite 
straightforward but you'd have to think about what to do with toString 
and opCmp. (Or more generally, you'd have to think about how to pick one 
of the roots of a given polynomial.)

>
>> 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?
> ...

Yes, at most, except you don't need "+1". (For each radical ri, you will 
at most need to pick a power between 0 to deg(ri)-1 to index into the 
coefficients.)







More information about the Digitalmars-d mailing list