Module grscheller.boring_math.integer_math

Library of functions and classes of an integer pure math nature.

# Copyright 2016-2023 Geoffrey R. Scheller
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

"""Library of functions and classes of an integer pure math nature."""

from __future__ import annotations

from typing import Callable, Iterator, Tuple
from grscheller.circular_array import CircularArray

__all__ = ['gcd', 'lcm', 'coprime', 'iSqrt', 'isSqr', 'primes', 'comb', 'fibonacci']

# Number Theory mathematical Functions.

def gcd(m: int, n: int) -> int:
    """Uses Euclidean algorithm to compute the gcd of two integers

    * takes two integers, returns `gcd > 0`
    * note that mathematically the gcd of `0` and `0` does not exist
    * `gcd(0, 0) = 1` a better choice than `math.gcd(0, 0) = 0`
    * `gcd(0, 0) = 1` eliminates `lcm` & `coprime` having to edge case test
    * `gcd(0, 0)` returning `1` instead of `0` more easily mathematically justified 
    """
    if 0 == m == n:
        return 1
    m, n = abs(m), abs(n)
    m, n = (m, n) if m > n else (n, m)
    while n > 0:
        m, n = n, m % n
    return m

def lcm(m: int, n: int) -> int:
    """Finds the least common multiple (lcm) of two integers.

    * takes two integers `m` and `n`
    * returns `lcm(m, n) > 0`
    """
    m //= gcd(m, n)
    return abs(m*n)

def coprime(m: int, n: int) -> Tuple(int, int):
    """Makes 2 integers coprime by dividing out their common factors.

    * returns `(0, 0)` when `n = m = 0`
    * returned coprimed values retain their original signs
    """
    coPrime = lambda mm, nn, common: (mm//common, nn//common)
    return coPrime(m, n, gcd(m, n))

def iSqrt(n: int) -> int:
    """Integer square root of a non-negative integer.

    * return the unique `m` such that `m*m <= n < (m+1)*(m+1)`
    * raises: ValueError if `n < 0`
    """
    if n < 0:
        msg = 'iSqrt(n): n must be non-negative'
        raise ValueError(msg)
    high = n
    low = 1
    while high > low:
        high = (high + low) // 2
        low = n // high
    return high

def isSqr(n: int) -> bool:
    """Returns true if integer argument is a perfect square"""
    return false if n < 0 else n == iSqrt(n)**2

def primes(start: int=2, end_before: int=100) -> Iterator:
    """Return a prime number iterator using the *Sieve of Eratosthenes* algorithm"""
    if start >= end_before or end_before < 3:
        return []
    if start < 2:
        start = 2

    sieve = [x for x in range(3, end_before, 2) if x % 3 != 0]
    stop = int(end_before**(0.5)) + 1
    front = -1
    for prime in sieve:
        front += 1
        if prime > stop:
            break
        for pot_prime in sieve[-1:front:-1]:
            if pot_prime % prime == 0:
                sieve.remove(pot_prime)

    if start <= 3 < end_before:  # We missed [2, 3] but
        sieve.insert(0, 3)       # saved about 60% for
    if start <= 2 < end_before:  # the initial storage
        sieve.insert(0, 2)       # space.

    # return sieve after trimming unwanted values
    return (x for x in sieve if x >= start)

# Combinatorics

def comb(n: int, m: int, targetTop: int=700, targetBot: int=5) -> int:
    """Implements `C(n,m)`, the number of combinations of `n` items taken `m`
    at a time, in a way that works efficiently for Python's arbitrary length
    integers.

    * default parameters geared to large values of `n` and `m`.
    * these defaults work reasonably well for smaller (human size) values
    * for inner loops with smaller values, use `targetTop = targetBot = 1`
    * or just use math.comb(n, m) instead
    * it is hoped pypy's JIT compiler will give better performance
    * raises `ValueError` if `n < 0` or `m < 0`
    """
    if n < 0 or m < 0:
        raise ValueError('for C(n, m) n and m must be a non-negavive ints')
    if n == m or m == 0:
        return 1
    elif m > n:
        return 0

    # using C(n, m) = C(n, n-m) to reduce number of factors in calculation
    if m > (n // 2):
        m = n - m

    # Prepare data structures
    tops = CircularArray(*range(n - m + 1, n + 1))
    bots = CircularArray(*range(1, m+1))

    # Compacting data structures makes algorithm work better for larger values
    size = len(tops)
    while size > targetTop:
        size -= 1
        top, bot = coprime(tops.popL() * tops.popL(), bots.popL() * bots.popL())
        tops.pushR(top)
        bots.pushR(bot)

    while size > targetBot:
        size -= 1
        bots.pushR(bots.popL() * bots.popL())

    # Cancel all factors in denominator before multiplying the remaining factors
    # in the numerator.
    for bot in bots:
        for ii in range(len(tops)):
            top, bot = coprime(tops.popL(), bot)
            if top > 1:
                tops.pushR(top)
            if bot == 1:
                break

    return tops.foldL(lambda x, y: x * y)

# Fibonacci Iterator

def fibonacci(fib0: int, fib1: int) -> Iterator:
    """Returns iterator to *Fibonacci* sequence whose beginning `fib0, fib1, ...`"""
    while True:
        yield fib0
        fib0, fib1 = fib1, fib0+fib1

Functions

def comb(n: int, m: int, targetTop: int = 700, targetBot: int = 5) ‑> int

Implements C(n,m), the number of combinations of n items taken m at a time, in a way that works efficiently for Python's arbitrary length integers.

• default parameters geared to large values of n and m.
• these defaults work reasonably well for smaller (human size) values
• for inner loops with smaller values, use targetTop = targetBot = 1
• or just use math.comb(n, m) instead
• it is hoped pypy's JIT compiler will give better performance
• raises ValueError if n < 0 or m < 0

Expand source code

def comb(n: int, m: int, targetTop: int=700, targetBot: int=5) -> int:
    """Implements `C(n,m)`, the number of combinations of `n` items taken `m`
    at a time, in a way that works efficiently for Python's arbitrary length
    integers.

    * default parameters geared to large values of `n` and `m`.
    * these defaults work reasonably well for smaller (human size) values
    * for inner loops with smaller values, use `targetTop = targetBot = 1`
    * or just use math.comb(n, m) instead
    * it is hoped pypy's JIT compiler will give better performance
    * raises `ValueError` if `n < 0` or `m < 0`
    """
    if n < 0 or m < 0:
        raise ValueError('for C(n, m) n and m must be a non-negavive ints')
    if n == m or m == 0:
        return 1
    elif m > n:
        return 0

    # using C(n, m) = C(n, n-m) to reduce number of factors in calculation
    if m > (n // 2):
        m = n - m

    # Prepare data structures
    tops = CircularArray(*range(n - m + 1, n + 1))
    bots = CircularArray(*range(1, m+1))

    # Compacting data structures makes algorithm work better for larger values
    size = len(tops)
    while size > targetTop:
        size -= 1
        top, bot = coprime(tops.popL() * tops.popL(), bots.popL() * bots.popL())
        tops.pushR(top)
        bots.pushR(bot)

    while size > targetBot:
        size -= 1
        bots.pushR(bots.popL() * bots.popL())

    # Cancel all factors in denominator before multiplying the remaining factors
    # in the numerator.
    for bot in bots:
        for ii in range(len(tops)):
            top, bot = coprime(tops.popL(), bot)
            if top > 1:
                tops.pushR(top)
            if bot == 1:
                break

    return tops.foldL(lambda x, y: x * y)

def coprime(m: int, n: int) ‑> Tuple(int, int)

Makes 2 integers coprime by dividing out their common factors.

• returns (0, 0) when n = m = 0
• returned coprimed values retain their original signs

Expand source code

def coprime(m: int, n: int) -> Tuple(int, int):
    """Makes 2 integers coprime by dividing out their common factors.

    * returns `(0, 0)` when `n = m = 0`
    * returned coprimed values retain their original signs
    """
    coPrime = lambda mm, nn, common: (mm//common, nn//common)
    return coPrime(m, n, gcd(m, n))

def fibonacci(fib0: int, fib1: int) ‑> Iterator

Returns iterator to Fibonacci sequence whose beginning fib0, fib1, …

Expand source code

def fibonacci(fib0: int, fib1: int) -> Iterator:
    """Returns iterator to *Fibonacci* sequence whose beginning `fib0, fib1, ...`"""
    while True:
        yield fib0
        fib0, fib1 = fib1, fib0+fib1

def gcd(m: int, n: int) ‑> int

Uses Euclidean algorithm to compute the gcd of two integers

• takes two integers, returns gcd > 0
• note that mathematically the gcd of 0 and 0 does not exist
• gcd(0, 0) = 1 a better choice than math.gcd(0, 0) = 0
• gcd(0, 0) = 1 eliminates lcm() & coprime() having to edge case test
• gcd()(0, 0) returning 1 instead of 0 more easily mathematically justified

Expand source code

def gcd(m: int, n: int) -> int:
    """Uses Euclidean algorithm to compute the gcd of two integers

    * takes two integers, returns `gcd > 0`
    * note that mathematically the gcd of `0` and `0` does not exist
    * `gcd(0, 0) = 1` a better choice than `math.gcd(0, 0) = 0`
    * `gcd(0, 0) = 1` eliminates `lcm` & `coprime` having to edge case test
    * `gcd(0, 0)` returning `1` instead of `0` more easily mathematically justified 
    """
    if 0 == m == n:
        return 1
    m, n = abs(m), abs(n)
    m, n = (m, n) if m > n else (n, m)
    while n > 0:
        m, n = n, m % n
    return m

def iSqrt(n: int) ‑> int

Integer square root of a non-negative integer.

• return the unique m such that m*m <= n < (m+1)*(m+1)
• raises: ValueError if n < 0

Expand source code

def iSqrt(n: int) -> int:
    """Integer square root of a non-negative integer.

    * return the unique `m` such that `m*m <= n < (m+1)*(m+1)`
    * raises: ValueError if `n < 0`
    """
    if n < 0:
        msg = 'iSqrt(n): n must be non-negative'
        raise ValueError(msg)
    high = n
    low = 1
    while high > low:
        high = (high + low) // 2
        low = n // high
    return high

def isSqr(n: int) ‑> bool

Returns true if integer argument is a perfect square

Expand source code

def isSqr(n: int) -> bool:
    """Returns true if integer argument is a perfect square"""
    return false if n < 0 else n == iSqrt(n)**2

def lcm(m: int, n: int) ‑> int

Finds the least common multiple (lcm) of two integers.

• takes two integers m and n
• returns lcm(m, n) > 0

Expand source code

def lcm(m: int, n: int) -> int:
    """Finds the least common multiple (lcm) of two integers.

    * takes two integers `m` and `n`
    * returns `lcm(m, n) > 0`
    """
    m //= gcd(m, n)
    return abs(m*n)

def primes(start: int = 2, end_before: int = 100) ‑> Iterator

Return a prime number iterator using the Sieve of Eratosthenes algorithm

Expand source code

def primes(start: int=2, end_before: int=100) -> Iterator:
    """Return a prime number iterator using the *Sieve of Eratosthenes* algorithm"""
    if start >= end_before or end_before < 3:
        return []
    if start < 2:
        start = 2

    sieve = [x for x in range(3, end_before, 2) if x % 3 != 0]
    stop = int(end_before**(0.5)) + 1
    front = -1
    for prime in sieve:
        front += 1
        if prime > stop:
            break
        for pot_prime in sieve[-1:front:-1]:
            if pot_prime % prime == 0:
                sieve.remove(pot_prime)

    if start <= 3 < end_before:  # We missed [2, 3] but
        sieve.insert(0, 3)       # saved about 60% for
    if start <= 2 < end_before:  # the initial storage
        sieve.insert(0, 2)       # space.

    # return sieve after trimming unwanted values
    return (x for x in sieve if x >= start)