# Untitled

By: a guest on Jul 22nd, 2012  |  syntax: None  |  size: 3.00 KB  |  hits: 13  |  expires: Never
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
1. How to multiply int arrays? [closed]
2. int* multi(int* tab1, int*tab2, int dlugoscTab1, int dlugoscTab2)
3. {
4.     int* A; // long value
5.     int dlugoscA;
6.
7.         int* B; // short value
8.         int dlugoscB;
9.
10.         int *W;  // result
11.         int dlugoscW;
12.
13.     if (dlugoscTab1 >= dlugoscTab2){
14.
15.     dlugoscW = dlugoscTab1*2;
16.
17.     A = new int[dlugoscTab1];
18.     dlugoscA = dlugoscTab1;
19.     //rewrite array1
20.     for (int i =0 ; i <dlugoscTab1; i++) A[i] = tab1[i];
21.     B = new int[dlugoscTab1];
22.     dlugoscB = dlugoscTab1;
23.     //rewrite array2
24.     for (int i =0 ; i <dlugoscTab1-dlugoscTab2; i++) B[i] = 0;
25.     for (int i =dlugoscTab1-dlugoscTab2 ; i <dlugoscTab1 ;  i++) B[i] = tab2[i-(dlugoscTab1-dlugoscTab2)];
26.
27.     //AAAAAAAABBB
28.     }else if(dlugoscTab1 < dlugoscTab2 ){
29.
30.     dlugoscW = dlugoscTab2*2;
31.
32.     A = new int[dlugoscTab2];//long
33.     dlugoscA = dlugoscTab2;
34.     for (int i =0 ; i <dlugoscTab2;i++) A[i] = tab2[i];
35.
36.     B = new int[dlugoscTab2]; //short
37.     dlugoscB = dlugoscTab2;
38.
39.     for (int i =0 ; i < ( dlugoscTab2-dlugoscTab1 ); i++) B[i] = 0;
40.     for (int i = ( dlugoscTab2-dlugoscTab1 ); i <dlugoscTab2 ;  i++) B[i ] = tab1[i-(dlugoscTab2-dlugoscTab1)];
41.
42.
43.     }
44.
45.     W = new int[dlugoscW];
46.     int tmp;
47.
48.     for(int i = 0 ; i < dlugoscW ; i++)
49.     {
50.
51.     //algorithm :
52.     W[dlugoscW  -i -1] += (A[dlugoscA  -i -1] * B[dlugoscB  -i -1] ); // Here is a problem.
53.
54.
55.
56.     }
57.
58.     W[0] = tmp;
59.     return W;
60. }
61.
62. #include <cassert>
63. #include <cstdlib>
64. #include <vector>
65. #include <iostream>
66.
67. typedef std::vector<int> number;
68.
69. number multiply(const number & a, const number & b) {
70.     number c(a.size()+b.size());
71.     // multiply
72.         for (unsigned int i=0; i<a.size(); ++i) { // i indexes a
73.             for (unsigned int j=0; j<b.size(); ++j) { // j indexes b
74.                 int prev = c[i+j];
75.                 c[i+j] += a[i]*b[j];
76.                 assert(c[i+j] > prev); // check for overflow
77.         }
78.     }
79.     // ripple carry -- we can do it all at once since
80.     // even a 32 bit int can fit the carries for
81.     // a 5,000 digit x 5,000 digit multiply
82.     // (exactly sqrt(2^31/9^2) digits on each operand IIRC)
83.     int carry = 0;
84.     for (unsigned int i=0; i <c.size(); ++i) {
85.         c[i] += carry;
86.         ldiv_t dt = ldiv(c[i], 10);
87.         carry = dt.quot;
88.         c[i] = dt.rem;
89.     }
90.     return c;
91. }
92.
94. {
95.     number n;
96.     assert(q>0);
97.     while (q) {
98.         ldiv_t dt = ldiv(q, 10);
99.         n.push_back(dt.rem);
100.         q = dt.quot;
101.     }
102.     return n;
103. }
104.
105. std::ostream & operator<<(std::ostream & str, const number & n)
106. {
107.     for (int i = n.size()-1; i >= 0; i--) {
108.         str << n[i];
109.     }
110.     return str;
111. }
112.
113. unsigned long store(const number & n)
114. {
115.     unsigned long q = 0;
116.     for (int i = n.size()-1; i >= 0; i--) {
117.         unsigned long prev = q;
118.         q = q*10 + n[i];
119.         assert(prev < q); // check for overflow
120.     }
121.     return q;
122. }
123.
124. int main()
125. {