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 = 2.0 * math.ceil(wig / 2.0)
  58     fwig = 2.0 * math.ceil(wig * ROUNDING_CONSTANT / 2.0)
  59     if wig <= 2.0 or cwig != fwig:
  60         # Avoid too uneven splits.
  61         return fallback_width
  62     coefficient = cwig / 2
  63     new_width = multiply_relative_width(goal_width, coefficient)
  64     return new_width
  65
  66 def step_down(current_bound, relative_width):
  67     """Return rate of logarithmic width below.
  68
  69     :param current_bound: The current target transmit rate to move [pps].
  70     :param relative_width: The base relative width to use.
  71     :type current_bound: float
  72     :type relative_width: float
  73     :returns: Transmit rate smaller by relative width [pps].
  74     :rtype: float
  75     """
  76     return current_bound * (1.0 - relative_width)
  77
  78 def step_up(current_bound, relative_width):
  79     """Return rate of logarithmic width above.
  80
  81     :param current_bound: The current target transmit rate to move [pps].
  82     :param relative_width: The base relative width to use.
  83     :type current_bound: float
  84     :type relative_width: float
  85     :returns: Transmit rate larger by logarithmically double width [pps].
  86     :rtype: float
  87     """
  88     return current_bound / (1.0 - relative_width)
  89
  90 def multiple_step_down(current_bound, relative_width, coefficient):
  91     """Return rate of multiplied logarithmic width below.
  92
  93     The multiplication happens in logarithmic space,
  94     so the resulting applied relative width is always less than 1.
  95
  96     :param relative_width: The base relative width to double.
  97     :param current_bound: The current target transmit rate to move [pps].
  98     :param coefficient: Multiply by this in logarithmic space.
  99     :type relative_width: float
 100     :type current_bound: float
 101     :type coefficient: float
 102     :returns: Transmit rate smaller by logarithmically multiplied width [pps].
 103     :rtype: float
 104     """
 105     new_width = multiply_relative_width(relative_width, coefficient)
 106     return step_down(current_bound, new_width)
 107
 108 def multiple_step_up(current_bound, relative_width, coefficient):
 109     """Return rate of double logarithmic width above.
 110
 111     The multiplication happens in logarithmic space,
 112     so the resulting applied relative width is always less than 1.
 113
 114     :param current_bound: The current target transmit rate to move [pps].
 115     :param relative_width: The base relative width to double.
 116     :param coefficient: Multiply by this in logarithmic space.
 117     :type current_bound: float
 118     :type relative_width: float
 119     :type coefficient: float
 120     :returns: Transmit rate larger by logarithmically multiplied width [pps].
 121     :rtype: float
 122     """
 123     new_width = multiply_relative_width(relative_width, coefficient)
 124     return step_up(current_bound, new_width)
 125
 126 def half_step_up(current_bound, relative_width, goal_width):
 127     """Return rate of half logarithmic width above.
 128
 129     :param relative_width: The base relative width to halve.
 130     :param current_bound: The current target transmit rate to move [pps].
 131     :type relative_width: float
 132     :type current_bound: float
 133     :returns: Transmit rate larger by logarithmically half width [pps].
 134     :rtype: float
 135     """
 136     new_width = halve_relative_width(relative_width, goal_width)
 137     return step_up(current_bound, new_width)