Loading...
Searching...
No Matches
dirichlet_powerful.h
Go to the documentation of this file.
1#pragma once
2
76
77#include <nut/modular_math.h>
78#include <nut/dirichlet.h>
79
81typedef struct{
82 uint64_t n;
83 int64_t hn;
84 uint64_t i;
85} nut_PfStackEnt;
86
89typedef struct{
90 uint64_t len, cap, max, rt_max, *primes, num_primes, modulus, small_primes;
91 nut_PfStackEnt *entries;
92 int h_kind;
93 union{
94 int64_t (*h_fn)(uint64_t p, uint64_t pp, uint64_t e, uint64_t m);
95 const int64_t *h_vals;
96 struct{
97 uint64_t *offsets;
98 int64_t *values;
99 } h_seqs;
100 };
101} nut_PfIt;
102
111NUT_ATTR_NONNULL(1, 5)
112NUT_ATTR_ACCESS(write_only, 1)
113bool nut_PfIt_init_fn(nut_PfIt *self, uint64_t max, uint64_t modulus, uint64_t small_primes, int64_t (*h_fn)(uint64_t p, uint64_t pp, uint64_t e, uint64_t m));
114
121NUT_ATTR_NONNULL(1, 5)
122NUT_ATTR_ACCESS(write_only, 1)
123bool nut_PfIt_init_hvals(nut_PfIt *restrict self, uint64_t max, uint64_t modulus, uint64_t small_primes, const int64_t *restrict h_vals);
124
135NUT_ATTR_NONNULL(1, 5, 6)
136NUT_ATTR_ACCESS(write_only, 1)
137bool nut_PfIt_init_hseqs(nut_PfIt *restrict self, uint64_t max, uint64_t modulus, uint64_t small_primes,
138 int64_t (*f_fn)(uint64_t p, uint64_t pp, uint64_t e, uint64_t m), int64_t (*g_fn)(uint64_t p, uint64_t pp, uint64_t e, uint64_t m)
139);
140
148#define NUT_PfIt_INIT(self, max, modulus, small_primes, h) _Generic((h), int64_t (*)(uint64_t, uint64_t, uint64_t, uint64_t): nut_PfIt_init_fn, int64_t*: nut_PfIt_init_hvals)((self), (max), (modulus), (small_primes), (h))
149
151NUT_ATTR_NONNULL(1)
152NUT_ATTR_ACCESS(read_write, 1)
153void nut_PfIt_destroy(nut_PfIt *self);
154
158NUT_ATTR_NONNULL(1, 2)
159NUT_ATTR_ACCESS(read_write, 1)
160NUT_ATTR_ACCESS(read_only, 2)
161bool nut_PfStack_push(nut_PfIt *restrict self, const nut_PfStackEnt *restrict ent);
162
166NUT_ATTR_NONNULL(1, 2)
167NUT_ATTR_ACCESS(read_write, 1)
168NUT_ATTR_ACCESS(write_only, 2)
169bool nut_PfStack_pop(nut_PfIt *restrict self, nut_PfStackEnt *restrict out);
170
175NUT_ATTR_NONNULL(1, 2)
176NUT_ATTR_ACCESS(read_write, 1)
177NUT_ATTR_ACCESS(write_only, 2)
178bool nut_PfIt_next(nut_PfIt *restrict self, nut_PfStackEnt *restrict out);
179
187NUT_ATTR_NONNULL(1, 2, 3)
188NUT_ATTR_ACCESS(write_only, 1)
189NUT_ATTR_ACCESS(read_only, 2)
190NUT_ATTR_ACCESS(read_write, 3)
191bool nut_Diri_sum_adjusted(int64_t *restrict out, const nut_Diri *restrict g_tbl, nut_PfIt *pf_it);
192
198NUT_ATTR_NONNULL(1, 2)
199NUT_ATTR_ACCESS(write_only, 1)
200NUT_ATTR_ACCESS(read_write, 2)
201bool nut_Diri_sum_u_adjusted(int64_t *restrict out, nut_PfIt *pf_it);
202
211NUT_ATTR_NONNULL(3, 4, 5)
212NUT_ATTR_ACCESS(read_write, 3)
213NUT_ATTR_ACCESS(read_only, 4)
214NUT_ATTR_ACCESS(read_only, 5)
215void nut_series_div(uint64_t n, int64_t m, int64_t h[restrict static n], int64_t f[restrict static n], int64_t g[restrict static n]);
216
217#define NUT_DIRI_H_FN 0
218#define NUT_DIRI_H_VALS 1
219#define NUT_DIRI_H_SEQS 2
220
nut_PfIt_init_hvals
bool nut_PfIt_init_hvals(nut_PfIt *restrict self, uint64_t max, uint64_t modulus, uint64_t small_primes, const int64_t *restrict h_vals)
Set up a powerful iterator that uses a table of values for h (when h(p^e) depends only on e)
nut_Diri_sum_adjusted
bool nut_Diri_sum_adjusted(int64_t *restrict out, const nut_Diri *restrict g_tbl, nut_PfIt *pf_it)
Compute the sum of f = g <*> h (from 1 up to g_tbl->x), where f(p) = g(p) The modulus used to reduce ...
nut_PfIt_destroy
void nut_PfIt_destroy(nut_PfIt *self)
Delete backing arrays for a powerful number iterator.
nut_PfStack_push
bool nut_PfStack_push(nut_PfIt *restrict self, const nut_PfStackEnt *restrict ent)
Mainly for internal use Push an entry into the internal stack of a powerful number iterator Doing thi...
nut_PfIt_next
bool nut_PfIt_next(nut_PfIt *restrict self, nut_PfStackEnt *restrict out)
Get the next entry from a powerful number iterator This entry will have out->n set to a powerful numb...
nut_PfIt_init_fn
bool nut_PfIt_init_fn(nut_PfIt *self, uint64_t max, uint64_t modulus, uint64_t small_primes, int64_t(*h_fn)(uint64_t p, uint64_t pp, uint64_t e, uint64_t m))
Set up a powerful iterator that uses a callback function to compute h.
nut_series_div
void nut_series_div(uint64_t n, int64_t m, int64_t h[restrict static n], int64_t f[restrict static n], int64_t g[restrict static n])
Compute the series quotient h = f / g for two (finite) power series In other words,...
nut_PfIt_init_hseqs
bool nut_PfIt_init_hseqs(nut_PfIt *restrict self, uint64_t max, uint64_t modulus, uint64_t small_primes, int64_t(*f_fn)(uint64_t p, uint64_t pp, uint64_t e, uint64_t m), int64_t(*g_fn)(uint64_t p, uint64_t pp, uint64_t e, uint64_t m))
Set up a powerful iterator that automatically computes h values given f and g (when a closed form for...
nut_Diri_sum_u_adjusted
bool nut_Diri_sum_u_adjusted(int64_t *restrict out, nut_PfIt *pf_it)
Compute the sum of f = u <*> h (from 1 up to pf_it->max), where f(p) = g(p) The modulus used to reduc...
nut_PfStack_pop
bool nut_PfStack_pop(nut_PfIt *restrict self, nut_PfStackEnt *restrict out)
Mainly for internal use Pop an entry from the internal stack of a powerful number iterator Doing this...
modular_math.h
NUT_ATTR_ACCESS
#define NUT_ATTR_ACCESS(...)
Wrapper for gcc's access function annotation - no clang equivalent, and currently disabled because it...
Definition modular_math.h:40
NUT_ATTR_NONNULL
#define NUT_ATTR_NONNULL(...)
Wrapper for gnu::nonnull attr.
Definition modular_math.h:75
nut_Diri
Wrapper to hold values of some multiplicative function.
Definition dirichlet.h:96
nut_PfIt
Iterator to find all powerful numbers and evaluate a function h at them See NUT_PfIt_INIT,...
Definition dirichlet_powerful.h:89
nut_PfStackEnt
Entry type for nut_PfIt.
Definition dirichlet_powerful.h:81