On 2013-08-20 06:51:01 +0200, Ulrich Kulisch wrote:
Dear Bill,
it may well be that CA and the EDP are not well suited for solving
problems which in general are NP-hard.
It is not related to NP-hard problems.
The usefulness and necessity of CA and the EDP for other problems, however,
have repeatedly been shown in the literature. As examples I just refer here
to three articles in the volume:
U. Kulisch and H. J. Stetter: Scientific Computation with Automatic Result
Verification, Computing Supplementum 6, Springer 1988.
[1] Th. Ottmann, G. Thiemt, Ch. Ullrich: On Arithmetical Problems of
Geometric Algorithms in the Plane.
[2] R. Lohner: Precise Evaluation of Polymomials in Several Variables.
[3] H. C. Fischer, G. Schumacher, R. Haggenmueller: Evaluation of Arithmetic
Expressions with Guaranteed High Accuracy.
I don't have a full access to these articles, but they seem to
represent numbers accurately by a sum of FP numbers (as in FP
expansions) and use the EDP as a tool to perform a product of two
such numbers. But as I've already said, this can be interesting
only if CA is implemented in hardware. Otherwise there are better
methods. And currently there are no signs that processor vendors
may wish to provide processors with CA.
Moreover, even though CA may be interesting[*] compared to a basic
software implementation, other tools could be used. Basic operations
for FP expansions could also be designed in hardware, with the
advantage that they would individually take much fewer resources,
and thus parallelization would be easier.
[*] This also depends on how efficiently FP numbers can be extracted
from the long accumulator.
Another point is that FP expansions can be more efficient than
conventional multiple precision because in practice, they benefit
from good FP hardware, and inputs/outputs are also FP numbers. But
if you accept some forms of multiple-precision hardware (such as a
long accumulator, though this is rather limited), then conventional
multiple precision may be more efficient if partly done in hardware
(and I suppose that it could also be useful for cryptography).
So, in short, saying that CA is useful is just like saying that any
new feature is useful. And I doubt that CA is one of the best.