On Evaluation of Powers (Q4024152)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 108717
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On Evaluation of Powers |
scientific article; zbMATH DE number 108717 |
Statements
On Evaluation of Powers (English)
0 references
25 February 1993
0 references
efficiency
0 references
calculation of \(n\)th power
0 references
least number of multiplications
0 references
0 references
0 references
0 references
Let \(f(n)\) be the least number of multiplications needed to calculate \(x^ n\). It is shown that \([\log_ 2 n]+1\leq f(n)\leq 2[\log_ 2 n]\), if \(n\) is not a power of 2. If \(n=2^ k\) then \(f(n)=k\). The upper bound can be lowered if the factorization of \(n\) is known.
0 references
