Skip to main content
Redhat Developers  Logo
  • Products

    Featured

    • Red Hat Enterprise Linux
      Red Hat Enterprise Linux Icon
    • Red Hat OpenShift AI
      Red Hat OpenShift AI
    • Red Hat Enterprise Linux AI
      Linux icon inside of a brain
    • Image mode for Red Hat Enterprise Linux
      RHEL image mode
    • Red Hat OpenShift
      Openshift icon
    • Red Hat Ansible Automation Platform
      Ansible icon
    • Red Hat Developer Hub
      Developer Hub
    • View All Red Hat Products
    • Linux

      • Red Hat Enterprise Linux
      • Image mode for Red Hat Enterprise Linux
      • Red Hat Universal Base Images (UBI)
    • Java runtimes & frameworks

      • JBoss Enterprise Application Platform
      • Red Hat build of OpenJDK
    • Kubernetes

      • Red Hat OpenShift
      • Microsoft Azure Red Hat OpenShift
      • Red Hat OpenShift Virtualization
      • Red Hat OpenShift Lightspeed
    • Integration & App Connectivity

      • Red Hat Build of Apache Camel
      • Red Hat Service Interconnect
      • Red Hat Connectivity Link
    • AI/ML

      • Red Hat OpenShift AI
      • Red Hat Enterprise Linux AI
    • Automation

      • Red Hat Ansible Automation Platform
      • Red Hat Ansible Lightspeed
    • Developer tools

      • Red Hat Trusted Software Supply Chain
      • Podman Desktop
      • Red Hat OpenShift Dev Spaces
    • Developer Sandbox

      Developer Sandbox
      Try Red Hat products and technologies without setup or configuration fees for 30 days with this shared Openshift and Kubernetes cluster.
    • Try at no cost
  • Technologies

    Featured

    • AI/ML
      AI/ML Icon
    • Linux
      Linux Icon
    • Kubernetes
      Cloud icon
    • Automation
      Automation Icon showing arrows moving in a circle around a gear
    • View All Technologies
    • Programming Languages & Frameworks

      • Java
      • Python
      • JavaScript
    • System Design & Architecture

      • Red Hat architecture and design patterns
      • Microservices
      • Event-Driven Architecture
      • Databases
    • Developer Productivity

      • Developer productivity
      • Developer Tools
      • GitOps
    • Secure Development & Architectures

      • Security
      • Secure coding
    • Platform Engineering

      • DevOps
      • DevSecOps
      • Ansible automation for applications and services
    • Automated Data Processing

      • AI/ML
      • Data Science
      • Apache Kafka on Kubernetes
      • View All Technologies
    • Start exploring in the Developer Sandbox for free

      sandbox graphic
      Try Red Hat's products and technologies without setup or configuration.
    • Try at no cost
  • Learn

    Featured

    • Kubernetes & Cloud Native
      Openshift icon
    • Linux
      Rhel icon
    • Automation
      Ansible cloud icon
    • Java
      Java icon
    • AI/ML
      AI/ML Icon
    • View All Learning Resources

    E-Books

    • GitOps Cookbook
    • Podman in Action
    • Kubernetes Operators
    • The Path to GitOps
    • View All E-books

    Cheat Sheets

    • Linux Commands
    • Bash Commands
    • Git
    • systemd Commands
    • View All Cheat Sheets

    Documentation

    • API Catalog
    • Product Documentation
    • Legacy Documentation
    • Red Hat Learning

      Learning image
      Boost your technical skills to expert-level with the help of interactive lessons offered by various Red Hat Learning programs.
    • Explore Red Hat Learning
  • Developer Sandbox

    Developer Sandbox

    • Access Red Hat’s products and technologies without setup or configuration, and start developing quicker than ever before with our new, no-cost sandbox environments.
    • Explore Developer Sandbox

    Featured Developer Sandbox activities

    • Get started with your Developer Sandbox
    • OpenShift virtualization and application modernization using the Developer Sandbox
    • Explore all Developer Sandbox activities

    Ready to start developing apps?

    • Try at no cost
  • Blog
  • Events
  • Videos

Generating pseudorandom numbers in Python

November 4, 2021
Fridolin Pokorny
Related topics:
C, C#, C++Open sourcePython
Related products:
Red Hat Enterprise Linux

Share:

    Random functions typically assign the same priority to each possible choice. In some cases, though, you want to be able to make a random choice while prioritizing some options. For instance, in Project Thoth, we need to prioritize more recent releases of Python packages. We use pseudorandom number calculation to prioritize newer libraries in the exploration phase of Thoth's reinforcement learning algorithm.

    This article explores termial random, a specific type of pseudorandom number calculation used in Project Thoth. We'll use the termial-random number generator to select an item from a list, assign the highest probability to the item at index 0, then assign lower probabilities to the following items as the index increases. You can apply the discussion and resources in this article to other Python projects.

    Pseudorandom number generation in Python

    The Python standard library offers several functions for pseudorandom number generation. For instance, if we want to pick an item randomly from a list, the random.choice method works well:

    import random
    
    my_list = [42, 33, 30, 16]
    # results in 42 with a probability of 1 / len(my_list)
    random.choice(my_list)

    Now, let’s say we want to give higher numbers a higher probability of being chosen. In other words, in the my_list example, we want to prioritize 42 over 33, 33 over 30, and 30 over 16.

    Weighted random choice in Python

    We have four numbers in total in our list, so let’s assign weights to these numbers as shown in Table 1.

    Table 1. Weights assigned to numbers.
    Number Weight
    42 4

    33

    3
    30 2
    16 1

    You can think of each weight as a number of "buckets" assigned to the number. In a randomly uniform way, our algorithm tries to hit one bucket. After hitting the bucket, we check which number the bucket corresponds to.

    The total number of buckets we can hit is equal to the sum of the weights:

    4 + 3 + 2 + 1 = 10

    Table 2 shows the probability of hitting each number, based on the buckets assigned to it, where all probabilities total up to 1.0.

    Table 2. The probability of hitting a number.
    Number Probability
    42 4 / 10 = 0.4
    33

    3 / 10 = 0.3

    30 2 / 10 = 0.2
    16 1 / 10 = 0.1

    Termial random number calculation

    To generalize this prioritization for n numbers, we can create the following formula that computes the total number of buckets to use for any n:

    n? = 1 + 2 + 3 + ... + (n - 2) + (n - 1) + n

    We could also write this formula as shown in Figure 1.

    Another way to write the termial formula.
    Figure 1. Another way to write the termial formula.

    The formula is called a termial as an analogy to factorials. The concept is related to triangular numbers.

    Computing the termial of n

    To compute the termial of n in Python, the simplest implementation is:

    termial_of_n = sum(range(1, len(my_list) + 1))  # O(N)

    A more efficient calculation uses the binomial coefficient and computes (len(my_list) + 1) over 2:

    l = len(my_list)
    # (l + 1) over 2 = l! / (2!*(l-2)!) = l * (l - 1) / 2
    termial_of_n = ((l*l) + l) >> 1  # O(1)

    Finally, we can pick a random (random uniform) bucket from our set of buckets:

    import random
    
    choice = random.randrange(termial_of_n)

    The result, stored in the variable choice, holds an integer from 0 to 9 (inclusively) and represents an index into the list of the buckets we created earlier, as shown in Table 3.

    Table 3. A complete list of buckets and possible choices.
    Choice Bucket Number
    0 1 42
    1 2 42
    2 3 42
    3 4 42
    4 5 33
    5 6 33
    6 7 33
    7 8 30
    8 9 30
    9 10 16

    Termial random with the binomial coefficient

    Now, how do we find which number we hit through a randomly picked bucket for any n? Let’s revisit how we computed the termial number of n using the formula based on the binomial coefficient:

    l = len(my_list)
    termial_of_n = ((l*l) + l) >> 1

    Following the definition of the termial function, we know that regardless of n, we always assign one bucket to the number at index n-1, two buckets to the number at index n-2, three buckets to the number at index n-3, and so on, down to the index 0. Using this knowledge, we can transform the binomial coefficient formula to the following equation:

    choice = ((i*i) + i) >> 1

    The next step is to find i that satisfies the given equation. The equation is a quadratic function described as:

    a*(i**2) + b*i + c = 0

    The values of our coefficients are:

    a = 1/2
    b = 1/2
    c = -choice

    Because choice is expected always to be a non-negative integer (an index into the list of buckets), we can search for a solution that always results in a non-negative integer (reducing one discriminant term that always results in negative i):

    import math
    
    # D = b**2 - 4*a*c
    # x1 = (-b + math.sqrt(D)) / (2*a)
    # x2 = (-b - math.sqrt(D)) / (2*a)
    # Given:
    #   a = 1/2
    #   b = 1/2
    #   c = -choice
    # D = (1/2)**2 + 4*0.5*choice = 0.25 + 2*choice
    i = math.floor(-0.5 + math.sqrt(0.25 + (choice << 1)))

    The solution has to be rounded using math.floor because it corresponds to the inverted index with respect to n. Because i is inverted, the final solution (index to the original list) is:

    my_list[n - 1 - i]

    Running the termial-random number generator

    Now, let's do the asymptotic complexity analysis, assuming that:

    • The len function can return the length of the list in O(1) time.
    • random.randrange operates in O(1) time.
    • We use the equation based on the binomial coefficient to compute the termial of n.

    The whole computation is done in O(1) time and O(1) space.

    If we used the sum-based computation of the termial of n, the algorithm would require O(n) time and O(1) space.

    The final source code in Python is:

    import random
    import math
    
    def random_termial(n: int) -> int:
        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

    Figure 2 shows the number of hits for n=10 when the termial random generator was run one million times:

    A benchmark shows that the termial generator works, choosing high-priority items more often than low-priority items.
    Figure 2. A benchmark with the termial random number generator.

    The chart shows that, just as we want, index 0 is prioritized most of the time; after that, index 1 is prioritized, and so on. The lowest priority is given to the index 9.

    Where to find the termial-random package

    The Project Thoth recommendation engine is available in a component called adviser and uses a C extension that implements the termial random calculation. The C extension is available on PyPI as the termial-random package and the source code is hosted in the thoth-station/termial-random repository.

    Conclusion

    As part of Project Thoth, we are accumulating knowledge to help Python developers create healthy applications. If you would like to follow updates in Project Thoth, feel free to subscribe to our YouTube channel or follow us on the @ThothStation Twitter handle.

    Last updated: October 6, 2022

    Related Posts

    • Secure your Python applications with Thoth recommendations

    • Resolve Python dependencies with Thoth Dependency Monkey

    • Thoth prescriptions for resolving Python dependencies

    • Mostly harmless: An account of pseudo-normal floating point numbers

    Recent Posts

    • Build container images in CI/CD with Tekton and Buildpacks

    • How to deploy OpenShift AI & Service Mesh 3 on one cluster

    • JVM tuning for Red Hat Data Grid on Red Hat OpenShift 4

    • Exploring Llama Stack with Python: Tool calling and agents

    • Enhance data security in OpenShift Data Foundation

    Red Hat Developers logo LinkedIn YouTube Twitter Facebook

    Products

    • Red Hat Enterprise Linux
    • Red Hat OpenShift
    • Red Hat Ansible Automation Platform

    Build

    • Developer Sandbox
    • Developer Tools
    • Interactive Tutorials
    • API Catalog

    Quicklinks

    • Learning Resources
    • E-books
    • Cheat Sheets
    • Blog
    • Events
    • Newsletter

    Communicate

    • About us
    • Contact sales
    • Find a partner
    • Report a website issue
    • Site Status Dashboard
    • Report a security problem

    RED HAT DEVELOPER

    Build here. Go anywhere.

    We serve the builders. The problem solvers who create careers with code.

    Join us if you’re a developer, software engineer, web designer, front-end designer, UX designer, computer scientist, architect, tester, product manager, project manager or team lead.

    Sign me up

    Red Hat legal and privacy links

    • About Red Hat
    • Jobs
    • Events
    • Locations
    • Contact Red Hat
    • Red Hat Blog
    • Inclusion at Red Hat
    • Cool Stuff Store
    • Red Hat Summit
    © 2025 Red Hat

    Red Hat legal and privacy links

    • Privacy statement
    • Terms of use
    • All policies and guidelines
    • Digital accessibility

    Report a website issue