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