📄 power.html
字号:
<HTML><!-- -- Copyright (c) 1996-1999 -- Silicon Graphics Computer Systems, Inc. -- -- Permission to use, copy, modify, distribute and sell this software -- and its documentation for any purpose is hereby granted without fee, -- provided that the above copyright notice appears in all copies and -- that both that copyright notice and this permission notice appear -- in supporting documentation. Silicon Graphics makes no -- representations about the suitability of this software for any -- purpose. It is provided "as is" without express or implied warranty. -- -- Copyright (c) 1994 -- Hewlett-Packard Company -- -- Permission to use, copy, modify, distribute and sell this software -- and its documentation for any purpose is hereby granted without fee, -- provided that the above copyright notice appears in all copies and -- that both that copyright notice and this permission notice appear -- in supporting documentation. Hewlett-Packard Company makes no -- representations about the suitability of this software for any -- purpose. It is provided "as is" without express or implied warranty. -- --><Head><Title>power</Title><!-- Generated by htmldoc --></HEAD><BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" ALINK="#ff0000"> <IMG SRC="CorpID.gif" ALT="SGI" HEIGHT="43" WIDTH="151"> <!--end header--><BR Clear><H1>power</H1><Table CellPadding=0 CellSpacing=0 width=100%><TR><TD Align=left><Img src = "algorithms.gif" Alt="" WIDTH = "194" HEIGHT = "38" ></TD><TD Align=right><Img src = "function.gif" Alt="" WIDTH = "194" HEIGHT = "38" ></TD></TR><TR><TD Align=left VAlign=top><b>Category</b>: algorithms</TD><TD Align=right VAlign=top><b>Component type</b>: function</TD></TR></Table><h3>Prototype</h3><tt>Power</tt> is an overloaded name; there are actually two <tt>power</tt>functions.<pre>template <class T, class Integer>inline T power(T x, Integer n);template <class T, class Integer, class <A href="MonoidOperation.html">MonoidOperation</A>>T power(T x, Integer n, MonoidOperation op);</pre> <h3>Description</h3><tt>Power</tt> is generalized exponentiation: it raises the value <tt>x</tt>to the power <tt>n</tt>, where <tt>n</tt> is a non-negative integer. <P>The first version of <tt>power</tt>returns <tt>x</tt> raised to the <tt>n</tt>th power; that is, it returns<tt>x * x ... * x</tt>, where <tt>x</tt> is repeated <tt>n</tt> times. <A href="#1">[1]</A> If<tt>n == 0</tt>, then it returns <tt><A href="MonoidOperation.html">identity_element</A>(<A href="times.html">multiplies</A><T>())</tt>.<P>The second version of <tt>power</tt> is just like the first exceptthat it uses an arbitrary <A href="MonoidOperation.html">Monoid Operation</A> instead of <tt><A href="times.html">multiplies</A><T></tt>, returning <tt><A href="MonoidOperation.html">identity_element</A>(op)</tt>when <tt>n == 0</tt>.<P><b>Important note</b>: <tt>power</tt> does not assume that multiplication iscommutative, but it does rely crucially on the fact thatmultiplication is associative. If you have defined <tt>*</tt> or<tt><A href="MonoidOperation.html">MonoidOperation</A></tt> to be a non-associative operation, then <tt>power</tt><i>will give you the wrong answer</i>. <A href="#2">[2]</A><h3>Definition</h3>Defined in the standard header <A href="numeric">numeric</A>, and in the nonstandardbackward-compatibility header <A href="algo.h">algo.h</A>. This function is an SGIextension; it is not part of the C++ standard.<h3>Requirements on types</h3>For the first version:<UL><LI><tt><A href="times.html">multiplies</A><T></tt> is a model of <A href="MonoidOperation.html">Monoid Operation</A>.<LI><tt>Integer</tt> is an integral type.</UL>For the second version:<UL><LI><tt>MonoidOperation</tt> is a model of <A href="MonoidOperation.html">Monoid Operation</A>.<LI><tt>T</tt> is <tt>MonoidOperation</tt>'s argument type.<LI><tt>n</tt> is an integral type.</UL><h3>Preconditions</h3><UL><LI><tt>n >= 0</tt>.</UL><h3>Complexity</h3>The number of multiplications (or, in the case of the second version,the number of applications of <tt>MonoidOperation</tt>) is <tt>lg(n) + nu(n)</tt>where <tt>lg</tt> is the base 2 logarithm and <tt>nu(n)</tt> is the number of <tt>1</tt>s in the binary representation of <tt>n</tt>. <A href="#3">[3]</A><h3>Example</h3><pre>int main() { cout << "2 ** 30 = " << power(2, 30) << endl;}</pre><h3>Notes</h3><P><A name="1">[1]</A>This is a conceptual description of what <tt>power</tt>'s return value is; it is not how <tt>power</tt> is actually implemented. If <tt>power</tt>were implemented that way then it would require <tt>n-1</tt> multiplications,which would be grossly inefficient. <tt>Power</tt> is implemented usingthe "Russian peasant algorithm", which requires only <tt>O(log n)</tt>multiplications.See section 4.6.3 of Knuth (D. E. Knuth, <i>The Art of ComputerProgramming. Volume 2: Seminumerical Algorithms</i>, Addison-Wesley, 1981) for a discussion.<P><A name="2">[2]</A>See the <A href="MonoidOperation.html">Monoid Operation</A> requirements for a discussion of associativity.<P><A name="3">[3]</A>This is in fact not the minimum possible number of multiplications:it is possible to compute the fifteenth power of <tt>x</tt> using onlyfive multiplications, but <tt>power(x, 15)</tt> uses six. <h3>See also</h3><A href="MonoidOperation.html">Monoid Operation</A>, <tt><A href="times.html">multiplies</A></tt>, <tt><A href="plus.html">plus</A></tt><!--start footer--> <HR SIZE="6"><A href="http://www.sgi.com/"><IMG SRC="surf.gif" HEIGHT="54" WIDTH="54" ALT="[Silicon Surf]"></A><A HREF="index.html"><IMG SRC="stl_home.gif" HEIGHT="54" WIDTH="54" ALT="[STL Home]"></A><BR><FONT SIZE="-2"><A href="http://www.sgi.com/Misc/sgi_info.html" TARGET="_top">Copyright © 1999 Silicon Graphics, Inc.</A> All Rights Reserved.</FONT><FONT SIZE="-3"><a href="http://www.sgi.com/Misc/external.list.html" TARGET="_top">TrademarkInformation</A></FONT><P></BODY></HTML> ⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -