Commit | Line | Data |
---|---|---|
168f834f PW |
1 | #include <mp.h> |
2 | mult(a,b,c) struct mint *a,*b,*c; | |
3 | { struct mint x,y,z; | |
4 | int sign; | |
5 | sign = 1; | |
6 | x.val=a->val; | |
7 | y.val=b->val; | |
8 | z.len=0; | |
9 | if(a->len<0) | |
10 | { x.len= -a->len; | |
11 | sign= -sign; | |
12 | } | |
13 | else x.len=a->len; | |
14 | if(b->len<0) | |
15 | { y.len= -b->len; | |
16 | sign= -sign; | |
17 | } | |
18 | else y.len=b->len; | |
19 | if(x.len<y.len) m_mult(&y,&x,&z); | |
20 | else m_mult(&x,&y,&z); | |
21 | xfree(c); | |
22 | if(sign<0) c->len= -z.len; | |
23 | else c->len=z.len; | |
24 | if(c->len==0) shfree(z.val); | |
25 | else c->val=z.val; | |
26 | return; | |
27 | } | |
28 | #define S2 x=a->val[j]; | |
29 | #define S3 x=x*b->val[i-j]; | |
30 | #define S4 tradd(&carry,&sum,x); | |
31 | #define S5 c->val[i]=sum.yy.low&077777; | |
32 | #define S6 sum.xx=sum.xx>>15; | |
33 | #define S7 sum.yy.high=carry; | |
34 | m_mult(a,b,c) struct mint *a,*b,*c; | |
35 | { long x; | |
36 | union {long xx; struct half yy;} sum; | |
37 | int carry; | |
38 | int i,j; | |
39 | c->val=xalloc(a->len+b->len,"m_mult"); | |
40 | sum.xx=0; | |
41 | for(i=0;i<b->len;i++) | |
42 | { carry=0; | |
43 | for(j=0;j<i+1;j++) | |
44 | { S2 | |
45 | S3 | |
46 | S4 | |
47 | } | |
48 | S5 | |
49 | S6 | |
50 | S7 | |
51 | } | |
52 | for(;i<a->len;i++) | |
53 | { carry=0; | |
54 | for(j=i-b->len+1;j<i+1;j++) | |
55 | { S2 | |
56 | S3 | |
57 | S4 | |
58 | } | |
59 | S5 | |
60 | S6 | |
61 | S7 | |
62 | } | |
63 | for(;i<a->len+b->len;i++) | |
64 | { carry=0; | |
65 | for(j=i-b->len+1;j<a->len;j++) | |
66 | { S2 | |
67 | S3 | |
68 | S4 | |
69 | } | |
70 | S5 | |
71 | S6 | |
72 | S7 | |
73 | } | |
74 | if(c->val[i-1]!=0) | |
75 | c->len=a->len+b->len; | |
76 | else c->len=a->len+b->len-1; | |
77 | return; | |
78 | } | |
79 | tradd(a,b,c) long c; int *a; union g {long xx; struct half yy;} *b; | |
80 | { | |
81 | b->xx= b->xx+c; | |
82 | if(b->yy.high&0100000) | |
83 | { b->yy.high= b->yy.high&077777; | |
84 | *a += 1; | |
85 | } | |
86 | return; | |
87 | } |