Re: Algorithm for denesting nested radicals

The original poster asked for efficient algorithms.

This raises the question: does the original poster have an inefficient
algorithm for the task?

If so, it would be good to see this algorithm. Then we can compare it
to other algorithms that do the same (or different!) thing.

If you have no algorithm, and no adequate specification for the task,
then it is hard to compare algorithms for efficiency or even adequacy.

There is a very simple way of computing with (purely numeric) radicals,
which is to evaluate them from the inside out, numerically, to high
precision. Do you need some other information not present in this kind
of computation?

You can even convert them back to radicals, given high enough
precision, sometimes.

RJF


Vladimir Bondarenko wrote:
................................................................

Simplifying Square Roots of Square Roots by Denesting
by David J. Jeffrey and Albert D. Rich

http://www.cybertester.com/data/denest.pdf

Abstract: We discuss why it is important to try to simplify the
square root of an expression containing other square roots, and
we give rules for doing this when it is possible. The square
root of an expression containing nth roots is also considered
briefly.

This article, in addition to treating a specific mathematical
topic, shows some of the steps that developers must take when
writing computer algebra systems.

................................................................

Could you give us some concrete examples you have problems with?


Sincerely,

Vladimir Bondarenko

VM and GEMM architect
Co-founder, CEO, Mathematical Director

http://www.cybertester.com/ Cyber Tester, LLC
http://maple.bug-list.org/ Maple Bugs Encyclopaedia
http://www.CAS-testing.org/ CAS Testing

................................................................


xyz91234@xxxxxxxxx wrote:
What algorithms are efficient for denesting nested radicals?
In "Simplification of Nested Radicals" by Susan Landau, is the
algorithm inefficient?
That method is not a general form. It cannot denest non-algebraic
functions such as radicals containing logarithms. Is there a method
that both works in general cases and its efficient, or do I have to
first expand some cases so it can denest by pattern matching?

Thanks

.

Relevant Pages

  • Re: square roots mod p.
    ... the algorithm in the "Handbook of Applied Cryptography" by Menezes, ... Legendre symbol of a mod p and found that a is a quadratic residue ... The expected running time of the ... r and -r are the two square roots of a mod p. ...
    (sci.math)
  • Re: Congruence based factoring algorithm, revised
    ... It's basically a disguised version of trial division. ... description of the algorithm. ... algorithm for computing modular square roots. ... his results are almost all wrong, but rather than mathematicians are ...
    (comp.theory)
  • Re: The factoring problem
    ... > multiplication is an algorithm invented by man. ... All known solutions for factoring ... square roots modulo pq. ... If you gave me the square roots of "x" modulo pq I could trivially ...
    (sci.crypt)
  • Re: Modular arithmetic question
    ... > solve this problem when the factorization of k is unknown (and k is ... algorithm for computing square roots mod p which ... If you could quickly compute the square roots of -1 mod F_n ... F_n as the sum of two squares. ...
    (sci.math)
  • Re: algebraic functions
    ... radicals is much more complicated than testing for 0/equality, ... which is a very particular case of denesting. ... must be an algorithm out there which decides equality for ... to do for equality with zero is to check whether the minimal ...
    (sci.math.research)