Roots of unity

Bob McElrath mcelrath at
Sun Jan 20 18:14:28 CET 2002

Richard B. Kreckel [kreckel at] wrote:
> On Sun, 20 Jan 2002, Bob McElrath wrote:
> [...]
> > What I see as needed in order to write some simplification routines are methods
> > for the ex class like there are in the numeric class:
> >     is_real, is_integer, operator<, etc...
> > And an assume() functionality to create symbols that are reals, integers, etc.
> The reason this has not been done is that we have absolutely no idea how
> to make it consistent.

Really?  Maybe I haven't thought about it as much as you...

But it seems you'd need methods:
for every function (sqrt, sum, sin, pow, ...), which could then query their
arguments in the appropriate manner to determine the final result.

> The sign of -1/2-sqrt(2/9) should be straightforwardly determinable.  But
> what keeps you then from trying to determine the sign of nested roots?  I
> believe that I read somewhere that algorithms which determine the sign of
> a general expression with n roots take time exponential in n, although
> sums seem to be easier.  This is still an active field of research.

The above naive algorithm looks O(n) in the number of functions to me.  Maybe
I'm missing something...

By nested root you mean something like:

-- Bob

Bob McElrath (rsmcelrath at 
Univ. of Wisconsin at Madison, Department of Physics
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 240 bytes
Desc: not available
Url :

More information about the GiNaC-list mailing list