1/2
1/3 2/3
1/4 3/4 2/5 3/5
1/5 4/5 3/7 4/7 2/7 5/7 3/8 5/8
1/6 5/6 4/9 5/9 3/10 7/10 4/11 7/11 2/9 7/9 5/12 7/12 3/11 8/11 5/13 8/13
1/7 6/7 5/11 6/11 4/13 9/13 5/14 9/14 3/13 10/13 7/17 10/17 4/15 11/15 7/18 11/18 2/11 9/11 7/16 9/16 5/17 12/17 7/19 ...
...
All the fraction in each row of the Stern-Brocot tree can be viewed like coordinates in a matrix(row/column).
For the generation of the Stern-Brocot tree can be used a method that produce the Farey fraction but not in ascending order(see[1]). If we visit the Stern-Brocot tree by rows we obtain at the end of each row a complete set of the Farey sequence. In this way, at the end of the n'th row we obtained {Fn}. Some of the fractions with the denomitor equal to n are stored above in the Stern-Brocot tree.
This is the ideea of the representation of the sparse/rare matrix using the Stern-Brocot tree.
Starting from the fraction 1/1 we can associate to each fraction a binary code; left = = 0, right = = 1.
If a sparse/rare matrtix contain a non-zero value on the position (x,y), we can associate for this position two decimal numbers obtained by the binary code described above - spliting the code by half. Let's note the code by z; than in some cases, z will be smaller than the binary representation of x and of y .
A better representation of a sparse/rare matrix than the classic method - storing a compact memory space - use dynamic memory - circular dynamic lists. In these lists are memo some values related to the next row and column in which is stored a non-zero value.
Let's take an example, the matix:
0 1 0 6 0
0 0 0 1 0
4 0 9 0 0
0 0 0 0 0
0 13 0 2 0
0 0 0 0 1
The positions (1, 4) - "0 0"and (5, 2) "11 01" (starting from 1/1) can be optimized like described above to (0, 0), (3, 1).
When allocating the nodes in the circular dynamic lists, these two nodes can use an other struct definition for the node: for the type of the row and column to use less bits - memo only one byte: the decimal representation of "1"+z .
(*) The codes obtained from the Stern-Brocot tree, are smaller than x and y only for the values of the interior of the tree - in general the values that do not appear in {Fn}.
References:
Pages maintained by Mr. Alexander Bogomolny :
1) http://www.cut-the-knot.org/blue/b-tree.shtml
2) http://www.cut-the-knot.org/blue/Stern.shtml
2) http://www.cut-the-knot.org/blue/encoding.shtml
3) http://www.cut-the-knot.org/blue/chaos_game.shtml
/************************************************************************************
Program that generates all the fractions from a level "h", of the Stern-Brocot Tree @ For a detailed description of the algorithm, please visit the site: @ http://www.cut-the-knot.org/blue/b-tree.shtml ************************************************************************************/
/************************************************************************************INCLUDES************************************************************************************/# include "stdio.h"# include "malloc.h"# include "math.h"
/************************************************************************************TYPES & VARIABLES************************************************************************************/
typedef unsigned long int UL_int;typedef unsigned char ui8_t;
UL_int h;
struct nod{ UL_int num,den; struct nod * s, * d;};
typedef struct nod NOD;
NOD * rad;
/* Output file wich stores the optimized positions */FILE * pf;
/* Variables that store the number of nodes */UL_int N, c_init;/* Variable that stores the number of optimized positions */UL_int c_opt;
/************************************************************************************FUNCTIONS************************************************************************************/
/*----------------------------------------------------*//* Functions for comparing the binary representations *//*----------------------------------------------------*/
ui8_t BIN_comp(UL_int a, UL_int b, UL_int h){ UL_int nr_cif_a, nr_cif_b; nr_cif_a = (UL_int) (log(a)/log(2.0)) + 1; nr_cif_b = (UL_int) (log(b)/log(2.0)) + 1; if(ceil((nr_cif_a + nr_cif_b)/8.0)+ 1 > ceil((h-2)/8.0) + 1) return 1; else return 0;}
/*----------------------------------------------------------------------*//* Function for the generation of the Stern-Brocot tree with "h" levels *//*----------------------------------------------------------------------*/
NOD * SB_tree(NOD * r, UL_int x, UL_int y, UL_int c){ NOD * p, * q; if(c==h-1) { /* Print all the fractions from a read level */ printf("%lu/%lu ",r->num,r->den); /* Check for optimized position */ if(BIN_comp(r->num,r->den,h) == 1) { c_opt++; fprintf(pf,"%lu/%lu\n",r->num,r->den); } return r; } else { p =(NOD *)malloc(sizeof(NOD)); p->s = NULL; p->d = NULL; p->num = x; p->den = x+y; r->s = SB_tree(p,x,x+y,c+1); q =(NOD *)malloc(sizeof(NOD)); q->s = NULL; q->d = NULL; q->num = y; q->den = x+y; r->d = SB_tree(q,y,x+y,c+1); }}
/************************************************************************************MAIN ()************************************************************************************/
void main(void){ pf=fopen("out.txt","w+"); /* Read the level */ printf("Enter the level in the tree: "); scanf("%lu",&h); /* The root is treated separatly */ rad =(NOD *)malloc(sizeof(NOD)); rad->s = NULL; rad->d = NULL; rad->num = 1; rad->den = 2; /* Generation of the STERN-BROCOT tree fractions */ /* http://www.cut-the-knot.org/blue/b-tree.shtml */ c_init = 1; SB_tree(rad,1,2,c_init); /* Print the number of optimised positions */ N = (UL_int) pow(2,h); printf("\nThe number of optimised positions is: %lu / %lu", c_opt, N); printf("\nPercent = %.2f %% optimised",(c_opt*100/(float)N));
fclose(pf);}/************************************************************************************END************************************************************************************/
/********************************************************************************************************************************************************************************/
/************************************************************************************INCLUDES************************************************************************************/
# include "stdio.h"
# include "malloc.h"
# include "math.h"
# include "conio.h"
/************************************************************************************TYPES & VARIABLES************************************************************************************/
typedef unsigned __int64 UL_int;
typedef unsigned char ui8_t;
UL_int h;
struct nod{ UL_int num,den; struct nod * s, * d;};
typedef struct nod NOD;
NOD * rad;
/* Output file wich stores the optimized positions */
FILE * pf;
/* Variables that store the number of nodes */
UL_int N, c_init;
/* Variable that stores the number of optimized positions */
UL_int c_opt;
/************************************************************************************FUNCTIONS************************************************************************************/
/*----------------------------------------------------*//* Functions for comparing the binary representations *//*----------------------------------------------------*/
ui8_t BIN_comp(UL_int a, UL_int b, UL_int h)
{
UL_int nr_cif_a, nr_cif_b;
nr_cif_a = (UL_int) (log(a)/log(2.0)) + 1;
nr_cif_b = (UL_int) (log(b)/log(2.0)) + 1;
if(ceil((nr_cif_a + nr_cif_b)/8.0)+ 1 > ceil((h-2)/8.0) + 1)
return 1;
else
return 0;
}
/*----------------------------------------------------------------------*//* Function for the generation of the Stern-Brocot tree with "h" levels *//*----------------------------------------------------------------------*/
NOD * SB_tree(NOD * r, UL_int x, UL_int y, UL_int c)
{
NOD * p, * q;
if(c==h-1)
{ /* Print all the fractions from a read level */
//printf("%lu/%lu ",r->num,r->den);
/* Check for optimized position */
if(BIN_comp(r->num,r->den,h) == 1)
{
c_opt++;
//fprintf(pf,"%lu/%lu\n",r->num,r->den);
}
return r;
}
else
{
p =(NOD *)malloc(sizeof(NOD));
p->s = NULL;
p->d = NULL;
p->num = x;
p->den = x+y;
r->s = SB_tree(p,x,x+y,c+1);
q =(NOD *)malloc(sizeof(NOD));
q->s = NULL;
q->d = NULL;
q->num = y;
q->den = x+y;
r->d = SB_tree(q,y,x+y,c+1);
}
}
/************************************************************************************MAIN ()************************************************************************************/
int main(void)
{
pf=fopen("out.txt","w+");
/* Read the level */
printf("Enter the level in the tree: ");
scanf("%llu",&h);
/* The root is treated separatly */
rad =(NOD *)malloc(sizeof(NOD));
rad->s = NULL;
rad->d = NULL;
rad->num = 1;
rad->den = 2;
/* Generation of the STERN-BROCOT tree fractions */ /* http://www.cut-the-knot.org/blue/b-tree.shtml */
c_init = 1;
SB_tree(rad,1,2,c_init);
/* Print the number of optimised positions */
N = (UL_int) pow(2,h);
printf("\nThe number of optimised positions is: %llu / %llu", c_opt, N);
printf("\nPercent = %.2f %% optimised",(c_opt*100/(float)N));
fclose(pf);
getche();
return 1;
}
/************************************************************************************END************************************************************************************/
No comments:
Post a Comment