Roots of Complex[Algebraic]

[Bryan Wilkinson]

I would like to compute the real roots of a cubic polynomial. I require exact computation so I am mainly using the Algebraic type. Even to find only the real roots, I seem to need to take roots of complex numbers, so I briefly need to switch to using the Complex[Algebraic] type. However, I am getting type errors when trying to take the square root of a Complex[Algebraic].

As expected:

sqrt(Real(4)) // 2

sqrt(Real(-4)) // runtime exception

sqrt(Algebraic(4)) // 2.00000000

sqrt(Algebraic(-4)) // runtime exception

sqrt(Complex(Real(4))) // (2 + 0i)

sqrt(Complex(Real(-4))) // (0 + 2i)

Unexpected:

sqrt(Complex(Algebraic(4))) // type errors

sqrt(Complex(Algebraic(-4))) // type errors

Here are the type errors:

not enough arguments for method sqrt: (implicit ev: spire.algebra.NRoot[spire.math.Complex[spire.math.Algebraic]])spire.math.Complex[spire.math.Algebraic]. Unspecified value parameter ev.

could not find implicit value for parameter ev: spire.algebra.NRoot[spire.math.Complex[spire.math.Algebraic]]

Is this a bug or am I doing something wrong?

Thanks,

- Bryan

[Tom Switzer]

I think the problem is that, currently, NRoot[Complex[A]] requires a Trig[A], and Trig[Algebraic] doesn't exist. I don't know enough about Complex to know whether Trig is a hard requirement. For instance, Complex#sqrt doesn't require a trig, but Complex#nroot does. So, while Complex(Algebraic(4)).sqrt will work, Complex(Algebraic(4)).nroot(2) won't.

A quick skim through the code make me feel that Trig may not be needed, so I'll try removing it as a requirement from nroot and pow and see what happens and report back.

[Tom Switzer]

Hrmm... so the sad news is that while sqrt and nroot don't actually require Trig, pow does. My initial thought is that fpow doesn't really belong in NRoot for reasons like this (we can only promise implementations up to Rationals), but it's a fairly major change to remove it. Erik, any thoughts? How terrible is it to move fpow out to Trig or some such? Or do we just leave things as-is?

[Erik Osheim]

Here is my take on this:

1. It would be nice if you didn't need a Trig[A] instance to do most
interesting things with Complex[A].

2. However, to do anything with complex numbers in polar form you do
need to use Trig[A] methods to go to cartesian form.

3. Many of the most natural implementations of pow/fpow/nroot involve
the polar form of complex numbers.

I haven't given a lot of thought to how to correct implement things
like: c^(1/3) or c^(17/16) just using cartesian coordinates. I'm
definitely open a new implementation, but I'd want to see what the
trade-off was before committing to it.

Does this all make sense? In some ways it's just an implementation
detail, but it's one that is very useful.

-- Erik

[Bryan Wilkinson]

I asked over at the math stack exchange about avoiding trigonometric functions and it seems that it is impossible even for the cube root.

http://math.stackexchange.com/questions/963438/cube-root-of-complex-number-without-trigonometric-functions/

- Bryan

[Tom Switzer]

OK - I think that settles it then! Note that Algebraic can support (real) root-finding, though it isn't implemented. We should add an issue.

[Erik Osheim]

I'm open to redesigning how NRoot[A] works. For example, I could
imagine a restricted Sqrt[A] class that NRoot[A] extends. I could also
image redesigning how fpow works (for example, taking a Rational or
Double instead of an A).

But yeah, it seems like Complex[A] and Quaternion[A] will continue
requiring Trig[A] for nroot and such.

Thanks for asking on stackexchange -- I didn't know if it was possible
to avoid trig functions or not (though obviously I didn't know how).

-- Erik