diff options
author | erdgeist <de@gsmk.de> | 2014-10-06 22:29:11 +0200 |
---|---|---|
committer | erdgeist <de@gsmk.de> | 2014-10-06 22:29:11 +0200 |
commit | 7214d06d2d54dcfa770dd98e902a0397f208aec3 (patch) | |
tree | e2bedf6cba24818ae79ed4352a386b5aa6005d12 /generate_table.c | |
parent | 2e57ec4405b2c52b48820aff75cd6d18efe2fc47 (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.
Diffstat (limited to 'generate_table.c')
-rw-r--r-- | generate_table.c | 71 |
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 | ||
9 | typedef enum { use_2pn, use_1_2pn, use_2pm_2pn, use_1_2pm_2pn } tr_flag; | 6 | typedef enum { use_2pn, use_1_2pn, use_2pm_2pn, use_1_2pm_2pn } tr_flag; |
10 | typedef struct { | 7 | typedef struct { |
@@ -16,6 +13,7 @@ typedef struct { | |||
16 | } table_record; | 13 | } table_record; |
17 | 14 | ||
18 | static int g_records; | 15 | static int g_records; |
16 | static int g_null; | ||
19 | static table_record g_tr[8192]; | 17 | static table_record g_tr[8192]; |
20 | 18 | ||
21 | static int compare_record( const void *a, const void *b ) { | 19 | static 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 | ||
27 | static 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 | |||
29 | static void add_record( double v, int n, int nsign, int m, tr_flag flag ) | 35 | static 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 | ||
68 | static 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 | |||
62 | int main() { | 95 | int 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 | } |