resources/libraries/python/MLRsearch/WidthArithmetics.py

   1 # Copyright (c) 2021 Cisco and/or its affiliates.
   2 # Licensed under the Apache License, Version 2.0 (the "License");
   3 # you may not use this file except in compliance with the License.
   4 # You may obtain a copy of the License at:
   5 #
   6 #     http://www.apache.org/licenses/LICENSE-2.0
   7 #
   8 # Unless required by applicable law or agreed to in writing, software
   9 # distributed under the License is distributed on an "AS IS" BASIS,
  10 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  11 # See the License for the specific language governing permissions and
  12 # limitations under the License.
  13
  14 """Module defining utility functions for manipulating intervals."""
  15
  16 import math
  17
  18
  19 ROUNDING_CONSTANT = 0.999999
  20
  21 def multiply_relative_width(relative_width, coefficient):
  22     """Return relative width corresponding to multiplied logarithmic width.
  23
  24     The multiplication happens in logarithmic space,
  25     so the resulting relative width is always less than 1.
  26
  27     :param relative_width: The base relative width to multiply.
  28     :param coefficient: Multiply by this in logarithmic space.
  29     :type relative_width: float
  30     :type coefficient: float
  31     :returns: The relative width of multiplied logarithmic size.
  32     :rtype: float
  33     """
  34     old_log_width = math.log(1.0 - relative_width)
  35     # Slight decrease to prevent rounding errors from prolonging the search.
  36     # TODO: Make the nines configurable.
  37     new_log_width = old_log_width * coefficient * ROUNDING_CONSTANT
  38     return 1.0 - math.exp(new_log_width)
  39
  40 def halve_relative_width(relative_width, goal_width):
  41     """Return relative width corresponding to half logarithmic width.
  42
  43     The logic attempts to save some halvings in future by performing
  44     uneven split. If rounding error risk is detected,
  45     even split is used.
  46
  47     :param relative_width: The base relative width to halve.
  48     :param goal_width: Width goal for final phase.
  49     :type relative_width: float
  50     :type goal_width: float
  51     :returns: The relative width of half logarithmic size.
  52     :rtype: float
  53     """
  54     fallback_width = 1.0 - math.sqrt(1.0 - relative_width)
  55     # Wig means Width In Goals.
  56     wig = math.log(1.0 - relative_width) / math.log(1.0 - goal_width)
  57     cwig = math.ceil(wig)
  58     if wig <= 2.0 or cwig != math.ceil(wig * ROUNDING_CONSTANT):
  59         return fallback_width
  60     coefficient = cwig // 2
  61     new_width = multiply_relative_width(goal_width, coefficient)
  62     return new_width
  63
  64 def step_down(current_bound, relative_width):
  65     """Return rate of logarithmic width below.
  66
  67     :param current_bound: The current target transmit rate to move [pps].
  68     :param relative_width: The base relative width to use.
  69     :type current_bound: float
  70     :type relative_width: float
  71     :returns: Transmit rate smaller by relative width [pps].
  72     :rtype: float
  73     """
  74     return current_bound * (1.0 - relative_width)
  75
  76 def step_up(current_bound, relative_width):
  77     """Return rate of logarithmic width above.
  78
  79     :param current_bound: The current target transmit rate to move [pps].
  80     :param relative_width: The base relative width to use.
  81     :type current_bound: float
  82     :type relative_width: float
  83     :returns: Transmit rate larger by logarithmically double width [pps].
  84     :rtype: float
  85     """
  86     return current_bound / (1.0 - relative_width)
  87
  88 def multiple_step_down(current_bound, relative_width, coefficient):
  89     """Return rate of multiplied logarithmic width below.
  90
  91     The multiplication happens in logarithmic space,
  92     so the resulting applied relative width is always less than 1.
  93
  94     :param relative_width: The base relative width to double.
  95     :param current_bound: The current target transmit rate to move [pps].
  96     :param coefficient: Multiply by this in logarithmic space.
  97     :type relative_width: float
  98     :type current_bound: float
  99     :type coefficient: float
 100     :returns: Transmit rate smaller by logarithmically multiplied width [pps].
 101     :rtype: float
 102     """
 103     new_width = multiply_relative_width(relative_width, coefficient)
 104     return step_down(current_bound, new_width)
 105
 106 def multiple_step_up(current_bound, relative_width, coefficient):
 107     """Return rate of double logarithmic width above.
 108
 109     The multiplication happens in logarithmic space,
 110     so the resulting applied relative width is always less than 1.
 111
 112     :param current_bound: The current target transmit rate to move [pps].
 113     :param relative_width: The base relative width to double.
 114     :param coefficient: Multiply by this in logarithmic space.
 115     :type current_bound: float
 116     :type relative_width: float
 117     :type coefficient: float
 118     :returns: Transmit rate larger by logarithmically multiplied width [pps].
 119     :rtype: float
 120     """
 121     new_width = multiply_relative_width(relative_width, coefficient)
 122     return step_up(current_bound, new_width)
 123
 124 def half_step_up(current_bound, relative_width, goal_width):
 125     """Return rate of half logarithmic width above.
 126
 127     :param relative_width: The base relative width to halve.
 128     :param current_bound: The current target transmit rate to move [pps].
 129     :type relative_width: float
 130     :type current_bound: float
 131     :returns: Transmit rate larger by logarithmically half width [pps].
 132     :rtype: float
 133     """
 134     new_width = halve_relative_width(relative_width, goal_width)
 135     return step_up(current_bound, new_width)