Line data    Source code

       1             : // Author(s): Jan Friso Groote
       2             : // Copyright: see the accompanying file COPYING or copy at
       3             : // https://github.com/mCRL2org/mCRL2/blob/master/COPYING
       4             : //
       5             : // Distributed under the Boost Software License, Version 1.0.
       6             : // (See accompanying file LICENSE_1_0.txt or copy at
       7             : // http://www.boost.org/LICENSE_1_0.txt)
       8             : //
       9             : /// \file general_utilities.h
      10             : /// \brief Some general mathematical functions not provided by standard libraries.
      11             : 
      12             : #ifndef MCRL2_UTILITIES_MATH_H
      13             : #define MCRL2_UTILITIES_MATH_H
      14             : 
      15             : #include <cassert>
      16             : #include <cmath>
      17             : #include <cstdlib>
      18             : 
      19             : namespace mcrl2
      20             : {
      21             : namespace utilities
      22             : {
      23             : 
      24             : // Compute base 2 logarithm of n, by checking which is the leftmost
      25             : // bit that has been set.
      26             : 
      27             : inline
      28          65 : std::size_t ceil_log2(std::size_t n)
      29             : {
      30          65 :   assert(n>0);
      31          65 :   std::size_t result = 0;
      32         192 :   while(n != 0)
      33             :   {
      34         127 :     n = n >> 1;
      35         127 :     ++result;
      36             :   }
      37          65 :   return result;
      38             : }
      39             : 
      40             : // Calculate n^m for numbers n,m of type std::size_t
      41             : inline 
      42          63 : std::size_t power_size_t(const std::size_t n_in, const std::size_t m_in)
      43             : {
      44          63 :   std::size_t result=1;
      45          63 :   std::size_t n=n_in;
      46          63 :   std::size_t m=m_in;
      47         213 :   while (m>0)  // Invariant: result*n^m=n_in^m_in;
      48             :   {
      49         150 :     if (m % 2==1)
      50             :     {
      51          63 :       result=result*n;
      52             :     }
      53         150 :     n=n*n;
      54         150 :     m=m/2;
      55             :   }
      56          63 :   return result;
      57             : }
      58             : 
      59             : } // namespace utilities
      60             : } // namespace mcrl2
      61             : 
      62             : 
      63             : #endif // MCRL2_UTILITIES_MATH_H
      64             :