Exact arithmetic with quadratic irrationals

[H. S. Teoh via Digitalmars-d]

On Wed, Apr 19, 2017 at 10:47:04PM +0200, Timon Gehr via Digitalmars-d wrote:
> On 19.04.2017 21:32, H. S. Teoh via Digitalmars-d wrote:
> > I alluded to this in D.learn some time ago, and finally decided to
> > take the dip and actually write the code. So here it is: exact
> > arithmetic with numbers of the form (a+b√r)/c where a, b, c are
> > integers, c!=0, and r is a (fixed) square-free integer.
> > 
> > Code:	https://github.com/quickfur/qrat
> > 
> > ...
> 
> Nice. :)
> 
> Some suggestions:
> 
> - You might want to support ^^ (it is useful for examples like the one
> below).

I would, except that I doubt it would perform any better than an actual
recursive or iterative algorithm for computing Fibonacci sequences,
because I don't know of any simple way to exponentiate a quadratic
rational using only integer arithmetic other than repeated
multiplication.  (For all I know, it may perform even worse, because
multiplying n quadratic rationals involves a lot more than just summing
n+1 integers as in an iterative implementation of Fibonacci.)

Hmm, come to think of it, I *could* expand the numerator using the
binomial theorem, treating (a+b√r) as a binomial (a+bx) where x=√r, and
folding even powers into the integral part (since x^2 = r, so x^(2k) =
r^k). The denominator could be exponentiated using plain ole integer
exponentiation.  Then it's just a matter of summing coefficients.

But it still seems to be about the same amount of work as (or more than)
summing n+1 integers in an iterative implementation of Fibonacci.  Am I
missing something?


> - constructor parameter _b should have a default value of 0.

Good point, done.


> - formatting should special case b==-1 like it special cases b==1.

Done, good catch!


>   (also: as you are using Unicode anyway, you could also use · instead
>   of *.  Another cute thing to do is to add a vinculum.)

Well, I would, but it gets a bit too fancy for my tastes and may not
render well on all displays. But I'll put it on my list of things to
consider.

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.  I have discovered algorithms that, given n
distinct radicals, allow a closed-form expression with 2^n coefficients
(+1 denominator), closed under field operations.  The only trouble in
this case is that reciprocating such things will be very slow, as will
comparisons, and both have a high chance of overflow (so BigInt is
probably a necessity).  And 2^n+1 coefficients for n radicals quickly
gets expensive space-wise as n increases.

Yesterday I also discovered an algorithm for expressing the reciprocal
of numbers of the form:

	(a + b∛r + c∛r^2)/d

in the same form. I.e., for rewriting:

	d/(a + b∛r + c∛r^2)

in the first form.  Which means it's possible to implement a QRat-like
representation for cubic rationals.  (The actual computation is rather
expensive, as it involves quite a lot of multiplications, squaring, and
cubing. But it's *possible*.)  I'm still trying to verify the
correctness of the formula I obtained, since while checking a concrete
example last night I discovered a possible error.

If this works out, I might consider 4th roots as well -- though I'm
expecting that might be near the limit of the usefulness of these
representations, since the complexity becomes so great that symbolic
manipulation like in Mathematica may turn out to be more feasible after
all.  But it may be of some theoretical interest whether such
representations are possible, even if they are ultimately impractical. A
particularly interesting question is whether such representations exist
for *all* algebraic numbers (of bounded degree).

Currently I have a conjecture that given a rational extension of n
radicals of degree k, field closure can be achieved with a
representation of k^n+1 coefficients. But it's still too early to say
whether algorithms exist for inverting radicals of degree k for large k
-- I have a creeping suspicion that perhaps somewhere around k=5 or k=6
the unsolvability of the general quintic may raise its ugly head and
prevent further progress.


T

-- 
INTEL = Only half of "intelligence".