My Project
Loading...
Searching...
No Matches
kChinese.cc
Go to the documentation of this file.
1#include "misc/auxiliary.h"
2
3#include "misc/intvec.h"
4#include "misc/options.h"
6#include "polys/matpol.h"
8#include "coeffs/longrat.h"
9#include "Singular/feOpt.h"
10#include "kernel/polys.h"
11#include "kernel/mod2.h"
12
13#ifdef HAVE_VSPACE
14
15#define mpz_isNeg(A) ((A)->_mp_size<0)
16number nlRInit (long i);
17
19#include "kernel/ideals.h"
20#include <sys/types.h>
21#include <sys/wait.h>
22#include <unistd.h>
23
24// send a number via a string s
25static char *send_number(char *s, number n)
26{
27 long *d=(long*)s;
28 if (SR_HDL(n) & SR_INT)
29 {
30 *d=(long)n;
31 s+=SIZEOF_LONG;
32 }
33 else
34 {
35 *d=n->s*2;/* n->s in 0..3: 0..6, use +8 for neg. numbers */
36 s+=SIZEOF_LONG;
37 if (mpz_isNeg(n->z)) { *d+=8; mpz_neg(n->z,n->z); }
38 size_t l;
39 d=(long*)s;
40 s+=SIZEOF_LONG;
41 mpz_export(s,&l,-1,sizeof(mp_limb_t),0,0,n->z);
42 *d=l;
43 s+=l*sizeof(mp_limb_t);
44 if (n->s!=3)
45 {
46 d=(long*)s;
47 s+=SIZEOF_LONG;
48 mpz_export(s,&l,-1,sizeof(mp_limb_t),0,0,n->n);
49 *d=l;
50 s+=l*sizeof(mp_limb_t);
51 }
52 }
53 return s;
54}
55
56static char * get_number(char *s, number *n)
57{
58 // format: last bit 1: imm. number (long)
59 // otherwise: 0,2: size(long) mpz, size(long) mpz
60 // 6: size(long) mpz
61 // 8,10: size(long) -mpz, size(long) mpz
62 // 14: size(long) -mpz
63 long *d=(long*)s;
64 s+=SIZEOF_LONG;
65 if (((*d)&1)==1) // immediate number
66 {
67 *n=(number)(*d);
68 }
69 else
70 {
71 *n=nlRInit(0);
72 BOOLEAN neg=(*d>=8);
73 if (neg) *d-=8;
74 (*n)->s=(*d)/2;
75 d=(long*)s;
76 s+=SIZEOF_LONG;
77 size_t l=*d;
78 mpz_realloc2((*n)->z,l*sizeof(mp_limb_t)*8);
79 mpz_import((*n)->z,l,-1,sizeof(mp_limb_t),0,0,s);
80 if (neg) mpz_neg((*n)->z,(*n)->z);
81 s+=l*sizeof(mp_limb_t);
82 if ((*n)->s!=3)
83 {
84 d=(long*)s;
85 s+=SIZEOF_LONG;
86 l=*d;
87 mpz_init2((*n)->n,l*sizeof(mp_limb_t)*8);
88 mpz_import((*n)->n,l,-1,sizeof(mp_limb_t),0,0,s);
89 s+=l*sizeof(mp_limb_t);
90 }
91 }
92 return s;
93}
94
95static long size_number(number n)
96{
97 long ll=SIZEOF_LONG;
98 if (SR_HDL(n) & SR_INT)
99 {
100 return SIZEOF_LONG;
101 }
102 else
103 {
104 if (n->s==3)
105 {
106 ll+=SIZEOF_LONG*2; /* n->s, mpz size */
107 long l=mpz_size1(n->z);
108 ll+=l*sizeof(mp_limb_t);
109 }
110 else
111 {
112 ll+=SIZEOF_LONG*3; /* n->s, mpz size(n->z) mpz size(n->n)*/
113 size_t l=mpz_size1(n->z);
114 ll+=l*sizeof(mp_limb_t);
115 l=mpz_size1(n->n);
116 ll+=l*sizeof(mp_limb_t);
117 }
118 }
119 return ll;
120}
121
122static char* send_mon(char *s, poly m, const ring r)
123{
124 // format: number exp[0..r->ExpL_Size]
126 memcpy(s,m->exp,r->ExpL_Size*sizeof(long));
127 s+=r->ExpL_Size*sizeof(long);
128 return s;
129}
130
131static char* get_mon(char *s, poly *m, const ring r)
132{
133 (*m)=p_Init(r);
134 s=get_number(s,&p_GetCoeff(*m,r));
135 memcpy((*m)->exp,s,r->ExpL_Size*sizeof(long));
136 s+=r->ExpL_Size*sizeof(long);
137 return s;
138}
139
140static long size_mon(poly m, const ring r)
141{
142 long ll=size_number(p_GetCoeff(m,r));
143 ll+=r->ExpL_Size*sizeof(long);
144 return ll;
145}
146
147static char* send_poly(char *s, int ind, poly p, const ring r)
148{
149 // format: index(long) length(long) mon...
150 //p_Write(p,r);PrintLn();
151 long *d=(long*)s;
152 *d=ind;
153 s+=SIZEOF_LONG;
154 long l=pLength(p);
155 d=(long*)s;
156 *d=l;
157 s+=SIZEOF_LONG;
158 while(p!=NULL)
159 {
160 s=send_mon(s,p,r);
161 pIter(p);
162 }
163 return s;
164}
165
166static char* get_poly(char *s,int &ind, poly *p,const ring r)
167{
168 long *d=(long*)s;
169 ind=*d;
170 s+=SIZEOF_LONG;
171 d=(long*)s;
172 long l=*d;
173 s+=SIZEOF_LONG;
174 for(long i=0;i<l;i++)
175 {
176 poly m;
177 s=get_mon(s,&m,r);
178 pNext(m)=*p;
179 *p=m;
180 }
181 *p=pReverse(*p);
182 return s;
183}
184
185static long size_poly(poly p, const ring r)
186{
187 long l=SIZEOF_LONG*2;
188 while(p!=NULL)
189 {
190 l+=size_mon(p,r);
191 pIter(p);
192 }
193 return l;
194}
195
196ideal id_ChineseRemainder_0(ideal *xx, number *q, int rl, const ring r)
197{
198 int cnt=0;int rw=0; int cl=0;
199 // find max. size of xx[.]:
200 for(int j=rl-1;j>=0;j--)
201 {
202 int i=IDELEMS(xx[j])*xx[j]->nrows;
203 if (i>cnt) cnt=i;
204 if (xx[j]->nrows >rw) rw=xx[j]->nrows; // for lifting matrices
205 if (xx[j]->ncols >cl) cl=xx[j]->ncols; // for lifting matrices
206 }
207 if (rw*cl !=cnt)
208 {
209 WerrorS("format mismatch in CRT");
210 return NULL;
211 }
212 int cpus=(int)(long)feOptValue(FE_OPT_CPUS);
215 /* start no more than MAX_PROCESS-1 children */
216 if ((cpus==1) || (2*cpus>=cnt))
217 /* at least 2 polys for each process, or switch to seriell version */
218 return id_ChineseRemainder(xx,q,rl,r);
219 ideal result=idInit(cnt,xx[0]->rank);
220 result->nrows=rw; // for lifting matrices
221 result->ncols=cl; // for lifting matrices
222 int parent_pid=getpid();
223 using namespace vspace;
224 vmem_init();
225 // Create a queue of int
226 VRef<Queue<int> > queue = vnew<Queue<int> >();
227 for(int i=cnt-1;i>=0; i--)
228 {
229 queue->enqueue(i); // the tasks: construct poly p[i]
230 }
231 for(int i=cpus;i>=0;i--)
232 {
233 queue->enqueue(-1); // stop sign, one for each child
234 }
235 // Create a queue of polys
236 VRef<Queue<VRef<VString> > > rqueue = vnew<Queue<VRef<VString> > >();
237 for (int i=0;i<cpus;i++)
238 {
239 int pid = fork_process();
240 if (pid==0) break; //child
241 }
242 if (parent_pid!=getpid()) // child ------------------------------------------
243 {
244 number *x=(number *)omAlloc(rl*sizeof(number));
245 poly *p=(poly *)omAlloc(rl*sizeof(poly));
246 CFArray inv_cache(rl);
249 loop
250 {
251 int ind=queue->dequeue();
252 if (ind== -1)
253 {
254 exit(0);
255 }
256
257 for(int j=rl-1;j>=0;j--)
258 {
259 if(ind>=IDELEMS(xx[j])*xx[j]->nrows) // out of range of this ideal
260 p[j]=NULL;
261 else
262 p[j]=xx[j]->m[ind];
263 }
264 poly res=p_ChineseRemainder(p,x,q,rl,inv_cache,r);
265 long l=size_poly(res,r);
266 //printf("size: %ld kB\n",(l+1023)/1024);
267 VRef<VString> msg = vstring(l+1);
268 char *s=(char*)msg->str();
269 send_poly(s,ind,res,r);
270 rqueue->enqueue(msg);
271 if (TEST_OPT_PROT) printf(".");
272 }
273 }
274 else // parent ---------------------------------------------------
275 {
276 if (TEST_OPT_PROT) printf("%d children created\n",cpus);
277 VRef<VString> msg;
278 while(cnt>0)
279 {
280 msg=rqueue->dequeue();
281 char *s=(char*)msg->str();
282 int ind;
283 poly p=NULL;
284 get_poly(s,ind,&p,r);
285 //printf("got res[%d]\n",ind);
286 result->m[ind]=p;
287 msg.free();
288 cnt--;
289 }
290 // removes queues
291 queue.free();
292 rqueue.free();
293 vmem_deinit();
294 }
295 return result;
296}
297
298ideal id_Farey_0(ideal x, number N, const ring r)
299{
300 int cnt=IDELEMS(x)*x->nrows;
301 int cpus=(int)(long)feOptValue(FE_OPT_CPUS);
304 /* start no more than MAX_PROCESS-1 children */
305 if (2*cpus>=cnt) /* at least 2 polys for each process,
306 or switch to seriell version */
307 return id_Farey(x,N,r);
308 ideal result=idInit(cnt,x->rank);
309 result->nrows=x->nrows; // for lifting matrices
310 result->ncols=x->ncols; // for lifting matrices
311
312 int parent_pid=getpid();
313 using namespace vspace;
314 vmem_init();
315 // Create a queue of int
316 VRef<Queue<int> > queue = vnew<Queue<int> >();
317 for(int i=cnt-1;i>=0; i--)
318 {
319 queue->enqueue(i); // the tasks: construct poly p[i]
320 }
321 for(int i=cpus;i>=0;i--)
322 {
323 queue->enqueue(-1); // stop sign, one for each child
324 }
325 // Create a queue of polys
326 VRef<Queue<VRef<VString> > > rqueue = vnew<Queue<VRef<VString> > >();
327 for (int i=0;i<cpus;i++)
328 {
329 int pid = fork_process();
330 if (pid==0) break; //child
331 }
332 if (parent_pid!=getpid()) // child ------------------------------------------
333 {
334 loop
335 {
336 int ind=queue->dequeue();
337 if (ind== -1)
338 {
339 exit(0);
340 }
341
342 poly res=p_Farey(x->m[ind],N,r);
343 long l=size_poly(res,r);
344 VRef<VString> msg = vstring(l+1);
345 char *s=(char*)msg->str();
346 send_poly(s,ind,res,r);
347 rqueue->enqueue(msg);
348 if (TEST_OPT_PROT) printf(".");
349 }
350 }
351 else // parent ---------------------------------------------------
352 {
353 if (TEST_OPT_PROT) printf("%d children created\n",cpus);
354 VRef<VString> msg;
355 while(cnt>0)
356 {
357 msg=rqueue->dequeue();
358 char *s=(char*)msg->str();
359 int ind;
360 poly p=NULL;
361 get_poly(s,ind,&p,r);
362 //printf("got res[%d]\n",ind);
363 result->m[ind]=p;
364 msg.free();
365 cnt--;
366 }
367 // wait for the children to finish
368 sleep(1);
369 // removes queues
370 queue.free();
371 rqueue.free();
372 vmem_deinit();
373 }
374 return result;
375}
376
377#if 0
378// debug for send_poly
379void test_n(poly n)
380{
381 p_Write(n,currRing);
382 char *buf=(char*)omAlloc0(2048*1000);
383 int ll=size_poly(n,currRing);
384 printf("size: %d\n",ll);
385 char *s=send_poly(buf,12345,n,currRing);
386 printf("send len: %d\n",(int)(s-buf));
387 long *d=(long*)buf;
388 for(int i=0;i<=ll/SIZEOF_LONG;i++) printf("%ld ",d[i]);
389 printf("\n");
390 n=NULL;
391 s=get_poly(buf,ll,&n,currRing);
392 printf("read len: %d\n",(int)(s-buf));
393 Print(":index: %d\n",ll);
394 p_Write(n,currRing);
395 PrintLn();
396 omFree(buf);
397}
398#endif
399#endif
All the auxiliary stuff.
int BOOLEAN
Definition: auxiliary.h:87
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:56
int l
Definition: cfEzgcd.cc:100
int m
Definition: cfEzgcd.cc:128
int i
Definition: cfEzgcd.cc:132
Variable x
Definition: cfModGcd.cc:4082
int p
Definition: cfModGcd.cc:4078
cl
Definition: cfModGcd.cc:4100
int int ncols
Definition: cf_linsys.cc:32
int nrows
Definition: cf_linsys.cc:32
#define Print
Definition: emacs.cc:80
return result
Definition: facAbsBiFact.cc:75
const CanonicalForm int s
Definition: facAbsFact.cc:51
CanonicalForm res
Definition: facAbsFact.cc:60
int j
Definition: facHensel.cc:110
void WerrorS(const char *s)
Definition: feFopen.cc:24
static void * feOptValue(feOptIndex opt)
Definition: feOpt.h:40
#define EXTERN_VAR
Definition: globaldefs.h:6
ideal id_Farey(ideal x, number N, const ring r)
Definition: ideals.cc:2848
static char * get_poly(char *s, int &ind, poly *p, const ring r)
Definition: kChinese.cc:166
#define mpz_isNeg(A)
Definition: kChinese.cc:15
static char * get_mon(char *s, poly *m, const ring r)
Definition: kChinese.cc:131
static long size_poly(poly p, const ring r)
Definition: kChinese.cc:185
ideal id_Farey_0(ideal x, number N, const ring r)
Definition: kChinese.cc:298
static long size_number(number n)
Definition: kChinese.cc:95
static char * send_poly(char *s, int ind, poly p, const ring r)
Definition: kChinese.cc:147
static char * send_number(char *s, number n)
Definition: kChinese.cc:25
number nlRInit(long i)
Definition: longrat.cc:2530
static char * send_mon(char *s, poly m, const ring r)
Definition: kChinese.cc:122
ideal id_ChineseRemainder_0(ideal *xx, number *q, int rl, const ring r)
Definition: kChinese.cc:196
static char * get_number(char *s, number *n)
Definition: kChinese.cc:56
static long size_mon(poly m, const ring r)
Definition: kChinese.cc:140
poly p_ChineseRemainder(poly *xx, mpz_ptr *x, mpz_ptr *q, int rl, mpz_ptr *C, const ring R)
VAR int n_SwitchChinRem
Definition: longrat.cc:3094
#define SR_INT
Definition: longrat.h:67
#define pIter(p)
Definition: monomials.h:37
#define pNext(p)
Definition: monomials.h:36
#define p_GetCoeff(p, r)
Definition: monomials.h:50
static const int MAX_PROCESS
Definition: vspace.h:1419
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define omFree(addr)
Definition: omAllocDecl.h:261
#define omAlloc0(size)
Definition: omAllocDecl.h:211
#define NULL
Definition: omList.c:12
#define TEST_OPT_PROT
Definition: options.h:104
poly p_Farey(poly p, number N, const ring r)
Definition: p_polys.cc:54
static int pLength(poly a)
Definition: p_polys.h:188
void p_Write(poly p, ring lmRing, ring tailRing)
Definition: polys0.cc:342
static poly pReverse(poly p)
Definition: p_polys.h:333
static poly p_Init(const ring r, omBin bin)
Definition: p_polys.h:1318
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13
Compatibility layer for legacy polynomial operations (over currRing)
void PrintLn()
Definition: reporter.cc:310
#define mpz_size1(A)
Definition: si_gmp.h:17
int status int void * buf
Definition: si_signals.h:59
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:35
ideal id_ChineseRemainder(ideal *xx, number *q, int rl, const ring r)
#define IDELEMS(i)
Definition: simpleideals.h:23
#define loop
Definition: structs.h:75
void free()
Definition: vspace.h:1805
#define SR_HDL(A)
Definition: tgb.cc:35