src/integer/conv/cl_I_cached_power.cc

   1 // cached_power().\r
   2 \r
   3 // Specification.\r
   4 #include "cl_I_cached_power.h"\r
   5 \r
   6 \r
   7 // Implementation.\r
   8 \r
   9 namespace cln {\r
  10 \r
  11 const power_table_entry power_table [36-2+1] = {\r
  12 #if (intDsize==8)\r
  13         { 7, 2*2*2*2*2*2*2 },\r
  14         { 5, 3*3*3*3*3 },\r
  15         { 3, 4*4*4 },\r
  16         { 3, 5*5*5 },\r
  17         { 3, 6*6*6 },\r
  18         { 2, 7*7 },\r
  19         { 2, 8*8 },\r
  20         { 2, 9*9 },\r
  21         { 2, 10*10 },\r
  22         { 2, 11*11 },\r
  23         { 2, 12*12 },\r
  24         { 2, 13*13 },\r
  25         { 2, 14*14 },\r
  26         { 2, 15*15 },\r
  27         { 1, 16 },\r
  28         { 1, 17 },\r
  29         { 1, 18 },\r
  30         { 1, 19 },\r
  31         { 1, 20 },\r
  32         { 1, 21 },\r
  33         { 1, 22 },\r
  34         { 1, 23 },\r
  35         { 1, 24 },\r
  36         { 1, 25 },\r
  37         { 1, 26 },\r
  38         { 1, 27 },\r
  39         { 1, 28 },\r
  40         { 1, 29 },\r
  41         { 1, 30 },\r
  42         { 1, 31 },\r
  43         { 1, 32 },\r
  44         { 1, 33 },\r
  45         { 1, 34 },\r
  46         { 1, 35 },\r
  47         { 1, 36 },\r
  48 #endif\r
  49 #if (intDsize==16)\r
  50         { 15, 2*2*2*2*2*2*2*2*2*2*2*2*2*2*2 },\r
  51         { 10, 3*3*3*3*3*3*3*3*3*3 },\r
  52         {  7, 4*4*4*4*4*4*4 },\r
  53         {  6, 5*5*5*5*5*5 },\r
  54         {  6, 6*6*6*6*6*6 },\r
  55         {  5, 7*7*7*7*7 },\r
  56         {  5, 8*8*8*8*8 },\r
  57         {  5, 9*9*9*9*9 },\r
  58         {  4, 10*10*10*10 },\r
  59         {  4, 11*11*11*11 },\r
  60         {  4, 12*12*12*12 },\r
  61         {  4, 13*13*13*13 },\r
  62         {  4, 14*14*14*14 },\r
  63         {  4, 15*15*15*15 },\r
  64         {  3, 16*16*16 },\r
  65         {  3, 17*17*17 },\r
  66         {  3, 18*18*18 },\r
  67         {  3, 19*19*19 },\r
  68         {  3, 20*20*20 },\r
  69         {  3, 21*21*21 },\r
  70         {  3, 22*22*22 },\r
  71         {  3, 23*23*23 },\r
  72         {  3, 24*24*24 },\r
  73         {  3, 25*25*25 },\r
  74         {  3, 26*26*26 },\r
  75         {  3, 27*27*27 },\r
  76         {  3, 28*28*28 },\r
  77         {  3, 29*29*29 },\r
  78         {  3, 30*30*30 },\r
  79         {  3, 31*31*31 },\r
  80         {  3, 32*32*32 },\r
  81         {  3, 33*33*33 },\r
  82         {  3, 34*34*34 },\r
  83         {  3, 35*35*35 },\r
  84         {  3, 36*36*36 },\r
  85 #endif\r
  86 #if (intDsize==32)\r
  87         { 31, 2UL*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2 },\r
  88         { 20, 3UL*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3 },\r
  89         { 15, 4UL*4*4*4*4*4*4*4*4*4*4*4*4*4*4 },\r
  90         { 13, 5UL*5*5*5*5*5*5*5*5*5*5*5*5 },\r
  91         { 12, 6UL*6*6*6*6*6*6*6*6*6*6*6 },\r
  92         { 11, 7UL*7*7*7*7*7*7*7*7*7*7 },\r
  93         { 10, 8UL*8*8*8*8*8*8*8*8*8 },\r
  94         { 10, 9UL*9*9*9*9*9*9*9*9*9 },\r
  95         {  9, 10UL*10*10*10*10*10*10*10*10 },\r
  96         {  9, 11UL*11*11*11*11*11*11*11*11 },\r
  97         {  8, 12UL*12*12*12*12*12*12*12 },\r
  98         {  8, 13UL*13*13*13*13*13*13*13 },\r
  99         {  8, 14UL*14*14*14*14*14*14*14 },\r
 100         {  8, 15UL*15*15*15*15*15*15*15 },\r
 101         {  7, 16UL*16*16*16*16*16*16 },\r
 102         {  7, 17UL*17*17*17*17*17*17 },\r
 103         {  7, 18UL*18*18*18*18*18*18 },\r
 104         {  7, 19UL*19*19*19*19*19*19 },\r
 105         {  7, 20UL*20*20*20*20*20*20 },\r
 106         {  7, 21UL*21*21*21*21*21*21 },\r
 107         {  7, 22UL*22*22*22*22*22*22 },\r
 108         {  7, 23UL*23*23*23*23*23*23 },\r
 109         {  6, 24UL*24*24*24*24*24 },\r
 110         {  6, 25UL*25*25*25*25*25 },\r
 111         {  6, 26UL*26*26*26*26*26 },\r
 112         {  6, 27UL*27*27*27*27*27 },\r
 113         {  6, 28UL*28*28*28*28*28 },\r
 114         {  6, 29UL*29*29*29*29*29 },\r
 115         {  6, 30UL*30*30*30*30*30 },\r
 116         {  6, 31UL*31*31*31*31*31 },\r
 117         {  6, 32UL*32*32*32*32*32 },\r
 118         {  6, 33UL*33*33*33*33*33 },\r
 119         {  6, 34UL*34*34*34*34*34 },\r
 120         {  6, 35UL*35*35*35*35*35 },\r
 121         {  6, 36UL*36*36*36*36*36 },\r
 122 #endif\r
 123 #if (intDsize==64)\r
 124         { 63, 2ULL*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2 },\r
 125         { 40, 3ULL*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3*3 },\r
 126         { 31, 4ULL*4*4*4*4*4*4*4*4*4*4*4*4*4*4*4*4*4*4*4*4*4*4*4*4*4*4*4*4*4*4 },\r
 127         { 27, 5ULL*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5*5 },\r
 128         { 24, 6ULL*6*6*6*6*6*6*6*6*6*6*6*6*6*6*6*6*6*6*6*6*6*6*6 },\r
 129         { 22, 7ULL*7*7*7*7*7*7*7*7*7*7*7*7*7*7*7*7*7*7*7*7*7 },\r
 130         { 21, 8ULL*8*8*8*8*8*8*8*8*8*8*8*8*8*8*8*8*8*8*8*8 },\r
 131         { 20, 9ULL*9*9*9*9*9*9*9*9*9*9*9*9*9*9*9*9*9*9*9 },\r
 132         { 19, 10ULL*10*10*10*10*10*10*10*10*10*10*10*10*10*10*10*10*10*10 },\r
 133         { 18, 11ULL*11*11*11*11*11*11*11*11*11*11*11*11*11*11*11*11*11 },\r
 134         { 17, 12ULL*12*12*12*12*12*12*12*12*12*12*12*12*12*12*12*12 },\r
 135         { 17, 13ULL*13*13*13*13*13*13*13*13*13*13*13*13*13*13*13*13 },\r
 136         { 16, 14ULL*14*14*14*14*14*14*14*14*14*14*14*14*14*14*14 },\r
 137         { 16, 15ULL*15*15*15*15*15*15*15*15*15*15*15*15*15*15*15 },\r
 138         { 15, 16ULL*16*16*16*16*16*16*16*16*16*16*16*16*16*16 },\r
 139         { 15, 17ULL*17*17*17*17*17*17*17*17*17*17*17*17*17*17 },\r
 140         { 15, 18ULL*18*18*18*18*18*18*18*18*18*18*18*18*18*18 },\r
 141         { 15, 19ULL*19*19*19*19*19*19*19*19*19*19*19*19*19*19 },\r
 142         { 14, 20ULL*20*20*20*20*20*20*20*20*20*20*20*20*20 },\r
 143         { 14, 21ULL*21*21*21*21*21*21*21*21*21*21*21*21*21 },\r
 144         { 14, 22ULL*22*22*22*22*22*22*22*22*22*22*22*22*22 },\r
 145         { 14, 23ULL*23*23*23*23*23*23*23*23*23*23*23*23*23 },\r
 146         { 13, 24ULL*24*24*24*24*24*24*24*24*24*24*24*24 },\r
 147         { 13, 25ULL*25*25*25*25*25*25*25*25*25*25*25*25 },\r
 148         { 13, 26ULL*26*26*26*26*26*26*26*26*26*26*26*26 },\r
 149         { 13, 27ULL*27*27*27*27*27*27*27*27*27*27*27*27 },\r
 150         { 13, 28ULL*28*28*28*28*28*28*28*28*28*28*28*28 },\r
 151         { 13, 29ULL*29*29*29*29*29*29*29*29*29*29*29*29 },\r
 152         { 13, 30ULL*30*30*30*30*30*30*30*30*30*30*30*30 },\r
 153         { 12, 31ULL*31*31*31*31*31*31*31*31*31*31*31 },\r
 154         { 12, 32ULL*32*32*32*32*32*32*32*32*32*32*32 },\r
 155         { 12, 33ULL*33*33*33*33*33*33*33*33*33*33*33 },\r
 156         { 12, 34ULL*34*34*34*34*34*34*34*34*34*34*34 },\r
 157         { 12, 35ULL*35*35*35*35*35*35*35*35*35*35*35 },\r
 158         { 12, 36ULL*36*36*36*36*36*36*36*36*36*36*36 },\r
 159 #endif\r
 160 };\r
 161 \r
 162 cached_power_table* ctable [36-2+1] = {\r
 163         NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,\r
 164         NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,\r
 165         NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,\r
 166         NULL, NULL, NULL, NULL, NULL\r
 167 };\r
 168 \r
 169 const cached_power_table_entry * cached_power (uintD base, uintL i)\r
 170 {\r
 171         var cached_power_table* ptr;\r
 172         if (!(ptr = ctable[base-2]))\r
 173         { ctable[base-2] = ptr = new cached_power_table (); }\r
 174         var uintL j;\r
 175         for (j = 0; j <= i; j++) {\r
 176                 if (zerop(ptr->element[j].base_pow)) {\r
 177                         // Compute b^(k*2^j) and its inverse.\r
 178                         cl_I x =\r
 179                             (j==0 ? cl_I(power_table[base-2].b_to_the_k)\r
 180                                   : ptr->element[j-1].base_pow * ptr->element[j-1].base_pow\r
 181                              );\r
 182                         ptr->element[j].base_pow = x;\r
 183 #ifdef MUL_REPLACES_DIV\r
 184                         ptr->element[j].inv_base_pow = floor1(ash(1,2*integer_length(x)),x);\r
 185 #endif\r
 186                 }\r
 187         }\r
 188         return &ptr->element[i];\r
 189 }\r
 190 \r
 191 AT_DESTRUCTION(cached_power)\r
 192 {\r
 193         for (var uintD base = 2; base <= 36; base++) {\r
 194                 var cached_power_table* ptr = ctable[base-2];\r
 195                 if (ptr) {\r
 196                         delete ptr;\r
 197                         ctable[base-2] = NULL;\r
 198                 }\r
 199         }\r
 200 }\r
 201 \r
 202 }  // namespace cln\r