summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorerdgeist <de@gsmk.de>2014-10-06 22:29:11 +0200
committererdgeist <de@gsmk.de>2014-10-06 22:29:11 +0200
commit7214d06d2d54dcfa770dd98e902a0397f208aec3 (patch)
treee2bedf6cba24818ae79ed4352a386b5aa6005d12
parent2e57ec4405b2c52b48820aff75cd6d18efe2fc47 (diff)
Add code to look for an optimal solution for negative parameters to exp() ... turns out, the naive solution had the same score as all the other optima.
-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}