sqrt_cont_frac.h File Reference

Continued fraction expansion for square root of integers. More...

#include <inttypes.h>
#include <gmp.h>

Go to the source code of this file.

Data Structures
struct	struct_cont_frac_state_t
	An ad-hoc structure for the computation of the continued fraction of a square root. More...
Defines
#define	_TIFA_SQRT_CONT_FRAC_H_
Typedefs
typedef struct struct_cont_frac_state_t	cont_frac_state_t
	Equivalent to struct struct_cont_frac_state_t.
Functions
void	init_cont_frac_state (cont_frac_state_t *const state, const mpz_t n)
	Initializes a cont_frac_state_t.
void	clear_cont_frac_state (cont_frac_state_t *const state)
	Clears a cont_frac_state_t.
static void	step_cont_frac_state (cont_frac_state_t *const state, uint32_t nsteps)
	Computes another term of a continued fraction.

---

Detailed Description

Continued fraction expansion for square root of integers.

Author:

Jerome Milan

Date:

Fri Jun 10 2011

Version:

2011-06-10

Defines the continued fraction expansion for the square root of non-perfect square integers.

The expansion is computed via an iterative process, each step giving the value of a new numerator. All the variables needed to perform this computation is stored in an ad-hoc structure called struct_cont_frac_state_t.

Note:

Since the denominator of the continued fraction is not used in the CFRAC algorithm, it is not computed here. Also, the numerator of the fraction is only given modulo n. These restrictions are completely trivial to fix should one need the complete approximation a/b of a square root.

Definition in file sqrt_cont_frac.h.

---

Define Documentation

#define _TIFA_SQRT_CONT_FRAC_H_

Standard include guard.

Definition at line 47 of file sqrt_cont_frac.h.

---

Function Documentation

void clear_cont_frac_state

(

cont_frac_state_t *const

state

)

Clears a cont_frac_state_t.

Clears a cont_frac_state_t.

Parameters:

[in]

state

A pointer to the cont_frac_state_t to clear.

void init_cont_frac_state	(	cont_frac_state_t *const	state,
		const mpz_t	n
	)

Initializes a cont_frac_state_t.

Initializes a cont_frac_state_t to begin the computation of a continued fraction. After invocation of this function, the fields of state corresponds to the calculation of the second term of the computed fraction, the first term beeing of course ceil(sqrt(n)).

Parameters:

[in]	state	A pointer to the cont_frac_state_t to initialize.
[in]	n	The non perfect square integer whose square root will be approximated by the computation of a continued fraction.

static void step_cont_frac_state	(	cont_frac_state_t *const	state,
		uint32_t	nsteps
	)			[inline, static]

Computes another term of a continued fraction.

Computes another coefficient in the expansion of a continued fraction and updates the structure state. The parameter nsteps gives the number of iteration to perform. A new term is computed at each iteration.

Note:

This function is actually given by state->step_function.

Parameters:

[in]	state	A pointer to the cont_frac_state_t.
[in]	nsteps	Number of steps to perfom.

Definition at line 192 of file sqrt_cont_frac.h.

References struct_cont_frac_state_t::step_function.