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