1 // Copyright (c) 2008 Max-Planck-Institute Saarbruecken (Germany). 2 // All rights reserved. 3 // 4 // This file is part of CGAL (www.cgal.org) 5 // 6 // $URL: https://github.com/CGAL/cgal/blob/v5.3/Algebraic_foundations/include/CGAL/ipower.h $ 7 // $Id: ipower.h 0779373 2020-03-26T13:31:46+01:00 Sébastien Loriot 8 // SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-Commercial 9 // 10 // 11 // Author(s) : Michael Hemmer 12 // 13 // This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE 14 // WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. 15 // 16 // $URL: https://github.com/CGAL/cgal/blob/v5.3/Algebraic_foundations/include/CGAL/ipower.h $ 17 18 #ifndef CGAL_IPOWER_H 19 #define CGAL_IPOWER_H 20 21 #include <CGAL/assertions.h> 22 23 namespace CGAL { 24 25 template <typename NT> 26 inline ipower(const NT & base,int expn)27NT ipower(const NT& base, int expn) { 28 // compute base^expn using square-and-multiply 29 CGAL_precondition(expn >= 0); 30 31 // handle trivial cases efficiently 32 if (expn == 0) return NT(1); 33 if (expn == 1) return base; 34 35 // find the most significant non-zero bit of expn 36 int e = expn, msb = 0; 37 while (e >>= 1) msb++; 38 39 // computing base^expn by square-and-multiply 40 NT res = base; 41 int b = 1<<msb; 42 while (b >>= 1) { // is there another bit right of what we saw so far? 43 res *= res; 44 if (expn & b) res *= base; 45 } 46 return res; 47 } 48 49 template <typename NT> 50 inline ipower(const NT & base,long expn)51NT ipower(const NT& base, long expn) { 52 // compute base^expn using square-and-multiply 53 CGAL_precondition(expn >= 0); 54 55 // handle trivial cases efficiently 56 if (expn == 0) return NT(1); 57 if (expn == 1) return base; 58 59 // find the most significant non-zero bit of expn 60 long e = expn, msb = 0; 61 while (e >>= 1) msb++; 62 63 // computing base^expn by square-and-multiply 64 NT res = base; 65 long b = 1L<<msb; 66 while (b >>= 1) { // is there another bit right of what we saw so far? 67 res *= res; 68 if (expn & b) res *= base; 69 } 70 return res; 71 } 72 73 } //namespace CGAL 74 75 #endif // CGAL_IPOWER_H 76