The packing of the numerators #
The packing of the numerators of the denominators of each class modulo 64 into one class modulo a
power of 2, as get_2adic_info and class_offsets make it: for each class of the denominators
modulo 64, with the word of the numerators modulo 64 that it admits in the 2-adic information
(Ratpoints.Sieve.twoAdic), the largest stride 2 ^ k, k ≤ 6 and k < Ratpoints.numStrides, for
which these numerators lie in one class a₀ mod 2 ^ k, and the pattern of the word in that packing,
from which the first stage of the sieve starts (Ratpoints.Sieve.andRowsChunked,
Ratpoints.Sieve.andRows), with the word den_bits of the classes that admit a numerator
(Ratpoints.Sieve.numClasses, Ratpoints.Sieve.packPattern); and, once the moduli are known, the
number of the distinct packings (Ratpoints.Sieve.numPackings), and the inverses of the strides
modulo the moduli with the row offsets of each packing, one for each modulus, which shift the rows
so that bit t of the bit array with the word number w stands for the numerator
a₀ + 2 ^ k (Ratpoints.rbaLength w + t) (Ratpoints.Sieve.classOffsets); and for a denominator the
residues of the denominator divided by the stride of its class modulo the moduli of the first two
stages, as fill_bp_list computes them (Ratpoints.Sieve.fillBpList). The classes
(Ratpoints.Sieve.NumClass) and the sieve of one denominator in the packing of its class are in
Ratpoints.Model.Sieve, the 2-adic information and the run, which reads the row offsets and the
residues, in Ratpoints.Model.Denominators.
Main definitions #
Ratpoints.Sieve.classMasks,Ratpoints.Sieve.packPattern,Ratpoints.Sieve.numClasses: the packings of the classes, their strides, residues and patterns.Ratpoints.Sieve.numPackings,Ratpoints.Sieve.halve,Ratpoints.Sieve.classRows,Ratpoints.Sieve.classOffsets: the number of the packings, and the row offsets of the packings with the inverses of the strides.Ratpoints.Sieve.fillBpList: the residues of a denominator divided by the stride of its class.
The classes #
The masks of the strides: bit a < 64 of mask k is set exactly when 2 ^ k ∣ a, for the
seven strides 2 ^ k, k ≤ 6, up to the modulus 64 of the 2-adic information; a mask of a larger
k is read as 0, which ends the loop over the strides of Ratpoints.Sieve.numClasses at k = 7
at the latest, so that its stride exponent is at most 6 whatever Ratpoints.numStrides is.
C: find_points.c:1058-1062
Deviation: an array of UInt64, for the array of RP_NUM_STRIDES unsigned longs, which the C
code initializes with these seven words and zeros beyond them, and an array read with the default
0 beyond its seven entries.
Equations
Instances For
The pattern of the word w of the admissible numerators modulo 64 of a class in the packing of
the stride 2 ^ k, 1 ≤ k ≤ 6, and the residue a₀ < 2 ^ k of all of its set bits: each set bit
a of w, lowest first (Ratpoints.Sieve.ctz), at the place ((a - a₀) mod 64) / 2 ^ k, below
64 / 2 ^ k; then the word doubled from that period up to 64 bits, packed ||| packed <<< s for
s = 64 / 2 ^ k, …, 32. Bit t of the result is bit (a₀ + 2 ^ k t) mod 64 of w.
C: find_points.c:1082-1094
Deviation: a function of its own for the two loops of the packed pattern, which the loop over the
classes of get_2adic_info calls for k ≥ 1 (Ratpoints.Sieve.numClasses), as the loop of the
binary algorithm of relprime is one (Ratpoints.Sieve.relprimeOdd); natural numbers for the
longs a, a0, t and the shift a of the doubling, s here: the difference a - a₀ of
natural numbers, which a ≥ a₀ makes the difference of the C code, the remainder by 64 for the
mask by 0x3f, the same on a non-negative value, and the division by 2 ^ k for the shift by k;
the lowest set bit by the loop of RP_CTZL (Ratpoints.Sieve.ctz).
Equations
- One or more equations did not get rendered due to their size.
Instances For
The packings of the 64 classes of the denominators modulo 64 (Ratpoints.Sieve.NumClass) and
the word den_bits of the classes that admit a numerator, from the words nb of the 2-adic
information (Ratpoints.Sieve.twoAdic), as get_2adic_info makes them: for each class b, with
the word w = nb[b], for w = 0 the stride 1 (k = 0), the residue a₀ = 0 and the pattern 0;
otherwise, for the lowest set bit a of w (Ratpoints.Sieve.ctz), the stride exponent k the
largest below Ratpoints.numStrides and at most 6 for which every set bit of w is
≡ a (mod 2 ^ k), found upwards from 1 with the masks of Ratpoints.Sieve.classMasks until the
first k at which a set bit lies off the mask shifted by a mod 2 ^ k, then less one;
a₀ = a mod 2 ^ k; the pattern w itself for k = 0 and otherwise the packed pattern
(Ratpoints.Sieve.packPattern); and bit b set in den_bits. No class has row offsets yet
(Ratpoints.Sieve.classOffsets). The word den_bits is that of Ratpoints.Sieve.denBits.
C: find_points.c:995, find_points.c:1064-1081, find_points.c:1095-1097,
find_points.c:1099-1104, find_points.c:1106-1114
Deviation: the classes and den_bits returned, for the array cls and the word den_bits that
get_2adic_info fills through its pointer arguments, from the words that Ratpoints.Sieve.twoAdic
returns; the packed pattern of a class with k ≥ 1 by a function of its own
(Ratpoints.Sieve.packPattern); the pattern of a class as one word, for the vector RBA(packed) of
line 1098; natural numbers for the longs k, a0 and a, and the remainder by 2 ^ k for the
mask (1L << k) - 1; the mask of a stride read from the array of the masks with the default 0
beyond its seven entries, as the C code reads the zeros that it puts beyond them; the lowest set bit
by the loop of RP_CTZL (Ratpoints.Sieve.ctz); no output under DEBUG.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The row offsets #
The number of the distinct packings (k, a₀) of the classes cls with a pattern
(Ratpoints.Sieve.NumClass), at least 1: the number of the rows of offsets that
Ratpoints.Sieve.classOffsets makes, which sizes the array of the offsets of the run
(Ratpoints.sieving). The packings are told apart by the key 2 ^ k + a₀, below
2 ^ Ratpoints.numStrides and 128, marked in two words.
C: find_points.c:1119-1130
Deviation: an array of two words, for the array seen of two unsigned longs; natural numbers for
the longs key and n, the division by 64 and the remainder by 64 for the shift by 6 and the
mask by 63 of the key; a natural number for the long result.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Half of x modulo the odd modulus p: x / 2 for even x and (x + p) / 2 for odd x, the
step of the chains of halvings of class_offsets (Ratpoints.Sieve.classOffsets): for x < p it
is below p, and twice it is x modulo p.
C: find_points.c:1159-1160
Deviation: a function of its own for the expression that the C code writes out for d and for e;
the remainder by 2 for the mask & 1 and the division by 2 for the shift >> 1; natural numbers
for the longs.
Instances For
The rows of offsets of the classes cls with a pattern, for the sieve entries es of the np
moduli of the run and the inverses rinv[n][k] = (2 ^ k Ratpoints.rbaLength)⁻¹ mod p of the n-th
modulus p, written into the array offsets of the run: for each class with a pattern, of the
stride 2 ^ k and the residue a₀, with the key 2 ^ k + a₀, the row of an earlier class with the
same key if there is one, and otherwise a new row of np offsets after the rows made so far, at the
position rows np, the n-th the remainder of a₀ rinv[n][k] by a multiplication with the
reciprocal of p (Ratpoints.Sieve.mulMod, exact since a₀ rinv[n][k] p < 2 ^ 64) plus the bias
of p; the class gets the position of its row.
C: find_points.c:1164-1182
Deviation: a function of its own for the loop over the classes of class_offsets
(Ratpoints.Sieve.classOffsets); the classes and the array of the offsets returned, for the array
of the classes and the array of the offsets that class_offsets writes through its pointer
arguments; the table of the rows by their keys an array of options of positions, for the array
row_of of 2 ^ RP_NUM_STRIDES pointers into the offsets, none for NULL, and the row of a class
its position in the array of the offsets, for the pointer row; the inverses rinv an array of
arrays, for the array of RP_NUM_STRIDES longs for each modulus on the stack; natural numbers for
the longs, the product a₀ rinv[n][k] a natural number for the long that RP_MULMOD converts
to an unsigned long, below 2 ^ 63 (Ratpoints.mul_lt_two_pow_63); the reciprocal and the bias
read from the sieve entry, as the C code reads them.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The row offsets of the classes cls, once the moduli of the run, with their sieve entries es,
are known, as class_offsets makes them: the largest stride exponent kmax among the classes with
a pattern; for each modulus p, the chains of halvings modulo p (Ratpoints.Sieve.halve) from
1 and from the inverse rbainv of Ratpoints.rbaLength modulo p, for k = 0, …, kmax, which
give the inverses 2 ^ (-k) mod p, which the sieve entry of p keeps for fill_bp_list
(Ratpoints.Sieve.SieveEntry.dinv, Ratpoints.Sieve.fillBpList), and the inverses
(2 ^ k Ratpoints.rbaLength)⁻¹ mod p; and the rows of offsets of the classes, written into the
array offsets of the run, of Ratpoints.Sieve.numPackings cls rows of one offset for each modulus
(Ratpoints.Sieve.classRows): the offset of a class of the stride 2 ^ k and the residue a₀ for
p is a₀ (2 ^ k Ratpoints.rbaLength)⁻¹ mod p plus the bias of p. The classes and the entries
return with their offsets and their inverses, and the array of the offsets filled.
C: find_points.c:1142-1158, find_points.c:1161-1162, find_points.c:1183
Deviation: the classes, the entries and the array of the offsets returned, for the arrays that
class_offsets writes through its pointer arguments; the number np of the moduli the number of
the sieve entries es, for the run all sp3_max of them (Ratpoints.sieving), with the reserve of
further primes that the correction of the moduli may take into the second stage during the run
(Ratpoints.Sieve.adaptPrimes); the inverses of 2 ^ k an array of kmax + 1 entries, for the
array dinv of RP_NUM_STRIDES longs of the sieve entry, whose entries beyond kmax stay unset
and unread; the inverses rinv an array of arrays, for the array on the stack; the loop over the
classes by a function of its own (Ratpoints.Sieve.classRows); natural numbers for the longs.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The residues of a denominator #
The residues of the denominator b divided by the stride 2 ^ k of its class modulo the moduli
of the sieve entries es of the first two stages, b dinv[k] mod p for the inverse dinv[k] of
2 ^ k modulo the modulus p (Ratpoints.Sieve.SieveEntry.dinv), each by multiplications with the
reciprocal mg of p from mgs (Ratpoints.Sieve.mulMod), exact below 2 ^ 64 / p: for
b ≤ Ratpoints.mulModLimit / Ratpoints.maxPrimeEven, the product b dinv[k] reduced at once; for
b ≤ Ratpoints.mulModLimit, b reduced first and then its product with dinv[k]; and beyond, b
reduced by the helper mod of the C code (Ratpoints.Sieve.modLong), which divides, and then the
product. The branch is chosen once for b. The sieve of the denominator reads the rows of these
residues (Ratpoints.Sieve.setRows).
C: find_points.c:3639-3679
Deviation: a list, made by a map over the entries and their reciprocals (List.zipWith) in the
branch that b chooses and returned, for the array bp_list that the loops over the positions
0, …, sp2 - 1 of sieve_list and magics fill through the pointer argument; the entries of the
first two stages and their reciprocals as arguments, for wk->sp2 and the arrays sieve_list and
magics of the arguments; natural numbers for the longs, the products natural numbers for the
longs that RP_MULMOD converts to unsigned longs, at most Ratpoints.mulModLimit in the first
branch (Ratpoints.mul_le_mulModLimit_of_le_div) and below 2 ^ 63 in the others
(Ratpoints.mul_lt_two_pow_63); no measurement of its time (RP_BP_TIC, RP_BP_TOC).
Equations
- One or more equations did not get rendered due to their size.
Instances For
Examples #
The packings of the classes against those of the loop over the classes of get_2adic_info, and the
patterns and the residues of fill_bp_list against their rules; the row offsets, which need the
sieve entries of the moduli, and the sieve of one denominator in the packing of its class are
examples of Ratpoints.Model.FindPoints.