From 7214d06d2d54dcfa770dd98e902a0397f208aec3 Mon Sep 17 00:00:00 2001
From: erdgeist <de@gsmk.de>
Date: Mon, 6 Oct 2014 22:29:11 +0200
Subject: 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.

---
 generate_table.c | 71 +++++++++++++++++++++++++++++++++++++++++++++++++++-----
 1 file 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 @@
 #include <math.h>
 #include <stdio.h>
 #include <stdlib.h>
-
-// s(-1) n(14) off(+1)   x =   x - ( x >> 14 )
-// s( 1) n(-4) off( 0)   x =       ( x <<  4 )
-// s( 1) n( 8) off(-1)   x = - x + ( x <<  8 )
+#include <string.h>
 
 typedef enum { use_2pn, use_1_2pn, use_2pm_2pn, use_1_2pm_2pn } tr_flag;
 typedef struct {
@@ -16,6 +13,7 @@ typedef struct {
 } table_record;
 
 static int g_records;
+static int g_null;
 static table_record g_tr[8192];
 
 static int compare_record( const void *a, const void *b ) {
@@ -26,6 +24,14 @@ static int compare_record( const void *a, const void *b ) {
   return 0;
 }
 
+static int get_record_score( int record )
+{
+  switch( g_tr[record].flag ) {
+  case use_2pn: case use_1_2pn: return 3;
+  default: return 4;
+  }
+}
+
 static void add_record( double v, int n, int nsign, int m, tr_flag flag )
 {
     g_tr[g_records].factor = v;
@@ -59,11 +65,38 @@ static void dump_record( int record )
   }
 }
 
+static void find_tail( int off, int record, int score ) {
+  static int trail[10240];
+  int i;
+// printf( "%d %d %d\n", off, record, score );
+  trail[off] = record;
+
+  // My naive implementation found a solution with score 51
+  // Don't look deeper when it's worse
+  if( score > 54 ) return;
+
+  if( g_tr[record].factor >= -0.0001220703125 ) {
+    printf( "%d\n", score );
+    for( i=0; i<=off; ++i)
+        dump_record( trail[i] );
+    return;
+  }
+
+  for( i = record + 1; i < g_null; ++i )
+    if( ( g_tr[record].factor / g_tr[i].factor < 2.0 ) && ( g_tr[record].factor / g_tr[i].factor >= 1.6 ) )
+      find_tail( off + 1, i, get_record_score( record ) + score );
+
+  // Retry each entry once
+  if( off && ( trail[off-1] != record ) )
+    find_tail( off+1, record, get_record_score( record ) + score );
+
+};
+
 int main() {
   int n, m, nsign;
 
   // loop over all constructs in the form +-1*x^+-2n, n=-31..+31
-  for (n=-31; n<= 31; ++n )
+  for (n=-21; n<= 21; ++n )
     for ( nsign=-1; nsign<=1; nsign+=2 )
     {
       // The one term only case
@@ -72,7 +105,7 @@ int main() {
           add_record( log(v), n, nsign, m, use_2pn );
 
       // Loop over second term
-      for (m=-31; m<=31; ++m )
+      for (m=-13; m<=13; ++m )
       {
         double v = pow( 2.0, (double)m ) + (double)nsign * pow( 2., (double)n );
         if( v <= 0.0 )
@@ -83,10 +116,36 @@ int main() {
       }
     }
 
+  // sort records by value
   qsort( g_tr, g_records, sizeof(*g_tr), compare_record );
 
+  printf( "All potential solutions:\n" );
   for (n=0; n<g_records; ++n )
     dump_record(n);
 
+  printf( "Now looking for the optima of the algorithm for negative exp().\nThis can take a while... \n" );
+
+  // Remove redundant entries
+  for (n=1; n<g_records; ++n ) {
+    if (fabs(g_tr[n].factor) / fabs(g_tr[n-1].factor) > 0.999 ) {
+      if (g_tr[n-1].flag == use_2pn || g_tr[n-1].flag == use_1_2pn || g_tr[n].factor > 0.0 )
+        memmove(g_tr+n,g_tr+n+1,(g_records-n-1)*sizeof(*g_tr));
+      else
+        memmove(g_tr+n-1,g_tr+n,(g_records-n-1)*sizeof(*g_tr));
+      --g_records; --n;
+    }
+  }
+
+  for (g_null=0; g_tr[g_null].factor <= 0.0; ++g_null);
+
+  // Now find all paths through factors ensuring that the gap between two
+  // steps is not larger than factor 2.0
+  // Tail terminates when we reach 0.0001220703125 and prints results
+
+  for (n=0; n<g_records; ++n ) {
+    if (g_tr[n].factor <= -0.693 && g_tr[n].factor >= -0.694 )
+        find_tail( 0, n, 0);
+  }
+
   return 0;
 }
-- 
cgit v1.2.3