moewsmoews_sieve.h File Reference

api to the Moews and Moews sieving algorithm More...

#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <sys/types.h>

Include dependency graph for moewsmoews_sieve.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	sieve_config_t
	Configuration and computed values needed to operate sieve, only 1 needed for multiple threads. More...
struct	sieve_worker_t
	Worker which holds state about a single thread running the sieve. More...

Functions
void	moews_sieve_odd_standard (sieve_worker_t *worker, uint64_t seg_start)
	runs sieve for odd sigma(m) More...
void	moews_sieve_odd_squared (sieve_worker_t *worker, uint64_t seg_start)
	takes odd m in range and runs sieve for sigma(m * m) More...
uint64_t	moews_lookup_sigma_m (const sieve_worker_t *worker, uint64_t m)
	lookup sigma(m) from m in a sieved block More...
uint64_t	moews_lookup_sigma_m_squared (const sieve_worker_t *worker, uint64_t m)
	lookup sigma(m * m) from m in a sieved block More...
sieve_config_t *	moews_init_sieve (size_t bound, size_t seg_len)
	creates a sieve_config_t which is shared by a pool of workers More...
void	moews_destroy_sieve (sieve_config_t *cfg)
	free's memory associated with sieve_config_t More...
sieve_worker_t *	moews_init_worker (const sieve_config_t *cfg)
	creates a worker object which can be used to run the sieve More...
void	destroy_worker (sieve_worker_t *worker)
	free's memory associated with sieve_worker_t More...
bool	moews_check_prime (const sieve_worker_t *worker, uint64_t m)
	checks if odd numbers in range (seg_start, seg_start + seg_len) is prime More...
size_t	moews_estimate_heap_usage (size_t bound, size_t seg_len, size_t num_workers)
	estimates how much heap the sieving buffers will require More...

Detailed Description

api to the Moews and Moews sieving algorithm

Author

Gavin Guinn (gavin.nosp@m.guin.nosp@m.n1@gm.nosp@m.ail..nosp@m.com)

Date

Originally Apr 18, 2014, modified 2021-12-27

Copyright

Public Domain (Please credit me; if you find this code useful I would love to hear about your work!)

Function Documentation

destroy_worker()

void destroy_worker

(

sieve_worker_t *

worker

)

free's memory associated with sieve_worker_t

Parameters

worker

to be free'd

moews_check_prime()

bool moews_check_prime	(	const sieve_worker_t *	worker,
		uint64_t	m
	)

checks if odd numbers in range (seg_start, seg_start + seg_len) is prime

Parameters

worker	that has previously run moews_sieve_odd_standard
m	check if this odd number in range (seg_start, seg_start + seg_len) is prime

Returns

bool is prime

moews_destroy_sieve()

void moews_destroy_sieve

(

sieve_config_t *

cfg

)

free's memory associated with sieve_config_t

Parameters

cfg	to be free'd

moews_estimate_heap_usage()

size_t moews_estimate_heap_usage	(	size_t	bound,
		size_t	seg_len,
		size_t	num_workers
	)

estimates how much heap the sieving buffers will require

Parameters

bound	sieve all odd sigma upto to bound
seg_len	size of range to sieve in a step
num_workers	number of threads working

Returns

size_t approx bytes to be consumed

moews_init_sieve()

sieve_config_t* moews_init_sieve	(	size_t	bound,
		size_t	seg_len
	)

creates a sieve_config_t which is shared by a pool of workers

Parameters

bound	sieving all odd sigma upto to bound
seg_len	size of range to sieve in a step

Returns

sieve_config_t* config struct which is free'd by calling moews_destroy_sieve

moews_init_worker()

sieve_worker_t* moews_init_worker

(

const sieve_config_t *

cfg

)

creates a worker object which can be used to run the sieve

Parameters

cfg	initalized sieve configuration struct

Returns

sieve_worker_t*

moews_lookup_sigma_m()

uint64_t moews_lookup_sigma_m	(	const sieve_worker_t *	worker,
		uint64_t	m
	)

lookup sigma(m) from m in a sieved block

Parameters

worker	see definition, has run moews_sieve_odd_standard last
m	number to lookup

Returns

uint64_t sigma(m)

moews_lookup_sigma_m_squared()

uint64_t moews_lookup_sigma_m_squared	(	const sieve_worker_t *	worker,
		uint64_t	m
	)

lookup sigma(m * m) from m in a sieved block

Parameters

worker	see definition, has run moews_sieve_odd_squared last
m	number to lookup

Returns

uint64_t sigma(m * m)

moews_sieve_odd_squared()

void moews_sieve_odd_squared	(	sieve_worker_t *	worker,
		uint64_t	seg_start
	)

takes odd m in range and runs sieve for sigma(m * m)

Parameters

worker	see struct definiton
seg_start	start of range to sieve

moews_sieve_odd_standard()

void moews_sieve_odd_standard	(	sieve_worker_t *	worker,
		uint64_t	seg_start
	)

runs sieve for odd sigma(m)

Parameters

worker	see struct definiton
seg_start	start of range to sieve