Module utils

This module contains functions to work with prime numbers and to compute dimension of multivariate spaces

Structs

PrimeNumberGenerator

Functions

compute_all_two_factors_decomposition

Compute all the possible two factors decomposition of a number n. It uses a cache where previous values have been computed. For instance, if n = 6, the function will return [(1, 6), (2, 3), (3, 2), (6, 1)]. The cache might be used to store the results of previous computations. The cache is a hashmap where the key is the number and the value is the list of all the possible two factors decomposition. The hashmap is updated in place. The third parameter is a precomputed list of prime numbers. It is updated in place in case new prime numbers are generated.

compute_indices_nested_loop

Compute the list of indices to perform N nested loops of different size each, whose sum is less than or equal to an optional upper bound. In other words, if we have to perform the 3 nested loops:

get_mapping_with_primes

Build mapping from 1..N to the first N prime numbers. It will be used to encode variables as prime numbers For instance, if N = 3, i.e. we have the variable $x_1, x_2, x_3$, the mapping will be [1, 2, 3, 2, 3, 5] The idea is to encode products of variables as products of prime numbers and then use the factorization of the products to know which variables must be fetched while computing a product of variables

is_prime

Naive implementation checking if n is prime You can also use the structure PrimeNumberGenerator to check if a number is prime using

naive_prime_factors

Given a number n, return the list of prime factors of n, with their multiplicity The first argument is the number to factorize, the second argument is the list of prime numbers to use to factorize the number The output is a list of tuples, where the first element is the prime number and the second element is the multiplicity of the prime number in the factorization of n.