approx.h File Reference

Approximate a value by multiplying some numbers from a pool. More...

#include <stdint.h>
#include <stdbool.h>
#include "exit_codes.h"
#include "array.h"

Go to the source code of this file.

Data Structures
struct	struct_uint32_tuple_t
	Defines a tuple of integers together with a sorting key. More...
struct	struct_approximer_t
	Structure used to find number approximation. More...
Defines
#define	_TIFA_APPROX_H_
#define	MAX_NPRIMES_IN_TUPLE   3
Typedefs
typedef struct struct_uint32_tuple_t	uint32_tuple_t
	Equivalent to struct_uint32_tuple_t.
Functions
approximer_t *	alloc_approximer (mpz_t target, uint32_array_t *const facpool, uint32_t nfactors)
	Allocates and returns a new approximer_t.
void	free_approximer (approximer_t *aximer)
	Frees a previously allocated approximer_t.
void	random_approximation (approximer_t *const aximer, mpz_t approxed, uint32_t *indexes)
	Generates a "random" approximation.

---

Detailed Description

Approximate a value by multiplying some numbers from a pool.

Author:

Jerome Milan

Date:

Fri Jun 10 2011

Version:

2011-06-10

This provides a structure approximer_t and associated functions that can be used to approximate a target value by multiplying a given number of factors from a given base. Each factor is allowed to appear only once in the decomposition of the approximation on the given base.

This is used in TIFA's SIQS implementation where we need to find a polynomial coefficient of a given order from the product of some prime numbers.

The strategy used to reach a good approximation is adapted from the Carrier-Wagstaff method.

• Let t be the target number to be obtained by multiplying n distinct numbers from a given base B=[p_1, p_2, p_3, ...] (with p_i < p_{i+1}).

• Set m so that B[m] is roughly equal to the n^th-root of t. Factors will be chosen from the set B[m-d], ..., B[m+d] with d suitably chosen.

• The approximation a of the target t is obtained by choosing a random combination of (n-i) factors completed by i other factors so as to obtain the best approximation as possible.

• Since all numbers must be distinct the (n-i) randomly chosen factors are picked from the set of B[j] with j odd and the remaining i factors from the set of B[k] with k even.

• The best remaining i factors are obtained by precomputing and sorting all combinations of i factors, then picking the most suitable one.

Definition in file approx.h.

---

Define Documentation

#define _TIFA_APPROX_H_

Standard include guard.

Definition at line 65 of file approx.h.

#define MAX_NPRIMES_IN_TUPLE   3

Maximum number of factors in the sorted factor combinations.

Definition at line 81 of file approx.h.

---

Function Documentation

approximer_t* alloc_approximer	(	mpz_t	target,
		uint32_array_t *const	facpool,
		uint32_t	nfactors
	)

Allocates and returns a new approximer_t.

Parameters:

	target	the target number to approximate.
	facpool	the pool of available factors.
	nfactors	the number of factors from facpool to use.

Returns:

A pointer to the newly allocated approximer_t.

void free_approximer

(

approximer_t *

aximer

)

Frees a previously allocated approximer_t.

Frees all memory used by the pointed approximer_t and then frees the aximer pointer.

Warning:

Do not call free(aximer) in client code after a call to free_approximer(aximer): it would result in an error.

Parameters:

aximer

the approximer_t to free.

void random_approximation	(	approximer_t *const	aximer,
		mpz_t	approxed,
		uint32_t *	indexes
	)

Generates a "random" approximation.

Parameters:

[in]	aximer	the approximer_t to use.
[out]	approxed	the approximation obtained.
[out]	indexes	the (sorted) indexes of the factors making up the approximation.