maths.binary_exponentiation
===========================

.. py:module:: maths.binary_exponentiation

.. autoapi-nested-parse::

   Binary Exponentiation

   This is a method to find a^b in O(log b) time complexity and is one of the most commonly
   used methods of exponentiation. The method is also useful for modular exponentiation,
   when the solution to (a^b) % c is required.

   To calculate a^b:
   - If b is even, then a^b = (a * a)^(b / 2)
   - If b is odd, then a^b = a * a^(b - 1)
   Repeat until b = 1 or b = 0

   For modular exponentiation, we use the fact that (a * b) % c = ((a % c) * (b % c)) % c



Attributes
----------

.. autoapisummary::

   maths.binary_exponentiation.a


Functions
---------

.. autoapisummary::

   maths.binary_exponentiation.binary_exp_iterative
   maths.binary_exponentiation.binary_exp_mod_iterative
   maths.binary_exponentiation.binary_exp_mod_recursive
   maths.binary_exponentiation.binary_exp_recursive


Module Contents
---------------

.. py:function:: binary_exp_iterative(base: float, exponent: int) -> float

   Computes a^b iteratively, where a is the base and b is the exponent

   >>> binary_exp_iterative(3, 5)
   243
   >>> binary_exp_iterative(11, 13)
   34522712143931
   >>> binary_exp_iterative(-1, 3)
   -1
   >>> binary_exp_iterative(0, 5)
   0
   >>> binary_exp_iterative(3, 1)
   3
   >>> binary_exp_iterative(3, 0)
   1
   >>> binary_exp_iterative(1.5, 4)
   5.0625
   >>> binary_exp_iterative(3, -1)
   Traceback (most recent call last):
       ...
   ValueError: Exponent must be a non-negative integer


.. py:function:: binary_exp_mod_iterative(base: float, exponent: int, modulus: int) -> float

   Computes a^b % c iteratively, where a is the base, b is the exponent, and c is the
   modulus

   >>> binary_exp_mod_iterative(3, 4, 5)
   1
   >>> binary_exp_mod_iterative(11, 13, 7)
   4
   >>> binary_exp_mod_iterative(1.5, 4, 3)
   2.0625
   >>> binary_exp_mod_iterative(7, -1, 10)
   Traceback (most recent call last):
       ...
   ValueError: Exponent must be a non-negative integer
   >>> binary_exp_mod_iterative(7, 13, 0)
   Traceback (most recent call last):
       ...
   ValueError: Modulus must be a positive integer


.. py:function:: binary_exp_mod_recursive(base: float, exponent: int, modulus: int) -> float

   Computes a^b % c recursively, where a is the base, b is the exponent, and c is the
   modulus

   >>> binary_exp_mod_recursive(3, 4, 5)
   1
   >>> binary_exp_mod_recursive(11, 13, 7)
   4
   >>> binary_exp_mod_recursive(1.5, 4, 3)
   2.0625
   >>> binary_exp_mod_recursive(7, -1, 10)
   Traceback (most recent call last):
       ...
   ValueError: Exponent must be a non-negative integer
   >>> binary_exp_mod_recursive(7, 13, 0)
   Traceback (most recent call last):
       ...
   ValueError: Modulus must be a positive integer


.. py:function:: binary_exp_recursive(base: float, exponent: int) -> float

   Computes a^b recursively, where a is the base and b is the exponent

   >>> binary_exp_recursive(3, 5)
   243
   >>> binary_exp_recursive(11, 13)
   34522712143931
   >>> binary_exp_recursive(-1, 3)
   -1
   >>> binary_exp_recursive(0, 5)
   0
   >>> binary_exp_recursive(3, 1)
   3
   >>> binary_exp_recursive(3, 0)
   1
   >>> binary_exp_recursive(1.5, 4)
   5.0625
   >>> binary_exp_recursive(3, -1)
   Traceback (most recent call last):
       ...
   ValueError: Exponent must be a non-negative integer


.. py:data:: a
   :value: 1269380576