Pogovor:Naloga: program Splošna potenca

Iz MaFiRaWiki

Če jaz tole prav razumem, je treba najti najkrajši "addition chain", kar pa je NP-težek problem in kot tak ni rešljiv z DP??? NinoBasic

Najbrž bi bilo dobro poiskati ustrezno zunanjo referenco. TomazPisanski 00:11, 6 julij 2007 (CEST)

Glej: http://en.wikipedia.org/wiki/Addition-chain_exponentiation

In mathematics and computer science, optimal addition-chain exponentiation is a method of exponentiation by positive integer powers that requires a minimal number of multiplications. It works by creating a minimal-length addition chain that generates the desired exponent. Each exponentiation in the chain can be evaluated by multiplying two of the earlier exponentiation results. More generally, addition-chain exponentiation may also refer to exponentiation by sub-optimal addition chains constructed by a variety of algorithms (since an optimal addition chain is very difficult to find).

The optimal addition-chain algorithm requires fewer multiplications than binary exponentiation for large exponents. On the other hand, the addition-chain method is much more complicated, since the determination of an optimal addition chain for a given exponent is an NP-hard problem. Even given an optimal chain, addition-chain exponentiation requires more memory than the binary method, because it must potentially store many previous exponents from the chain simultaneously. In practice, therefore, optimal addition-chain exponentiation is primarily used for small fixed exponents for which the optimal chain can be precomputed and is not too large.

However, there are also several methods to approximate an optimal addition chain, and which often require fewer multiplications than binary exponentiation. Indeed, binary exponentiation itself is a suboptimal addition-chain algorithm. The best algorithm choice depends on the context (such as the relative cost of the multiplication and the number of times a given exponent is re-used). See Gordon (1998) for a survey.

Note that the problem of finding the optimal addition chain cannot be solved by dynamic programming, because it does not satisfy the assumption of optimal substructure. That is, it is not sufficient to decompose the power into smaller powers, each of which is computed optimally, since the addition chains for the smaller powers must be related (to share computations).

--NinoBasic 14:01, 8 julij 2007 (CEST)

Osebna orodja