Termial random using CPython extension

termial_random.py

#!/usr/bin/env python3
# pip install termial-random
from termial_random import random as termial_random
from termial_random import seed as termial_seed
import math
import os
import random
import sys
import timeit

_ROUNDS = int(os.getenv("TERMIAL_DEFAULT_ROUNDS", 3))
_ITERATIONS = int(os.getenv("TERMIAL_ITERATIONS", 1000000))
_N = int(os.getenv("TERMIAL_N", 10000))


def random_termial_v0(n: int) -> int:
    """Get index to an item from a list of size n.
    The higher index of an item is, the lower probability of picking it.
    """
    termial_of_n = ((n * n) + n) >> 1
    choice = random.randrange(termial_of_n)
    i = math.floor(-0.5 + math.sqrt(0.25 + (choice << 1)))
    return n - 1 - i


def random_termial_v1(n: int) -> int:
    """Get index to an item from a list of size n.
    The higher index of an item is, the lower probability of picking it.
    """
    termial_of_n = ((n ** 2) + n) >> 1
    choice = random.randrange(termial_of_n)
    i = math.floor(-0.5 + math.sqrt(0.25 + (choice << 1)))
    return n - 1 - i


def random_termial_v2(n: int) -> int:
    """Get index to an item from a list of size n.
    The higher index of an item is, the lower probability of picking it.
    """
    if n % 2:  # or n & 1
        # odd numbers
        nearest = n + 1
        termial_of_n = ((1 + nearest) * (nearest / 2)) - nearest
    else:
        termial_of_n = (1 + n) * (n / 2)

    choice = random.randrange(termial_of_n)
    i = math.floor(-0.5 + math.sqrt(0.25 + (choice << 1)))
    return n - 1 - i


def random_termial_v3(n: int) -> int:
    """Get index to an item from a list of size n.
    The higher index of an item is, the lower probability of picking it.
    """
    addition = (n * (n & 1))
    nearest = n + addition
    termial_of_n = ((1 + nearest) * (nearest >> 1)) - addition
    choice = random.randrange(termial_of_n)
    i = math.floor(-0.5 + math.sqrt(0.25 + (choice << 1)))
    return n - 1 - i


def main():
    print("n          = ", _N)
    print("rounds     = ", _ROUNDS)
    print("iterations = ", _ITERATIONS)
    print()
    termial_seed(100)
    for i in range(_ROUNDS):
        print(f">>> Round {i}")
        for func in ("termial_random", "random_termial_v0", "random_termial_v1", "random_termial_v2", "random_termial_v3"):
            print(
                "\t",
                func,
                ": ",
                timeit.timeit(
                    f"{func}({_N})",
                    number=_ITERATIONS,
                    globals=globals(),
                ),
            )


__name__ == "__main__" and main()

Results:

n          =  10000
rounds     =  3
iterations =  1000000

>>> Round 0
	 termial_random :  0.09750318998703733
	 random_termial_v0 :  1.1372068689961452
	 random_termial_v1 :  1.269488532008836
	 random_termial_v2 :  1.168210485993768
	 random_termial_v3 :  1.311580680005136
>>> Round 1
	 termial_random :  0.10147541099286173
	 random_termial_v0 :  1.5275097150006332
	 random_termial_v1 :  1.8169503919925774
	 random_termial_v2 :  1.4386834100005217
	 random_termial_v3 :  1.5303558710002108
>>> Round 2
	 termial_random :  0.0953157280018786
	 random_termial_v0 :  1.1922939850046532
	 random_termial_v1 :  1.371060094999848
	 random_termial_v2 :  1.1832250639999984
	 random_termial_v3 :  1.4025582900067093