Continued fraction/Arithmetic/G(matrix ng, continued fraction n): Difference between revisions
Content added Content deleted
Line 1,444: | Line 1,444: | ||
=={{header|C}}== |
=={{header|C}}== |
||
===With a garbage collector=== |
|||
{{trans|ATS}} |
{{trans|ATS}} |
||
{{libheader|Boehm GC}} |
{{libheader|Boehm GC}} |
||
I use a garbage collector to make the free use of heap space both easier and more error-free. Or, in many cases, you can simply let the memory leak. |
I use a garbage collector to make the free use of heap space both easier and more error-free. Or, in many cases, you can simply let the memory leak. |
||
The output of a generator is memoized and can be reused without computing again. If the generator needs to produce more terms, it picks up where it left off. |
|||
<syntaxhighlight lang="c"> |
<syntaxhighlight lang="c"> |
||
Line 1,979: | Line 1,982: | ||
(1+sqrt(2)/2)/2 => [0;1,5,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,...] |
(1+sqrt(2)/2)/2 => [0;1,5,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,...] |
||
(1+1/sqrt(2))/2 => [0;1,5,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,...]</pre> |
(1+1/sqrt(2))/2 => [0;1,5,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,...]</pre> |
||
===Without a garbage collector=== |
|||
{{trans|ATS}} |
|||
This code is ported from ATS code that uses linear typing to ensure good malloc/free discipline. I try to retain the memory-use pattern of the ATS, to be safe against double-free errors, and hopefully to avoid memory leaks. (Absence of leaks is harder to be sure of.) When a generator is used as source of terms for another generator, the latter generator "consumes" the former (as if the types were linear), severely limiting reusability. Because of this, reusability of a generator is limited, and so I do not bother with memoization. |
|||
I use the '''[[maybe_unused]]''' notation of C23. You can simply remove the very few instances of it, if they bother you. |
|||
For no good reason, the program writes its output as code for input to groff. |
|||
<syntaxhighlight lang="C"> |
|||
/*------------------------------------------------------------------*/ |
|||
/* For C23 without need of a garbage collector. */ |
|||
#include <assert.h> |
|||
#include <stdio.h> |
|||
#include <stdlib.h> |
|||
#include <stdint.h> |
|||
#include <stdbool.h> |
|||
#include <string.h> |
|||
/*------------------------------------------------------------------*/ |
|||
/* We need consistent definitions of division and remainder. Let us |
|||
set those here. For convenience (because C provides it), we will |
|||
use truncation towards zero. */ |
|||
#define DIV(a, b) ((a) / (b)) |
|||
#define REM(a, b) ((a) % (b)) |
|||
/* Choose a memory allocator. (Ideally one should check for NULL |
|||
return values, but for this pedagogical example let us skip |
|||
that.) */ |
|||
#define MALLOC_INIT() do { } while (0) /* A no-op. */ |
|||
#define MALLOC malloc |
|||
#define REALLOC realloc |
|||
#define FREE free |
|||
/*------------------------------------------------------------------*/ |
|||
/* The basics. */ |
|||
/* The integer type. */ |
|||
typedef long long int integer; |
|||
/* A generator is a recursive type that forms a tree. */ |
|||
typedef struct generator *generator_t; |
|||
typedef struct generator_list *generator_list_t; |
|||
struct generator_list |
|||
{ |
|||
generator_t car; |
|||
generator_list_t cdr; |
|||
}; |
|||
typedef void generator_func_t (integer *workspace, |
|||
generator_list_t sources, |
|||
bool *term_exists, |
|||
integer *term); |
|||
struct generator |
|||
{ |
|||
generator_func_t *run; /* What does the work. */ |
|||
size_t worksize; /* The size of the workspace. */ |
|||
integer *initial; /* The initial value of the workspace. */ |
|||
integer *workspace; /* The workspace itself. */ |
|||
generator_list_t sources; /* The sources of input terms. */ |
|||
}; |
|||
/* Reinitializes a generator. (Needed because there is no |
|||
memoization.) */ |
|||
void generator_t_initialize (generator_t); |
|||
/* Frees a generator. */ |
|||
void generator_t_free (generator_t); |
|||
/*------------------------------------------------------------------*/ |
|||
/* A function to print the output of a generator in a form suitable |
|||
for eqn/troff. */ |
|||
void ftroff_generator_output (FILE *, generator_t, int max_terms); |
|||
/*------------------------------------------------------------------*/ |
|||
/* Some functions to make generators. */ |
|||
/* For a rational number. */ |
|||
generator_t r2cf_make (integer n, integer d); |
|||
/* For the square root of 2. */ |
|||
generator_t sqrt2_make (void); |
|||
/* For a homographic function. */ |
|||
generator_t hfunc_make (integer a1, integer a, integer b1, integer b, |
|||
generator_t source); |
|||
/*------------------------------------------------------------------*/ |
|||
/* Implementations. */ |
|||
void |
|||
generator_t_initialize (generator_t gen) |
|||
{ |
|||
if (gen != NULL) |
|||
{ |
|||
memcpy (gen->workspace, gen->initial, |
|||
gen->worksize * sizeof (integer)); |
|||
for (generator_list_t p = gen->sources; p != NULL; p = p->cdr) |
|||
generator_t_initialize (p->car); |
|||
} |
|||
} |
|||
void |
|||
generator_t_free (generator_t gen) |
|||
{ |
|||
if (gen != NULL) |
|||
{ |
|||
FREE (gen->initial); |
|||
FREE (gen->workspace); |
|||
generator_list_t p = gen->sources; |
|||
while (p != NULL) |
|||
{ |
|||
generator_list_t q = p->cdr; |
|||
generator_t_free (p->car); |
|||
FREE (p); |
|||
p = q; |
|||
} |
|||
FREE (gen); |
|||
} |
|||
} |
|||
/* - - - - - - - - - - - - - */ |
|||
void |
|||
ftroff_generator_output (FILE *outf, generator_t gen, int max_terms) |
|||
{ |
|||
assert (1 <= max_terms); |
|||
generator_t_initialize (gen); |
|||
int terms_count = 0; |
|||
int sep = 0; |
|||
bool done = false; |
|||
while (!done) |
|||
{ |
|||
if (terms_count == max_terms) |
|||
{ |
|||
fprintf (outf, ", ~ ... ~ ]"); |
|||
done = true; |
|||
} |
|||
else |
|||
{ |
|||
bool term_exists; |
|||
integer term; |
|||
gen->run (gen->workspace, gen->sources, &term_exists, |
|||
&term); |
|||
if (term_exists) |
|||
{ |
|||
switch (sep) |
|||
{ |
|||
case 0: |
|||
fprintf (outf, "[ ^ "); |
|||
sep = 1; |
|||
break; |
|||
case 1: |
|||
fprintf (outf, "; ^ "); |
|||
sep = 2; |
|||
break; |
|||
default: |
|||
fprintf (outf, " , "); |
|||
break; |
|||
} |
|||
fprintf (outf, "%jd", (intmax_t) term); |
|||
terms_count += 1; |
|||
} |
|||
else |
|||
{ |
|||
fprintf (outf, "^ ] "); |
|||
done = true; |
|||
} |
|||
} |
|||
} |
|||
generator_t_initialize (gen); |
|||
} |
|||
/* - - - - - - - - - - - - - */ |
|||
static void |
|||
r2cf_run (integer *workspace, |
|||
[[maybe_unused]] generator_list_t sources, |
|||
bool *term_exists, integer *term) |
|||
{ |
|||
integer d = workspace[1]; |
|||
*term_exists = (d != 0); |
|||
if (*term_exists) |
|||
{ |
|||
integer n = workspace[0]; |
|||
integer q = DIV (n, d); |
|||
integer r = REM (n, d); |
|||
workspace[0] = d; |
|||
workspace[1] = r; |
|||
*term = q; |
|||
} |
|||
} |
|||
generator_t |
|||
r2cf_make (integer n, integer d) |
|||
{ |
|||
generator_t gen = MALLOC (sizeof (*gen)); |
|||
gen->run = r2cf_run; |
|||
gen->worksize = 2; |
|||
gen->initial = MALLOC (gen->worksize * sizeof (integer)); |
|||
gen->workspace = MALLOC (gen->worksize * sizeof (integer)); |
|||
gen->initial[0] = n; |
|||
gen->initial[1] = d; |
|||
memcpy (gen->workspace, gen->initial, |
|||
gen->worksize * sizeof (integer)); |
|||
gen->sources = NULL; |
|||
return gen; |
|||
} |
|||
/* - - - - - - - - - - - - - */ |
|||
static void |
|||
sqrt2_run (integer *workspace, |
|||
[[maybe_unused]] generator_list_t sources, |
|||
bool *term_exists, integer *term) |
|||
{ |
|||
*term_exists = true; |
|||
*term = workspace[0]; |
|||
workspace[0] = 2; |
|||
} |
|||
generator_t |
|||
sqrt2_make (void) |
|||
{ |
|||
generator_t gen = MALLOC (sizeof (*gen)); |
|||
gen->run = sqrt2_run; |
|||
gen->worksize = 1; |
|||
gen->initial = MALLOC (gen->worksize * sizeof (integer)); |
|||
gen->workspace = MALLOC (gen->worksize * sizeof (integer)); |
|||
gen->initial[0] = 1; |
|||
memcpy (gen->workspace, gen->initial, |
|||
gen->worksize * sizeof (integer)); |
|||
gen->sources = NULL; |
|||
return gen; |
|||
} |
|||
/* - - - - - - - - - - - - - */ |
|||
static void |
|||
hfunc_take_term (integer *workspace, generator_list_t sources) |
|||
{ |
|||
generator_t src = sources->car; |
|||
bool term_exists1; |
|||
integer term1; |
|||
src->run (src->workspace, src->sources, &term_exists1, &term1); |
|||
integer a1 = workspace[0]; |
|||
integer b1 = workspace[2]; |
|||
if (term_exists1) |
|||
{ |
|||
integer a = workspace[1]; |
|||
integer b = workspace[3]; |
|||
workspace[0] = a + (a1 * term1); |
|||
workspace[1] = a1; |
|||
workspace[2] = b + (b1 * term1); |
|||
workspace[3] = b1; |
|||
} |
|||
else |
|||
{ |
|||
workspace[1] = a1; |
|||
workspace[3] = b1; |
|||
} |
|||
} |
|||
static void |
|||
hfunc_run (integer *workspace, generator_list_t sources, |
|||
bool *term_exists, integer *term) |
|||
{ |
|||
bool done = false; |
|||
while (!done) |
|||
{ |
|||
integer b1 = workspace[2]; |
|||
integer b = workspace[3]; |
|||
if (b1 == 0 && b == 0) |
|||
{ |
|||
*term_exists = false; |
|||
done = true; |
|||
} |
|||
else |
|||
{ |
|||
integer a1 = workspace[0]; |
|||
integer a = workspace[1]; |
|||
if (b1 != 0 && b != 0) |
|||
{ |
|||
integer q1 = DIV (a1, b1); |
|||
integer q = DIV (a, b); |
|||
if (q1 == q) |
|||
{ |
|||
workspace[0] = b1; |
|||
workspace[1] = b; |
|||
workspace[2] = a1 - (b1 * q); |
|||
workspace[3] = a - (b * q); |
|||
*term_exists = true; |
|||
*term = q; |
|||
done = true; |
|||
} |
|||
else |
|||
hfunc_take_term (workspace, sources); |
|||
} |
|||
else |
|||
hfunc_take_term (workspace, sources); |
|||
} |
|||
} |
|||
} |
|||
generator_t |
|||
hfunc_make (integer a1, integer a, integer b1, integer b, |
|||
generator_t source) |
|||
{ |
|||
generator_t gen = MALLOC (sizeof (*gen)); |
|||
gen->run = hfunc_run; |
|||
gen->worksize = 4; |
|||
gen->initial = MALLOC (gen->worksize * sizeof (integer)); |
|||
gen->workspace = MALLOC (gen->worksize * sizeof (integer)); |
|||
gen->initial[0] = a1; |
|||
gen->initial[1] = a; |
|||
gen->initial[2] = b1; |
|||
gen->initial[3] = b; |
|||
memcpy (gen->workspace, gen->initial, |
|||
gen->worksize * sizeof (integer)); |
|||
gen->sources = MALLOC (sizeof (struct generator_list)); |
|||
gen->sources->car = source; |
|||
gen->sources->cdr = NULL; |
|||
return gen; |
|||
} |
|||
/*------------------------------------------------------------------*/ |
|||
/* Components of the demonstration. */ |
|||
#define MAX_TERMS 20 |
|||
#define GOES_TO " ~ -> ~ " |
|||
#define START_EQ ".EQ\n" |
|||
#define STOP_EQ "\n.EN\n" |
|||
#define NEW_LINE "\n" |
|||
void |
|||
ftroff_rational_number (FILE *outf, integer n, integer d) |
|||
{ |
|||
generator_t gen = r2cf_make (n, d); |
|||
fprintf (outf, "%s %jd over %jd %s", |
|||
START_EQ, (intmax_t) n, (intmax_t) d, GOES_TO); |
|||
ftroff_generator_output (outf, gen, MAX_TERMS); |
|||
fprintf (outf, "%s%s", STOP_EQ, NEW_LINE); |
|||
generator_t_free (gen); |
|||
} |
|||
void |
|||
ftroff_sqrt2 (FILE *outf) |
|||
{ |
|||
generator_t gen = sqrt2_make (); |
|||
fprintf (outf, "%s sqrt 2 %s", START_EQ, GOES_TO); |
|||
ftroff_generator_output (outf, gen, MAX_TERMS); |
|||
fprintf (outf, "%s%s", STOP_EQ, NEW_LINE); |
|||
generator_t_free (gen); |
|||
} |
|||
void |
|||
ftroff_hfunc_of_rational_number (FILE *outf, |
|||
const char *expr, |
|||
integer a1, integer a, |
|||
integer b1, integer b, |
|||
integer n, integer d) |
|||
{ |
|||
generator_t gen = hfunc_make (a1, a, b1, b, r2cf_make (n, d)); |
|||
fprintf (outf, "%s %s %s", START_EQ, expr, GOES_TO); |
|||
ftroff_generator_output (outf, gen, MAX_TERMS); |
|||
fprintf (outf, "%s%s", STOP_EQ, NEW_LINE); |
|||
generator_t_free (gen); |
|||
} |
|||
void |
|||
ftroff_hfunc_of_sqrt2 (FILE *outf, const char *expr, |
|||
integer a1, integer a, integer b1, integer b) |
|||
{ |
|||
generator_t gen = hfunc_make (a1, a, b1, b, sqrt2_make ()); |
|||
fprintf (outf, "%s %s %s", START_EQ, expr, GOES_TO); |
|||
ftroff_generator_output (outf, gen, MAX_TERMS); |
|||
fprintf (outf, "%s%s", STOP_EQ, NEW_LINE); |
|||
generator_t_free (gen); |
|||
} |
|||
void |
|||
ftroff_complicated (FILE *outf) |
|||
{ |
|||
/* This function demonstrates a more complicated nesting of |
|||
generators. */ |
|||
/* gen1 = 1/sqrt(2) */ |
|||
generator_t gen1 = hfunc_make (0, 1, 1, 0, sqrt2_make ()); |
|||
/* gen2 = 1 + gen1 */ |
|||
generator_t gen2 = hfunc_make (1, 1, 0, 1, gen1); |
|||
/* gen = gen2 / 2 */ |
|||
generator_t gen = hfunc_make (1, 0, 0, 2, gen2); |
|||
fprintf (outf, "%s {1 ~ + ~ { 1 over { sqrt 2 } }} over 2 %s", |
|||
START_EQ, GOES_TO); |
|||
ftroff_generator_output (outf, gen, MAX_TERMS); |
|||
fprintf (outf, "%s%s", STOP_EQ, NEW_LINE); |
|||
generator_t_free (gen); |
|||
} |
|||
/*------------------------------------------------------------------*/ |
|||
int |
|||
main (void) |
|||
{ |
|||
MALLOC_INIT (); |
|||
FILE *outf = stdout; |
|||
/* Output is for "eqn -Tpdf | groff -Tpdf -P-p6i,5.5i -ms" */ |
|||
fprintf (outf, ".nr PO 0.25i\n"); |
|||
fprintf (outf, ".nr HM 0.25i\n"); |
|||
fprintf (outf, ".ps 14\n"); |
|||
ftroff_rational_number (outf, 13, 11); |
|||
ftroff_rational_number (outf, 22, 7); |
|||
ftroff_sqrt2 (outf); |
|||
ftroff_hfunc_of_rational_number |
|||
(outf, "{ 13 over 11 } ~ + ~ { 1 over 2 }", |
|||
2, 1, 0, 2, 13, 11); |
|||
ftroff_hfunc_of_rational_number |
|||
(outf, "{ 22 over 7 } ~ + ~ { 1 over 2 }", |
|||
2, 1, 0, 2, 22, 7); |
|||
ftroff_hfunc_of_rational_number |
|||
(outf, "{ ^ {\"\\s-3\" 22 over 7 \"\\s+3\"}} over 4", |
|||
1, 0, 0, 4, 22, 7); |
|||
ftroff_hfunc_of_sqrt2 |
|||
(outf, "{ sqrt 2 } over 2", 1, 0, 0, 2); |
|||
ftroff_hfunc_of_sqrt2 |
|||
(outf, "1 over { sqrt 2 }", 0, 1, 1, 0); |
|||
ftroff_hfunc_of_sqrt2 |
|||
(outf, "{ 2 ~ + ~ { sqrt 2 }} over 4", 1, 2, 0, 4); |
|||
ftroff_complicated (outf); |
|||
return 0; |
|||
} |
|||
/*------------------------------------------------------------------*/ |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
Run something like the following: |
|||
<pre> |
|||
$ cc -Wall -Wextra -g -std=gnu2x univariate-continued-fraction-task-no-gc.c && ./a.out | eqn -Tpdf | groff -Tpdf -P-p6i,5.5i -ms > foo.pdf |
|||
$ okular foo.pdf |
|||
</pre> |
|||
In place of okular, you can use your favorite PDF viewer. To make the PNG, I used ImageMagick and ran: |
|||
<pre>$ convert -flatten -quality 0 foo.pdf foo.png</pre> |
|||
[[File:Univariate-continued-fraction-task-no-gc.c.png|alt=The output of the C program that uses no garbage collector, as rendered by groff.]] |
|||
=={{header|C++}}== |
=={{header|C++}}== |