src/integer/conv/cl_I_to_digits.cc

   1 // UDS_to_digits().
   2
   3 // General includes.
   4 #include "cl_sysdep.h"
   5
   6 // Specification.
   7 #include "cl_I.h"
   8
   9
  10 // Implementation.
  11
  12 #include "cl_DS.h"
  13
  14 // Tabelle: enthält zu jeder Basis b (2 <= b <= 36)
  15 // - eine Kettenbruchapproximation num/den von intDsize*log(2)/log(b)
  16 //   (num/den >= intDsize*log(2)/log(b), mit num <= 2^10)
  17 // - k-1 und b^k mit b^k < 2^intDsize, k maximal.
  18   typedef struct { /* uintW num,den; */ uintC k_1; uintD b_hoch_k; } power_table_entry;
  19   static power_table_entry table [36-2+1] = {
  20     #if (intDsize==8)
  21       { /*    8,  1, */ 7-1, 2*2*2*2*2*2*2},
  22       { /*  106, 21, */ 5-1, 3*3*3*3*3},
  23       { /*    4,  1, */ 3-1, 4*4*4},
  24       { /*  789,229, */ 3-1, 5*5*5},
  25       { /*  359,116, */ 3-1, 6*6*6},
  26       { /*  436,153, */ 2-1, 7*7},
  27       { /*    8,  3, */ 2-1, 8*8},
  28       { /*   53, 21, */ 2-1, 9*9},
  29       { /*  525,218, */ 2-1, 10*10},
  30       { /* 1006,435, */ 2-1, 11*11},
  31       { /*  665,298, */ 2-1, 12*12},
  32       { /*  988,457, */ 2-1, 13*13},
  33       { /*  872,415, */ 2-1, 14*14},
  34       { /*  987,482, */ 2-1, 15*15},
  35       { /*    2,  1, */ 1-1, 16},
  36       { /*  869,444, */ 1-1, 17},
  37       { /*  871,454, */ 1-1, 18},
  38       { /*  597,317, */ 1-1, 19},
  39       { /*   87, 47, */ 1-1, 20},
  40       { /*  989,543, */ 1-1, 21},
  41       { /*  949,529, */ 1-1, 22},
  42       { /*  191,108, */ 1-1, 23},
  43       { /*  930,533, */ 1-1, 24},
  44       { /*  789,458, */ 1-1, 25},
  45       { /*  691,406, */ 1-1, 26},
  46       { /*  461,274, */ 1-1, 27},
  47       { /*  218,131, */ 1-1, 28},
  48       { /*  690,419, */ 1-1, 29},
  49       { /*  494,303, */ 1-1, 30},
  50       { /*  633,392, */ 1-1, 31},
  51       { /*    8,  5, */ 1-1, 32},
  52       { /*  766,483, */ 1-1, 33},
  53       { /*  629,400, */ 1-1, 34},
  54       { /*  967,620, */ 1-1, 35},
  55       { /*  359,232, */ 1-1, 36},
  56     #endif
  57     #if (intDsize==16)
  58       { /*   16,  1, */ 15-1, 2*2*2*2*2*2*2*2*2*2*2*2*2*2*2},
  59       { /*  212, 21, */ 10-1, 3*3*3*3*3*3*3*3*3*3},
  60       { /*    8,  1, */  7-1, 4*4*4*4*4*4*4},
  61       { /*  379, 55, */  6-1, 5*5*5*5*5*5},
  62       { /*  359, 58, */  6-1, 6*6*6*6*6*6},
  63       { /*  872,153, */  5-1, 7*7*7*7*7},
  64       { /*   16,  3, */  5-1, 8*8*8*8*8},
  65       { /*  106, 21, */  5-1, 9*9*9*9*9},
  66       { /*  525,109, */  4-1, 10*10*10*10},
  67       { /* 1013,219, */  4-1, 11*11*11*11},
  68       { /*  665,149, */  4-1, 12*12*12*12},
  69       { /*  761,176, */  4-1, 13*13*13*13},
  70       { /*  685,163, */  4-1, 14*14*14*14},
  71       { /*  987,241, */  4-1, 15*15*15*15},
  72       { /*    4,  1, */  3-1, 16*16*16},
  73       { /*  869,222, */  3-1, 17*17*17},
  74       { /*  871,227, */  3-1, 18*18*18},
  75       { /*  113, 30, */  3-1, 19*19*19},
  76       { /*  174, 47, */  3-1, 20*20*20},
  77       { /*   51, 14, */  3-1, 21*21*21},
  78       { /*  653,182, */  3-1, 22*22*22},
  79       { /*  191, 54, */  3-1, 23*23*23},
  80       { /*  677,194, */  3-1, 24*24*24},
  81       { /*  789,229, */  3-1, 25*25*25},
  82       { /*  691,203, */  3-1, 26*26*26},
  83       { /*  461,137, */  3-1, 27*27*27},
  84       { /*  436,131, */  3-1, 28*28*28},
  85       { /*  359,109, */  3-1, 29*29*29},
  86       { /*  988,303, */  3-1, 30*30*30},
  87       { /*  633,196, */  3-1, 31*31*31},
  88       { /*   16,  5, */  3-1, 32*32*32},
  89       { /*  203, 64, */  3-1, 33*33*33},
  90       { /*  629,200, */  3-1, 34*34*34},
  91       { /*  967,310, */  3-1, 35*35*35},
  92       { /*  359,116, */  3-1, 36*36*36},
  93     #endif
  94     #if (intDsize==32)
  95       { /*   32,  1, */ 31-1, 2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL},
  96       { /*  424, 21, */ 20-1, 3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL},
  97       { /*   16,  1, */ 15-1, 4UL*4UL*4UL*4UL*4UL*4UL*4UL*4UL*4UL*4UL*4UL*4UL*4UL*4UL*4UL},
  98       { /*  758, 55, */ 13-1, 5UL*5UL*5UL*5UL*5UL*5UL*5UL*5UL*5UL*5UL*5UL*5UL*5UL},
  99       { /*  359, 29, */ 12-1, 6UL*6UL*6UL*6UL*6UL*6UL*6UL*6UL*6UL*6UL*6UL*6UL},
 100       { /*   57,  5, */ 11-1, 7UL*7UL*7UL*7UL*7UL*7UL*7UL*7UL*7UL*7UL*7UL},
 101       { /*   32,  3, */ 10-1, 8UL*8UL*8UL*8UL*8UL*8UL*8UL*8UL*8UL*8UL},
 102       { /*  212, 21, */ 10-1, 9UL*9UL*9UL*9UL*9UL*9UL*9UL*9UL*9UL*9UL},
 103       { /*  289, 30, */  9-1, 10UL*10UL*10UL*10UL*10UL*10UL*10UL*10UL*10UL},
 104       { /*  990,107, */  9-1, 11UL*11UL*11UL*11UL*11UL*11UL*11UL*11UL*11UL},
 105       { /*  848, 95, */  8-1, 12UL*12UL*12UL*12UL*12UL*12UL*12UL*12UL},
 106       { /*  761, 88, */  8-1, 13UL*13UL*13UL*13UL*13UL*13UL*13UL*13UL},
 107       { /* 1017,121, */  8-1, 14UL*14UL*14UL*14UL*14UL*14UL*14UL*14UL},
 108       { /*  901,110, */  8-1, 15UL*15UL*15UL*15UL*15UL*15UL*15UL*15UL},
 109       { /*    8,  1, */  7-1, 16UL*16UL*16UL*16UL*16UL*16UL*16UL},
 110       { /*  869,111, */  7-1, 17UL*17UL*17UL*17UL*17UL*17UL*17UL},
 111       { /*  683, 89, */  7-1, 18UL*18UL*18UL*18UL*18UL*18UL*18UL},
 112       { /*  113, 15, */  7-1, 19UL*19UL*19UL*19UL*19UL*19UL*19UL},
 113       { /*  348, 47, */  7-1, 20UL*20UL*20UL*20UL*20UL*20UL*20UL},
 114       { /*   51,  7, */  7-1, 21UL*21UL*21UL*21UL*21UL*21UL*21UL},
 115       { /*  653, 91, */  7-1, 22UL*22UL*22UL*22UL*22UL*22UL*22UL},
 116       { /*  191, 27, */  7-1, 23UL*23UL*23UL*23UL*23UL*23UL*23UL},
 117       { /*  677, 97, */  6-1, 24UL*24UL*24UL*24UL*24UL*24UL},
 118       { /*  379, 55, */  6-1, 25UL*25UL*25UL*25UL*25UL*25UL},
 119       { /*  851,125, */  6-1, 26UL*26UL*26UL*26UL*26UL*26UL},
 120       { /*  922,137, */  6-1, 27UL*27UL*27UL*27UL*27UL*27UL},
 121       { /*  872,131, */  6-1, 28UL*28UL*28UL*28UL*28UL*28UL},
 122       { /*  718,109, */  6-1, 29UL*29UL*29UL*29UL*29UL*29UL},
 123       { /*  150, 23, */  6-1, 30UL*30UL*30UL*30UL*30UL*30UL},
 124       { /*  633, 98, */  6-1, 31UL*31UL*31UL*31UL*31UL*31UL},
 125       { /*   32,  5, */  6-1, 32UL*32UL*32UL*32UL*32UL*32UL},
 126       { /*  203, 32, */  6-1, 33UL*33UL*33UL*33UL*33UL*33UL},
 127       { /*  629,100, */  6-1, 34UL*34UL*34UL*34UL*34UL*34UL},
 128       { /*  967,155, */  6-1, 35UL*35UL*35UL*35UL*35UL*35UL},
 129       { /*  359, 58, */  6-1, 36UL*36UL*36UL*36UL*36UL*36UL},
 130     #endif
 131     #if (intDsize==64)
 132       { /*   64,  1, */ 63-1, 2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL*2UL},
 133       { /*  848, 21, */ 40-1, 3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL*3UL},
 134       { /*   32,  1, */ 31-1, 4UL*4UL*4UL*4UL*4UL*4UL*4UL*4UL*4UL*4UL*4UL*4UL*4UL*4UL*4UL*4UL*4UL*4UL*4UL*4UL*4UL*4UL*4UL*4UL*4UL*4UL*4UL*4UL*4UL*4UL*4UL},
 135       { /*  634, 23, */ 27-1, 5UL*5UL*5UL*5UL*5UL*5UL*5UL*5UL*5UL*5UL*5UL*5UL*5UL*5UL*5UL*5UL*5UL*5UL*5UL*5UL*5UL*5UL*5UL*5UL*5UL*5UL*5UL},
 136       { /*  718, 29, */ 24-1, 6UL*6UL*6UL*6UL*6UL*6UL*6UL*6UL*6UL*6UL*6UL*6UL*6UL*6UL*6UL*6UL*6UL*6UL*6UL*6UL*6UL*6UL*6UL*6UL},
 137       { /*  114,  5, */ 22-1, 7UL*7UL*7UL*7UL*7UL*7UL*7UL*7UL*7UL*7UL*7UL*7UL*7UL*7UL*7UL*7UL*7UL*7UL*7UL*7UL*7UL*7UL},
 138       { /*   64,  3, */ 21-1, 8UL*8UL*8UL*8UL*8UL*8UL*8UL*8UL*8UL*8UL*8UL*8UL*8UL*8UL*8UL*8UL*8UL*8UL*8UL*8UL*8UL},
 139       { /*  424, 21, */ 20-1, 9UL*9UL*9UL*9UL*9UL*9UL*9UL*9UL*9UL*9UL*9UL*9UL*9UL*9UL*9UL*9UL*9UL*9UL*9UL*9UL},
 140       { /*  289, 15, */ 19-1, 10UL*10UL*10UL*10UL*10UL*10UL*10UL*10UL*10UL*10UL*10UL*10UL*10UL*10UL*10UL*10UL*10UL*10UL*10UL},
 141       { /* 1018, 55, */ 18-1, 11UL*11UL*11UL*11UL*11UL*11UL*11UL*11UL*11UL*11UL*11UL*11UL*11UL*11UL*11UL*11UL*11UL*11UL},
 142       { /*  607, 34, */ 17-1, 12UL*12UL*12UL*12UL*12UL*12UL*12UL*12UL*12UL*12UL*12UL*12UL*12UL*12UL*12UL*12UL*12UL},
 143       { /*  761, 44, */ 17-1, 13UL*13UL*13UL*13UL*13UL*13UL*13UL*13UL*13UL*13UL*13UL*13UL*13UL*13UL*13UL*13UL*13UL},
 144       { /*  975, 58, */ 16-1, 14UL*14UL*14UL*14UL*14UL*14UL*14UL*14UL*14UL*14UL*14UL*14UL*14UL*14UL*14UL*14UL},
 145       { /*  901, 55, */ 16-1, 15UL*15UL*15UL*15UL*15UL*15UL*15UL*15UL*15UL*15UL*15UL*15UL*15UL*15UL*15UL*15UL},
 146       { /*   16,  1, */ 15-1, 16UL*16UL*16UL*16UL*16UL*16UL*16UL*16UL*16UL*16UL*16UL*16UL*16UL*16UL*16UL},
 147       { /*  595, 38, */ 15-1, 17UL*17UL*17UL*17UL*17UL*17UL*17UL*17UL*17UL*17UL*17UL*17UL*17UL*17UL*17UL},
 148       { /* 1013, 66, */ 15-1, 18UL*18UL*18UL*18UL*18UL*18UL*18UL*18UL*18UL*18UL*18UL*18UL*18UL*18UL*18UL},
 149       { /*  226, 15, */ 15-1, 19UL*19UL*19UL*19UL*19UL*19UL*19UL*19UL*19UL*19UL*19UL*19UL*19UL*19UL*19UL},
 150       { /*  696, 47, */ 14-1, 20UL*20UL*20UL*20UL*20UL*20UL*20UL*20UL*20UL*20UL*20UL*20UL*20UL*20UL},
 151       { /*  102,  7, */ 14-1, 21UL*21UL*21UL*21UL*21UL*21UL*21UL*21UL*21UL*21UL*21UL*21UL*21UL*21UL},
 152       { /*  775, 54, */ 14-1, 22UL*22UL*22UL*22UL*22UL*22UL*22UL*22UL*22UL*22UL*22UL*22UL*22UL*22UL},
 153       { /*  382, 27, */ 14-1, 23UL*23UL*23UL*23UL*23UL*23UL*23UL*23UL*23UL*23UL*23UL*23UL*23UL*23UL},
 154       { /* 1019, 73, */ 13-1, 24UL*24UL*24UL*24UL*24UL*24UL*24UL*24UL*24UL*24UL*24UL*24UL*24UL},
 155       { /*  758, 55, */ 13-1, 25UL*25UL*25UL*25UL*25UL*25UL*25UL*25UL*25UL*25UL*25UL*25UL*25UL},
 156       { /*  994, 73, */ 13-1, 26UL*26UL*26UL*26UL*26UL*26UL*26UL*26UL*26UL*26UL*26UL*26UL*26UL},
 157       { /*  673, 50, */ 13-1, 27UL*27UL*27UL*27UL*27UL*27UL*27UL*27UL*27UL*27UL*27UL*27UL*27UL},
 158       { /*  892, 67, */ 13-1, 28UL*28UL*28UL*28UL*28UL*28UL*28UL*28UL*28UL*28UL*28UL*28UL*28UL},
 159       { /*  830, 63, */ 13-1, 29UL*29UL*29UL*29UL*29UL*29UL*29UL*29UL*29UL*29UL*29UL*29UL*29UL},
 160       { /*  300, 23, */ 13-1, 30UL*30UL*30UL*30UL*30UL*30UL*30UL*30UL*30UL*30UL*30UL*30UL*30UL},
 161       { /*  633, 49, */ 12-1, 31UL*31UL*31UL*31UL*31UL*31UL*31UL*31UL*31UL*31UL*31UL*31UL},
 162       { /*   64,  5, */ 12-1, 32UL*32UL*32UL*32UL*32UL*32UL*32UL*32UL*32UL*32UL*32UL*32UL},
 163       { /*  203, 16, */ 12-1, 33UL*33UL*33UL*33UL*33UL*33UL*33UL*33UL*33UL*33UL*33UL*33UL},
 164       { /*  629, 50, */ 12-1, 34UL*34UL*34UL*34UL*34UL*34UL*34UL*34UL*34UL*34UL*34UL*34UL},
 165       { /*  836, 67, */ 12-1, 35UL*35UL*35UL*35UL*35UL*35UL*35UL*35UL*35UL*35UL*35UL*35UL},
 166       { /*  359, 29, */ 12-1, 36UL*36UL*36UL*36UL*36UL*36UL*36UL*36UL*36UL*36UL*36UL*36UL},
 167     #endif
 168     };
 169
 170 // Timing für Dezimal-Umwandlung einer Zahl mit N Digits = (N*32) Bits,
 171 // auf einem i486 33 MHz unter Linux:
 172 //    N      standard  dnq(div)  dnq(mul)  combined
 173 //     10     0.00031   0.00043   0.00059   0.00031
 174 //     25     0.00103   0.00125   0.00178   0.00103
 175 //     50     0.0030    0.0034    0.0051    0.0030
 176 //    100     0.0100    0.0108    0.0155    0.0100
 177 //    250     0.054     0.055     0.064     0.054
 178 //    500     0.207     0.209     0.229     0.207
 179 //    750     0.47      0.48      0.47      0.47
 180 //   1000     0.81      0.81      0.86      0.81
 181 //   1250     1.25      1.12      1.20      1.12
 182 //   1500     1.81      1.60      1.64      1.61
 183 //   1750     2.45      2.24      2.15      2.25
 184 //   1940     3.01      3.03      3.12      2.80
 185 //   2000     3.20      3.11      3.30      2.89
 186 //   2500     5.00      4.11      4.38      3.91
 187 //   3000     7.3       5.8       5.7       5.5
 188 //   4000    13.0      12.4      12.9       9.7
 189 //   5000    20.3      15.3      15.1      12.4
 190 //  10000    81.4      57.8      56.4      32.5
 191 //  25000                                 112
 192 //  50000                                 265
 193 // dnq(div) means divide-and-conquer using division by B at the topmost call,
 194 //                threshold = 1015.
 195 // dnq(mul) means divide-and-conquer using multiplication by 1/B at the topmost
 196 //                call, threshold = 2050.
 197 // combined means divide-and-conquer as long as length >= threshold.
 198   const unsigned int cl_digits_div_threshold = 1015;
 199   //#define MUL_REPLACES_DIV
 200   const int cl_digits_algo = 1;
 201
 202 // Tabelle: enthält zu jeder Basis b (2 <= b <= 36)
 203 // NULL oder einen Vektor von lazy berechneten b^(k*2^i) und 1/b^(k*2^i).
 204   typedef struct cached_power_table_entry {
 205     ALLOCATE_ANYWHERE(cached_power_table_entry)
 206     cl_I base_pow; // 0 or b^(k*2^i)
 207     #ifdef MUL_REPLACES_DIV
 208     cl_I inv_base_pow; // if base_pow: floor(2^(2*integer_length(base_pow))/base_pow)
 209     #endif
 210   } cached_power_table_entry;
 211   struct cached_power_table {
 212         cached_power_table_entry element[30];
 213         // Constructor and destructor - nothing special.
 214         cached_power_table () {}
 215         ~cached_power_table () {}
 216         // Allocation and deallocation.
 217         void* operator new (size_t size) { return cl_malloc_hook(size); }
 218         void operator delete (void* ptr) { cl_free_hook(ptr); }
 219   };
 220   static cached_power_table* ctable [36-2+1] =
 221     { NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
 222       NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
 223       NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
 224       NULL, NULL, NULL, NULL, NULL
 225     };
 226   static const cached_power_table_entry * cached_power (uintD base, uintL i)
 227     { var cached_power_table* ptr;
 228       if (!(ptr = ctable[base-2]))
 229         { ctable[base-2] = ptr = new cached_power_table (); }
 230       var uintL j;
 231       for (j = 0; j <= i; j++)
 232         if (zerop(ptr->element[j].base_pow))
 233           { // Compute b^(k*2^j) and its inverse.
 234             cl_I x =
 235               (j==0 ? (cl_I)(unsigned long)(table[base-2].b_hoch_k)
 236                     : ptr->element[j-1].base_pow * ptr->element[j-1].base_pow
 237               );
 238             ptr->element[j].base_pow = x;
 239             #ifdef MUL_REPLACES_DIV
 240             ptr->element[j].inv_base_pow = floor1(ash(1,2*integer_length(x)),x);
 241             #endif
 242           }
 243       return &ptr->element[i];
 244     }
 245   AT_DESTRUCTION(cached_power)
 246     { for (var uintD base = 2; base <= 36; base++)
 247         { var cached_power_table* ptr = ctable[base-2];
 248           if (ptr)
 249             { delete ptr; ctable[base-2] = NULL; }
 250         }
 251     }
 252
 253 // like I_to_digits, except that the result has exactly erg_len characters.
 254 static inline void I_to_digits_noshrink (const cl_I& X, uintD base, uintL erg_len, cl_digits* erg)
 255 {
 256   I_to_digits(X,base,erg);
 257   if (erg->len > erg_len) cl_abort();
 258   var uintL count = erg_len - erg->len;
 259   if (count > 0)
 260     { var uintB* ptr = erg->MSBptr;
 261       do { *--ptr = '0'; } while (--count > 0);
 262       erg->MSBptr = ptr; erg->len = erg->len;
 263     }
 264 }
 265
 266 void I_to_digits (const cl_I& X, uintD base, cl_digits* erg)
 267 {
 268 // Methode:
 269 // Umwandlung ins Stellensystem der Basis b geht durch Umwandlung ins Stellen-
 270 // system der Basis b^k (k>=1, b^k<2^intDsize, k maximal) vor sich.
 271 // Aufsuchen von k und b^k aus einer Tabelle.
 272 // Reduktion der UDS zu einer NUDS X.
 273 // Falls X=0: die eine Ziffer 0.
 274 // Falls X>0:
 275 //   Dividiere X durch das Wort b^k,
 276 //   (Single-Precision-Division, vgl. UDS_DIVIDE mit n=1:
 277 //     r:=0, j:=m=Länge(X),
 278 //     while j>0 do
 279 //       j:=j-1, r:=r*beta+X[j], X[j]:=floor(r/b^k), r:=r-b^k*q[j].
 280 //     r=Rest.)
 281 //   zerlege den Rest (mit k-1 Divisionen durch b) in k Ziffern, wandle diese
 282 //   Ziffern einzeln in Ascii um und lege sie an die DIGITS an.
 283 //   Teste auf Speicherüberlauf.
 284 //   X := Quotient.
 285 //   Mache aus X wieder eine NUDS (maximal 1 Nulldigit streichen).
 286 //   Dies solange bis X=0.
 287 //   Streiche die führenden Nullen.
 288       // Aufsuchen von k-1 und b^k aus der Tabelle:
 289       var power_table_entry* tableptr = &table[base-2];
 290       var uintC k_1 = tableptr->k_1; // k-1
 291       var uintD b_hoch_k = tableptr->b_hoch_k; // b^k
 292       var uintB* erg_ptr = erg->LSBptr;
 293       #define next_digit(d)  { *--erg_ptr = (d<10 ? '0'+d : 'A'-10+d); }
 294       // Spezialfälle:
 295       if (zerop(X))
 296         { next_digit(0); goto fertig; } // 0 -> eine Ziffer '0'
 297       else if ((base & (base-1)) == 0)
 298         { // Schneller Algorithmus für Zweierpotenzen
 299           var const uintD* MSDptr;
 300           var uintC len;
 301           var const uintD* LSDptr;
 302           I_to_NDS_nocopy(X, MSDptr=,len=,LSDptr=,cl_false,);
 303           var int b = (base==2 ? 1 : base==4 ? 2 : base==8 ? 3 : /*base==16*/ 4);
 304           var uintD carry = 0;
 305           var int carrybits = 0;
 306           loop
 307             { if (carrybits >= b)
 308                 { var uintD d = carry & (base-1);
 309                   next_digit(d);
 310                   carry = carry >> b; carrybits -= b;
 311                 }
 312                 else
 313                 { var uintD d = carry;
 314                   if (LSDptr != MSDptr)
 315                     { carry = lsprefnext(LSDptr);
 316                       d |= (carry << carrybits) & (base-1);
 317                       next_digit(d);
 318                       carry = carry >> (b-carrybits); carrybits = intDsize - (b-carrybits);
 319                     }
 320                     else
 321                     { next_digit(d); break; }
 322                 }
 323             }
 324         }
 325       else if (fixnump(X) || TheBignum(X)->length < cl_digits_div_threshold
 326                || !cl_digits_algo)
 327         { // Standard-Algorithmus
 328           CL_ALLOCA_STACK;
 329           var uintD* MSDptr;
 330           var uintC len;
 331           var uintD* LSDptr;
 332           I_to_NDS(X, MSDptr=,len=,LSDptr=);
 333           // normalisiere zu einer NUDS:
 334           if (mspref(MSDptr,0)==0) { msshrink(MSDptr); len--; }
 335           loop
 336             { // Noch die NUDS MSDptr/len/.. mit len>0 abzuarbeiten.
 337               // Single-Precision-Division durch b^k:
 338               var uintD rest = divu_loop_msp(b_hoch_k,MSDptr,len);
 339               // Zerlegen des Restes in seine k Ziffern:
 340               var uintC count = k_1;
 341               if ((intDsize>=11) || (count>0))
 342                 // (Bei intDsize>=11 ist wegen b<=36 zwangsläufig
 343                 // k = ceiling(intDsize*log(2)/log(b))-1 >= 2, also count = k_1 > 0.)
 344                 do { var uintD d;
 345                      #if HAVE_DD
 346                        divuD((uintDD)rest,base,rest=,d=);
 347                      #else
 348                        divuD(0,rest,base,rest=,d=);
 349                      #endif
 350                      next_digit(d);
 351                    }
 352                    until (--count == 0);
 353               next_digit(rest); // letzte der k Ziffern ablegen
 354               // Quotienten normalisieren (max. 1 Digit streichen):
 355               if (mspref(MSDptr,0)==0) { msshrink(MSDptr); len--; if (len==0) break; }
 356         }   }
 357       else
 358         { // Divide-and-conquer:
 359           // Find largest i such that B = base^(k*2^i) satisfies B <= X.
 360           // Divide by B: X = X1*B + X0. Convert X0 to string, fill up
 361           // for k*2^i characters, convert X1 to string. (Have to convert
 362           // X0 first because the conversion may temporarily prepend some
 363           // zero characters.)
 364           var uintL ilen_X = integer_length(X);
 365           var const cached_power_table_entry * p;
 366           var uintL ilen_B;
 367           var uintL i;
 368           for (i = 0; ; i++)
 369             { p = cached_power(base,i);
 370               ilen_B = integer_length(p->base_pow);
 371               if (2*ilen_B >= ilen_X) break;
 372               // 2*ilen_B < ilen_X, so certainly B^2 < X, let's continue with i+1.
 373             }
 374           // 2*ilen_B >= ilen_X, implies X < 2*B^2.
 375           // Of course also X >= B, implies ilen_X >= ilen_B.
 376           #ifdef MUL_REPLACES_DIV
 377           // Divide by B by computing
 378           //   q := floor((X * floor(2^ilen_X/B)) / 2^ilen_X).
 379           // We have q <= floor(X/B) <= q+1, so we may have to increment q.
 380           // Note also that
 381           // floor(2^ilen_X/B) = floor(floor(2^(2*ilen_B)/B)/2^(2*ilen_B-ilen_X))
 382           var cl_I q = (X * (p->inv_base_pow >> (2*ilen_B-ilen_X))) >> ilen_X;
 383           var cl_I r = X - q * p->base_pow;
 384           if (r < 0) cl_abort();
 385           if (r >= p->base_pow)
 386             { q = q+1; r = r - p->base_pow;
 387               if (r >= p->base_pow) cl_abort();
 388             }
 389           #else
 390           var cl_I_div_t q_r = floor2(X,p->base_pow);
 391           var const cl_I& q = q_r.quotient;
 392           var const cl_I& r = q_r.remainder;
 393           #endif
 394           var const cl_I& X1 = q;
 395           var const cl_I& X0 = r;
 396           var uintL B_baselen = (uintL)(k_1+1)<<i;
 397           I_to_digits_noshrink(X0,base,B_baselen,erg);
 398           erg->LSBptr -= B_baselen;
 399           I_to_digits(X1,base,erg);
 400           erg->LSBptr += B_baselen;
 401           erg_ptr = erg->MSBptr;
 402         }
 403       #undef next_digit
 404       // Streiche führende Nullen:
 405       while (*erg_ptr == '0') { erg_ptr++; }
 406       fertig:
 407       erg->MSBptr = erg_ptr;
 408       erg->len = erg->LSBptr - erg_ptr;
 409 }
 410 // Bit complexity (N := length(X)): O(log(N)*M(N)).
 411