summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--generate_table.c71
1 files changed, 65 insertions, 6 deletions
diff --git a/generate_table.c b/generate_table.c
index 9fd05bc..85711ce 100644
--- a/generate_table.c
+++ b/generate_table.c
@@ -1,10 +1,7 @@
1#include <math.h> 1#include <math.h>
2#include <stdio.h> 2#include <stdio.h>
3#include <stdlib.h> 3#include <stdlib.h>
4 4#include <string.h>
5// s(-1) n(14) off(+1) x = x - ( x >> 14 )
6// s( 1) n(-4) off( 0) x = ( x << 4 )
7// s( 1) n( 8) off(-1) x = - x + ( x << 8 )
8 5
9typedef enum { use_2pn, use_1_2pn, use_2pm_2pn, use_1_2pm_2pn } tr_flag; 6typedef enum { use_2pn, use_1_2pn, use_2pm_2pn, use_1_2pm_2pn } tr_flag;
10typedef struct { 7typedef struct {
@@ -16,6 +13,7 @@ typedef struct {
16} table_record; 13} table_record;
17 14
18static int g_records; 15static int g_records;
16static int g_null;
19static table_record g_tr[8192]; 17static table_record g_tr[8192];
20 18
21static int compare_record( const void *a, const void *b ) { 19static int compare_record( const void *a, const void *b ) {
@@ -26,6 +24,14 @@ static int compare_record( const void *a, const void *b ) {
26 return 0; 24 return 0;
27} 25}
28 26
27static int get_record_score( int record )
28{
29 switch( g_tr[record].flag ) {
30 case use_2pn: case use_1_2pn: return 3;
31 default: return 4;
32 }
33}
34
29static void add_record( double v, int n, int nsign, int m, tr_flag flag ) 35static void add_record( double v, int n, int nsign, int m, tr_flag flag )
30{ 36{
31 g_tr[g_records].factor = v; 37 g_tr[g_records].factor = v;
@@ -59,11 +65,38 @@ static void dump_record( int record )
59 } 65 }
60} 66}
61 67
68static void find_tail( int off, int record, int score ) {
69 static int trail[10240];
70 int i;
71// printf( "%d %d %d\n", off, record, score );
72 trail[off] = record;
73
74 // My naive implementation found a solution with score 51
75 // Don't look deeper when it's worse
76 if( score > 54 ) return;
77
78 if( g_tr[record].factor >= -0.0001220703125 ) {
79 printf( "%d\n", score );
80 for( i=0; i<=off; ++i)
81 dump_record( trail[i] );
82 return;
83 }
84
85 for( i = record + 1; i < g_null; ++i )
86 if( ( g_tr[record].factor / g_tr[i].factor < 2.0 ) && ( g_tr[record].factor / g_tr[i].factor >= 1.6 ) )
87 find_tail( off + 1, i, get_record_score( record ) + score );
88
89 // Retry each entry once
90 if( off && ( trail[off-1] != record ) )
91 find_tail( off+1, record, get_record_score( record ) + score );
92
93};
94
62int main() { 95int main() {
63 int n, m, nsign; 96 int n, m, nsign;
64 97
65 // loop over all constructs in the form +-1*x^+-2n, n=-31..+31 98 // loop over all constructs in the form +-1*x^+-2n, n=-31..+31
66 for (n=-31; n<= 31; ++n ) 99 for (n=-21; n<= 21; ++n )
67 for ( nsign=-1; nsign<=1; nsign+=2 ) 100 for ( nsign=-1; nsign<=1; nsign+=2 )
68 { 101 {
69 // The one term only case 102 // The one term only case
@@ -72,7 +105,7 @@ int main() {
72 add_record( log(v), n, nsign, m, use_2pn ); 105 add_record( log(v), n, nsign, m, use_2pn );
73 106
74 // Loop over second term 107 // Loop over second term
75 for (m=-31; m<=31; ++m ) 108 for (m=-13; m<=13; ++m )
76 { 109 {
77 double v = pow( 2.0, (double)m ) + (double)nsign * pow( 2., (double)n ); 110 double v = pow( 2.0, (double)m ) + (double)nsign * pow( 2., (double)n );
78 if( v <= 0.0 ) 111 if( v <= 0.0 )
@@ -83,10 +116,36 @@ int main() {
83 } 116 }
84 } 117 }
85 118
119 // sort records by value
86 qsort( g_tr, g_records, sizeof(*g_tr), compare_record ); 120 qsort( g_tr, g_records, sizeof(*g_tr), compare_record );
87 121
122 printf( "All potential solutions:\n" );
88 for (n=0; n<g_records; ++n ) 123 for (n=0; n<g_records; ++n )
89 dump_record(n); 124 dump_record(n);
90 125
126 printf( "Now looking for the optima of the algorithm for negative exp().\nThis can take a while... \n" );
127
128 // Remove redundant entries
129 for (n=1; n<g_records; ++n ) {
130 if (fabs(g_tr[n].factor) / fabs(g_tr[n-1].factor) > 0.999 ) {
131 if (g_tr[n-1].flag == use_2pn || g_tr[n-1].flag == use_1_2pn || g_tr[n].factor > 0.0 )
132 memmove(g_tr+n,g_tr+n+1,(g_records-n-1)*sizeof(*g_tr));
133 else
134 memmove(g_tr+n-1,g_tr+n,(g_records-n-1)*sizeof(*g_tr));
135 --g_records; --n;
136 }
137 }
138
139 for (g_null=0; g_tr[g_null].factor <= 0.0; ++g_null);
140
141 // Now find all paths through factors ensuring that the gap between two
142 // steps is not larger than factor 2.0
143 // Tail terminates when we reach 0.0001220703125 and prints results
144
145 for (n=0; n<g_records; ++n ) {
146 if (g_tr[n].factor <= -0.693 && g_tr[n].factor >= -0.694 )
147 find_tail( 0, n, 0);
148 }
149
91 return 0; 150 return 0;
92} 151}