1 | // ---------------------------------------------------------------------------- |
---|
2 | // semic.cc |
---|
3 | // begin of file |
---|
4 | // Stephan Endrass, endrass@mathematik.uni-mainz.de |
---|
5 | // 23.7.99 |
---|
6 | // ---------------------------------------------------------------------------- |
---|
7 | |
---|
8 | #define SEMIC_CC |
---|
9 | |
---|
10 | #include"mod2.h" |
---|
11 | |
---|
12 | #ifdef HAVE_SPECTRUM |
---|
13 | |
---|
14 | #ifdef SEMIC_PRINT |
---|
15 | #ifndef SEMIC_IOSTREAM |
---|
16 | #include<stdio.h> |
---|
17 | #else |
---|
18 | #include<iostream.h> |
---|
19 | #endif |
---|
20 | #endif |
---|
21 | |
---|
22 | #include<string.h> |
---|
23 | #include<values.h> |
---|
24 | |
---|
25 | #include"intvec.h" |
---|
26 | #include"lists.h" |
---|
27 | #include"GMPrat.h" |
---|
28 | #include"semic.h" |
---|
29 | |
---|
30 | // ---------------------------------------------------------------------------- |
---|
31 | // Delete the memory of a spectrum |
---|
32 | // ---------------------------------------------------------------------------- |
---|
33 | |
---|
34 | inline void spectrum::copy_delete( void ) |
---|
35 | { |
---|
36 | if( s != (Rational*)NULL && n > 0 ) delete [] s; |
---|
37 | if( w != (int*)NULL && n > 0 ) delete [] w; |
---|
38 | copy_zero( ); |
---|
39 | } |
---|
40 | |
---|
41 | // ---------------------------------------------------------------------------- |
---|
42 | // Allocate memory for a spectrum of k numbers |
---|
43 | // ---------------------------------------------------------------------------- |
---|
44 | |
---|
45 | void spectrum::copy_new( int k ) |
---|
46 | { |
---|
47 | if( k > 0 ) |
---|
48 | { |
---|
49 | s = new Rational[k]; |
---|
50 | w = new int[k]; |
---|
51 | |
---|
52 | #ifndef NDEBUG |
---|
53 | if( s == (Rational*)NULL || w == (int*)NULL ) |
---|
54 | { |
---|
55 | #ifdef SEMIC_PRINT |
---|
56 | #ifdef SEMIC_IOSTREAM |
---|
57 | cerr << "spectrum::copy_new(" << k << ")" << endl; |
---|
58 | cerr << " returned ZERO!!!" << endl; |
---|
59 | cerr << " exit..." << endl; |
---|
60 | #else |
---|
61 | fprintf( stderr,"spectrum::copy_new( %d )\n",k ); |
---|
62 | fprintf( stderr," returned ZERO!!!\n" ); |
---|
63 | fprintf( stderr," exit...\n" ); |
---|
64 | #endif |
---|
65 | #endif |
---|
66 | } |
---|
67 | #endif |
---|
68 | } |
---|
69 | else if( k == 0 ) |
---|
70 | { |
---|
71 | s = (Rational*)NULL; |
---|
72 | w = (int*)NULL; |
---|
73 | } |
---|
74 | else if( k < 0 ) |
---|
75 | { |
---|
76 | #ifdef SEMIC_PRINT |
---|
77 | #ifdef SEMIC_IOSTREAM |
---|
78 | cerr << "spectrum::copy_new(" << k << ")"; |
---|
79 | cerr << ": k < 0 ..." << endl; |
---|
80 | #else |
---|
81 | fprintf( stderr,"spectrum::copy_new( %d )",k ); |
---|
82 | fprintf( stderr,": k < 0 ...\n" ); |
---|
83 | #endif |
---|
84 | #endif |
---|
85 | |
---|
86 | exit( 1 ); |
---|
87 | } |
---|
88 | } |
---|
89 | |
---|
90 | // ---------------------------------------------------------------------------- |
---|
91 | // Initialize a spectrum deep from another spectrum |
---|
92 | // ---------------------------------------------------------------------------- |
---|
93 | |
---|
94 | void spectrum::copy_deep( const spectrum &spec ) |
---|
95 | { |
---|
96 | mu = spec.mu; |
---|
97 | pg = spec.pg; |
---|
98 | n = spec.n; |
---|
99 | |
---|
100 | copy_new( n ); |
---|
101 | |
---|
102 | for( int i=0; i<n; i++ ) |
---|
103 | { |
---|
104 | s[i] = spec.s[i]; |
---|
105 | w[i] = spec.w[i]; |
---|
106 | } |
---|
107 | } |
---|
108 | |
---|
109 | // ---------------------------------------------------------------------------- |
---|
110 | // Initialize a spectrum deep from a singular lists |
---|
111 | // ---------------------------------------------------------------------------- |
---|
112 | |
---|
113 | void spectrum::copy_deep( lists l ) |
---|
114 | { |
---|
115 | mu = (int)(l->m[0].Data( )); |
---|
116 | pg = (int)(l->m[1].Data( )); |
---|
117 | n = (int)(l->m[2].Data( )); |
---|
118 | |
---|
119 | copy_new( n ); |
---|
120 | |
---|
121 | intvec *num = (intvec*)l->m[3].Data( ); |
---|
122 | intvec *den = (intvec*)l->m[4].Data( ); |
---|
123 | intvec *mul = (intvec*)l->m[5].Data( ); |
---|
124 | |
---|
125 | for( int i=0; i<n; i++ ) |
---|
126 | { |
---|
127 | s[i] = (Rational)((*num)[i])/(Rational)((*den)[i]); |
---|
128 | w[i] = (*mul)[i]; |
---|
129 | } |
---|
130 | } |
---|
131 | |
---|
132 | // ---------------------------------------------------------------------------- |
---|
133 | // Copy constructor for spectrum |
---|
134 | // ---------------------------------------------------------------------------- |
---|
135 | |
---|
136 | spectrum::spectrum( const spectrum &spec ) |
---|
137 | { |
---|
138 | copy_deep( spec ); |
---|
139 | } |
---|
140 | |
---|
141 | // ---------------------------------------------------------------------------- |
---|
142 | // singular lists constructor for spectrum |
---|
143 | // ---------------------------------------------------------------------------- |
---|
144 | |
---|
145 | spectrum::spectrum( lists l ) |
---|
146 | { |
---|
147 | copy_deep( l ); |
---|
148 | } |
---|
149 | |
---|
150 | // ---------------------------------------------------------------------------- |
---|
151 | // Destructor for spectrum |
---|
152 | // ---------------------------------------------------------------------------- |
---|
153 | |
---|
154 | spectrum::~spectrum( ) |
---|
155 | { |
---|
156 | copy_delete( ); |
---|
157 | } |
---|
158 | |
---|
159 | |
---|
160 | // ---------------------------------------------------------------------------- |
---|
161 | // operator = for spectrum |
---|
162 | // ---------------------------------------------------------------------------- |
---|
163 | |
---|
164 | spectrum spectrum::operator = ( const spectrum &spec ) |
---|
165 | { |
---|
166 | copy_delete( ); |
---|
167 | copy_deep( spec ); |
---|
168 | |
---|
169 | return *this; |
---|
170 | } |
---|
171 | |
---|
172 | // ---------------------------------------------------------------------------- |
---|
173 | // generate a Singular lists from a spectrum |
---|
174 | // ---------------------------------------------------------------------------- |
---|
175 | |
---|
176 | lists spectrum::thelist( void ) |
---|
177 | { |
---|
178 | lists L = (lists)AllocSizeOf( slists ); |
---|
179 | |
---|
180 | L->Init( 6 ); |
---|
181 | |
---|
182 | intvec *num = NewIntvec1( n ); |
---|
183 | intvec *den = NewIntvec1( n ); |
---|
184 | intvec *mult = NewIntvec1( n ); |
---|
185 | |
---|
186 | for( int i=0; i<n; i++ ) |
---|
187 | { |
---|
188 | (*num) [i] = s[i].get_num_si( ); |
---|
189 | (*den) [i] = s[i].get_den_si( ); |
---|
190 | (*mult)[i] = w[i]; |
---|
191 | } |
---|
192 | |
---|
193 | L->m[0].rtyp = INT_CMD; // milnor number |
---|
194 | L->m[1].rtyp = INT_CMD; // geometrical genus |
---|
195 | L->m[2].rtyp = INT_CMD; // # of spectrum numbers |
---|
196 | L->m[3].rtyp = INTVEC_CMD; // numerators |
---|
197 | L->m[4].rtyp = INTVEC_CMD; // denomiantors |
---|
198 | L->m[5].rtyp = INTVEC_CMD; // multiplicities |
---|
199 | |
---|
200 | L->m[0].data = (void*)mu; |
---|
201 | L->m[1].data = (void*)pg; |
---|
202 | L->m[2].data = (void*)n; |
---|
203 | L->m[3].data = (void*)num; |
---|
204 | L->m[4].data = (void*)den; |
---|
205 | L->m[5].data = (void*)mult; |
---|
206 | |
---|
207 | return L; |
---|
208 | } |
---|
209 | |
---|
210 | // ---------------------------------------------------------------------------- |
---|
211 | // add the two spectra s1 and s2 and return their sum |
---|
212 | // ---------------------------------------------------------------------------- |
---|
213 | |
---|
214 | spectrum operator + ( const spectrum &s1,const spectrum &s2 ) |
---|
215 | { |
---|
216 | int i1=0, i2=0, i3=0; |
---|
217 | |
---|
218 | spectrum result; |
---|
219 | |
---|
220 | do |
---|
221 | { |
---|
222 | if( i1 >= s1.n ) |
---|
223 | { |
---|
224 | i2++; |
---|
225 | } |
---|
226 | else if( i2 >= s2.n ) |
---|
227 | { |
---|
228 | i1++; |
---|
229 | } |
---|
230 | else if( s1.s[i1] < s2.s[i2] ) |
---|
231 | { |
---|
232 | i1++; |
---|
233 | } |
---|
234 | else if( s1.s[i1] == s2.s[i2] ) |
---|
235 | { |
---|
236 | i1++; |
---|
237 | i2++; |
---|
238 | } |
---|
239 | else |
---|
240 | { |
---|
241 | i2++; |
---|
242 | } |
---|
243 | i3++; |
---|
244 | } |
---|
245 | while( i1 < s1.n || i2 < s2.n ); |
---|
246 | |
---|
247 | result.copy_new( i3 ); |
---|
248 | result.n = i3; |
---|
249 | |
---|
250 | i1 = i2 = i3 = 0; |
---|
251 | |
---|
252 | do |
---|
253 | { |
---|
254 | if( i1 >= s1.n ) |
---|
255 | { |
---|
256 | result.s[i3] = s2.s[i2]; |
---|
257 | result.w[i3] = s2.w[i2]; |
---|
258 | i2++; |
---|
259 | } |
---|
260 | else if( i2 >= s2.n ) |
---|
261 | { |
---|
262 | result.s[i3] = s1.s[i1]; |
---|
263 | result.w[i3] = s1.w[i1]; |
---|
264 | i1++; |
---|
265 | } |
---|
266 | else if( s1.s[i1] < s2.s[i2] ) |
---|
267 | { |
---|
268 | result.s[i3] = s1.s[i1]; |
---|
269 | result.w[i3] = s1.w[i1]; |
---|
270 | i1++; |
---|
271 | } |
---|
272 | else if( s1.s[i1] == s2.s[i2] ) |
---|
273 | { |
---|
274 | result.s[i3] = s1.s[i1]; |
---|
275 | result.w[i3] = s1.w[i1] + s2.w[i2]; |
---|
276 | i1++; |
---|
277 | i2++; |
---|
278 | } |
---|
279 | else |
---|
280 | { |
---|
281 | result.s[i3] = s2.s[i2]; |
---|
282 | result.w[i3] = s2.w[i2]; |
---|
283 | i2++; |
---|
284 | } |
---|
285 | i3++; |
---|
286 | } |
---|
287 | while( i1 < s1.n || i2 < s2.n ); |
---|
288 | |
---|
289 | result.mu = s1.mu + s2.mu; |
---|
290 | result.pg = s1.pg + s2.pg; |
---|
291 | |
---|
292 | return result; |
---|
293 | } |
---|
294 | |
---|
295 | // ---------------------------------------------------------------------------- |
---|
296 | // multiply the multiplicities of the spectrum numbers of a with m |
---|
297 | // ---------------------------------------------------------------------------- |
---|
298 | |
---|
299 | spectrum operator * ( int k,const spectrum &spec ) |
---|
300 | { |
---|
301 | if( k == 0 ) |
---|
302 | { |
---|
303 | spectrum result; |
---|
304 | |
---|
305 | return result; |
---|
306 | } |
---|
307 | else |
---|
308 | { |
---|
309 | spectrum result( spec ); |
---|
310 | |
---|
311 | result.mu *= k; |
---|
312 | result.pg *= k; |
---|
313 | |
---|
314 | for( int i=0; i<result.n; i++ ) |
---|
315 | { |
---|
316 | result.w[i] *= k; |
---|
317 | } |
---|
318 | |
---|
319 | return result; |
---|
320 | } |
---|
321 | } |
---|
322 | |
---|
323 | // ---------------------------------------------------------------------------- |
---|
324 | // Print a spectrum |
---|
325 | // ---------------------------------------------------------------------------- |
---|
326 | |
---|
327 | #ifdef SEMIC_PRINT |
---|
328 | |
---|
329 | ostream & operator << ( ostream &s,const spectrum &spec ) |
---|
330 | { |
---|
331 | for( int i=0; i<spec.n; i++ ) |
---|
332 | { |
---|
333 | if( i>0 ) |
---|
334 | { |
---|
335 | #ifdef SEMIC_STDOUT |
---|
336 | s << "+"; |
---|
337 | #else |
---|
338 | fprintf( stdout,"+" ); |
---|
339 | #endif |
---|
340 | } |
---|
341 | |
---|
342 | #ifdef SEMIC_STDOUT |
---|
343 | s << spec.w[i] << "*t^"; |
---|
344 | #else |
---|
345 | fprintf( stdout,"%d*t^",spec.w[i] ); |
---|
346 | #endif |
---|
347 | |
---|
348 | s << spec.s[i]; |
---|
349 | } |
---|
350 | |
---|
351 | return s; |
---|
352 | } |
---|
353 | #endif |
---|
354 | |
---|
355 | // ---------------------------------------------------------------------------- |
---|
356 | // Add a subspectrum with multiplicity k (faster than '+') |
---|
357 | // ---------------------------------------------------------------------------- |
---|
358 | |
---|
359 | int spectrum::add_subspectrum( spectrum &a,int k ) |
---|
360 | { |
---|
361 | int i,j; |
---|
362 | for( i=0, j=0; i<n; i++ ) |
---|
363 | { |
---|
364 | if( s[i] == a.s[j] ) |
---|
365 | { |
---|
366 | w[i] += k*a.w[j]; |
---|
367 | j++; |
---|
368 | } |
---|
369 | } |
---|
370 | |
---|
371 | return ( j == a.n ? TRUE : FALSE ); |
---|
372 | } |
---|
373 | |
---|
374 | // ---------------------------------------------------------------------------- |
---|
375 | // set *alpha to the next spectrum number strictly bigger than *alpha |
---|
376 | // returns: TRUE, if such a spectrum number exists |
---|
377 | // FALSE otherwise |
---|
378 | // ---------------------------------------------------------------------------- |
---|
379 | |
---|
380 | int spectrum::next_number( Rational *alpha ) |
---|
381 | { |
---|
382 | int i=0; |
---|
383 | |
---|
384 | while( i < n && *alpha >= s[i] ) |
---|
385 | { |
---|
386 | i++; |
---|
387 | } |
---|
388 | |
---|
389 | if( i < n ) |
---|
390 | { |
---|
391 | *alpha = s[i]; |
---|
392 | return TRUE; |
---|
393 | } |
---|
394 | else |
---|
395 | { |
---|
396 | return FALSE; |
---|
397 | } |
---|
398 | } |
---|
399 | |
---|
400 | // ---------------------------------------------------------------------------- |
---|
401 | // find the next interval on the real line of same length as |
---|
402 | // [*alpha1,*alpha2] having a spectrum number as interval border |
---|
403 | // ---------------------------------------------------------------------------- |
---|
404 | |
---|
405 | int spectrum::next_interval( Rational *alpha1,Rational *alpha2 ) |
---|
406 | { |
---|
407 | Rational zero( 0,1 ); |
---|
408 | Rational a1 = *alpha1; |
---|
409 | Rational a2 = *alpha2; |
---|
410 | Rational d = *alpha2 - *alpha1; |
---|
411 | |
---|
412 | int e1 = this->next_number( &a1 ); |
---|
413 | int e2 = this->next_number( &a2 ); |
---|
414 | |
---|
415 | if( e1 || e2 ) |
---|
416 | { |
---|
417 | Rational d1 = a1 - *alpha1; |
---|
418 | Rational d2 = a2 - *alpha2; |
---|
419 | |
---|
420 | if( d1 < d2 || d2 == zero ) |
---|
421 | { |
---|
422 | *alpha1 = a1; |
---|
423 | *alpha2 = a1 + d; |
---|
424 | } |
---|
425 | else |
---|
426 | { |
---|
427 | *alpha1 = a2 - d; |
---|
428 | *alpha2 = a2; |
---|
429 | } |
---|
430 | return TRUE; |
---|
431 | } |
---|
432 | else |
---|
433 | { |
---|
434 | return FALSE; |
---|
435 | } |
---|
436 | } |
---|
437 | |
---|
438 | // ---------------------------------------------------------------------------- |
---|
439 | // compute the numver of spectrum numbers in the inverval [*alpha1,*alpha2] |
---|
440 | // ---------------------------------------------------------------------------- |
---|
441 | |
---|
442 | int spectrum::numbers_in_interval( Rational &alpha1, |
---|
443 | Rational &alpha2,interval_status status ) |
---|
444 | { |
---|
445 | int count = 0; |
---|
446 | |
---|
447 | for( int i=0; i<n; i++ ) |
---|
448 | { |
---|
449 | if( ( ( status == OPEN || status == LEFTOPEN ) && |
---|
450 | s[i] > alpha1 ) || |
---|
451 | ( ( status == CLOSED || status == RIGHTOPEN ) && |
---|
452 | s[i] >= alpha1 ) ) |
---|
453 | { |
---|
454 | if( ( ( status == OPEN || status == RIGHTOPEN ) && |
---|
455 | s[i] < alpha2 ) || |
---|
456 | ( ( status == CLOSED || status == LEFTOPEN ) && |
---|
457 | s[i] <= alpha2 ) ) |
---|
458 | { |
---|
459 | count += w[i]; |
---|
460 | } |
---|
461 | else |
---|
462 | { |
---|
463 | break; |
---|
464 | } |
---|
465 | } |
---|
466 | } |
---|
467 | |
---|
468 | return count; |
---|
469 | } |
---|
470 | |
---|
471 | // ---------------------------------------------------------------------------- |
---|
472 | // find the maximal integer k such that k*t is semicontinous |
---|
473 | // for the spectrum |
---|
474 | // ---------------------------------------------------------------------------- |
---|
475 | |
---|
476 | int spectrum::mult_spectrum( spectrum &t ) |
---|
477 | { |
---|
478 | spectrum u = *this + t; |
---|
479 | |
---|
480 | Rational alpha1 = -2; |
---|
481 | Rational alpha2 = -1; |
---|
482 | |
---|
483 | int mult=INT_MAX,nthis,nt; |
---|
484 | |
---|
485 | while( u.next_interval( &alpha1,&alpha2 ) ) |
---|
486 | { |
---|
487 | nt = t.numbers_in_interval( alpha1,alpha2,LEFTOPEN ); |
---|
488 | nthis = this->numbers_in_interval( alpha1,alpha2,LEFTOPEN ); |
---|
489 | |
---|
490 | if( nt != 0 ) |
---|
491 | { |
---|
492 | mult = (nthis/nt < mult ? nthis/nt: mult ); |
---|
493 | } |
---|
494 | |
---|
495 | } |
---|
496 | |
---|
497 | return mult; |
---|
498 | } |
---|
499 | |
---|
500 | // ---------------------------------------------------------------------------- |
---|
501 | // find the maximal integer k such that k*t is semicontinous |
---|
502 | // for the spectrum (in the homogeneous sense) |
---|
503 | // ---------------------------------------------------------------------------- |
---|
504 | |
---|
505 | int spectrum::mult_spectrumh( spectrum &t ) |
---|
506 | { |
---|
507 | spectrum u = *this + t; |
---|
508 | |
---|
509 | Rational alpha1 = -2; |
---|
510 | Rational alpha2 = -1; |
---|
511 | |
---|
512 | int mult=INT_MAX,nthis,nt; |
---|
513 | |
---|
514 | while( u.next_interval( &alpha1,&alpha2 ) ) |
---|
515 | { |
---|
516 | nt = t.numbers_in_interval( alpha1,alpha2,LEFTOPEN ); |
---|
517 | nthis = this->numbers_in_interval( alpha1,alpha2,LEFTOPEN ); |
---|
518 | |
---|
519 | if( nt != 0 ) |
---|
520 | { |
---|
521 | mult = (nthis/nt < mult ? nthis/nt: mult ); |
---|
522 | } |
---|
523 | |
---|
524 | nt = t.numbers_in_interval( alpha1,alpha2,OPEN ); |
---|
525 | nthis = this->numbers_in_interval( alpha1,alpha2,OPEN ); |
---|
526 | |
---|
527 | if( nt != 0 ) |
---|
528 | { |
---|
529 | mult = (nthis/nt < mult ? nthis/nt: mult ); |
---|
530 | } |
---|
531 | } |
---|
532 | |
---|
533 | return mult; |
---|
534 | } |
---|
535 | |
---|
536 | // ---------------------------------------------------------------------------- |
---|
537 | // Set the Milnor number |
---|
538 | // ---------------------------------------------------------------------------- |
---|
539 | |
---|
540 | /* |
---|
541 | int spectrum::set_milnor( void ) |
---|
542 | { |
---|
543 | mu = 0; |
---|
544 | |
---|
545 | for( int i=0; i<n; i++ ) |
---|
546 | { |
---|
547 | mu += w[i]; |
---|
548 | } |
---|
549 | |
---|
550 | return mu; |
---|
551 | } |
---|
552 | |
---|
553 | // ---------------------------------------------------------------------------- |
---|
554 | // Set the geometrical genus |
---|
555 | // ---------------------------------------------------------------------------- |
---|
556 | |
---|
557 | int spectrum::set_geometric_genus( void ) |
---|
558 | { |
---|
559 | pg = 0; |
---|
560 | |
---|
561 | for( int i=0; i<n && s[i]<=1; i++ ) |
---|
562 | { |
---|
563 | pg += w[i]; |
---|
564 | } |
---|
565 | return pg; |
---|
566 | } |
---|
567 | */ |
---|
568 | |
---|
569 | #endif /* HAVE_SPECTRUM */ |
---|
570 | // ---------------------------------------------------------------------------- |
---|
571 | // semic.cc |
---|
572 | // end of file |
---|
573 | // ---------------------------------------------------------------------------- |
---|