1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <string.h>
4.  
5. //co zwracaja poszzczegolne funkcje, odwolywanie sie do tablicy w funkcjach, wczytywanie , wypisywanie,
6. //czy tablice na poczatku oplaca sie wypelniac zerami
7. //wypisywanie wielu zer gdy komorka 0
8.  
9. #define MAX(x, y) (((x) > (y)) ? (x) : (y))
10.  
11.  
12. unsigned int a[1100], b[1100], p[1100], k[1100], s[1100], r[1100];
13.  
14. /*for(int i=0;i<1100;i++){
15.     a[i]=0;
16.     b[i]=0;
17.     p[i]=0;
18.     k[i]=0;
19.     s[i]=0;
20.     r[i]=0;
21.  
22.     if(i==s){
23.         k[i]=1000000000; //wynik z dzielenia moze byc maksymalnie liczba a czyli dlugosc wyniku moze miec maksymalnie dlugosc pierwszej liczby
24.     }
25.  
26. }
27. */
28. unsigned long long w[2200];
29.  
30. char licz1[9900];
31. char licz2[9900];
32.  
33. int n,m;
34.  
35. FILE *fp = fopen ("liczba1.txt", "r"); // liczba a
36.  
37. FILE *fp2 = fopen ("liczba2.txt", "r"); //liczba b
38.  
39. FILE *fp3 = fopen ("wynik.txt","w"); //liczba utworozna przy pomocy obliczen na a i b
40.  
41. void init(*fp,*fp2)
42. {
43.  
44.     int d1,d2;
45.  
46.     while(fgets (licz1, 9900, fp)!=NULL)    // wczytywanie liczby pierwszej do licz1 i sprawdzanie jej dlugosci
47.     {
48.         d1++;
49.     }
50.  
51.     while(fgets (licz2, 9900, fp2)!=NULL)    // wczytywanie liczby drugiej do licz2 i sprawdzanie jej dlugosci
52.     {
53.         d2++;
54.     }
55.  
56.     n=(d1/9)+1; //ilosc komorek w tablicach a  i b;
57.     m=(d2/9)+1;
58.  
59.     unsigned int b; //pomocnicze trzymanie komorki z tablicy a
60.     int c; // 10^j;
61.  
62.     for(int i=0; i<n; i++) //konwersja liczby zapisanej jako string w tablice z podzielona na czesci liczba
63.     {
64.  
65.         d=0;
66.         c=1;
67.  
68.         for (int j=0; j<9; j++)
69.         {
70.  
71.             //licz1[d1-(j*(i+1)]; cyfra z tablicy charow
72.  
73.             d=d+((licz1[d1-(j*(i+1))]-'0')*c);
74.  
75.  
76.             c=c*10;
77.  
78.         }
79.  
80.         a[i]=d; //pojdencza komorka tablicy z pierwsza liczba trzymajaca 9cyfrowa liczbe
81.  
82.     }
83.  
84. //druga liczba
85.     for(int i=0; i<m; i++) //konwersja liczby zapisanej jako string w tablice z podzielona na czesci liczba
86.     {
87.  
88.         d=0;
89.         c=1;
90.  
91.         for (int j=0; j<9; j++)
92.         {
93.  
94.             //licz1[d1-(j*(i+1)]; cyfra z tablicy charow
95.  
96.             d=d+((licz1[d1-(j*(i+1))]-'0')*c);
97.  
98.  
99.             c=c*10;
100.  
101.         }
102.  
103.         b[i]=d; //pojdencza komorka tablicy z pierwsza liczba trzymajaca 9cyfrowa liczbe
104.  
105.     }
106.  
107. }
108.  
109. int nadmiar=0;;
110. int maxs = MAX(n,m);
111.  
112. void sum()
113. {
114.  
115.     w[0]=(a[0]+b[0])%1000000000+nadmiar;
116.  
117.  
118.     for (int i=1; i<maxs; i++)
119.     {
120.  
121.  
122.         nadmiar=((a[i-1]+b[i-1])-(a[i-1]+b[i-1])%1000000000)/1000000000;
123.  
124.         // nadmiar pierwsza cyfra sumy dwoch komorek tablic a i b jesli liczba przekracza 9 cyfr
125.  
126.  
127.         w[i]=((a[i]+b[i])%1000000000)+nadmiar;
128.  
129.         //suma dwoch komorek z nadmiarem z poprzedniej liczby
130.  
131.     }
132.  
133.  
134.  
135. }
136.  
137. //n ilosc komorek w tablicy liczby a
138. //m ilosc komorek liczby b
139.  
140. void sub()
141. {
142.  
143. //odejmowanie jesli liczba1 > liczba2
144.     if(n>m || a[n-1]>b[n-1])
145.     {
146.  
147.         //odejmowanie kazdej komorki jak w odejmowaniu slupkowym
148.         for(int i=0; i<n; i++)
149.         {
150.             if(a[i]>b[i])
151.             {
152.                 w[i]=a[i]-b[i];
153.             }
154.             else // jesli komorka liczby1 jest mniejsza od komorki z liczby2 zapozyczamy z kolejnej
155.                 //komorki liczby1 jedynke i dodajemy jej wartosc do aktualnej komorki
156.             {
157.                 a[i+1]=a[i+1]-1;
158.                 a[i]=a[i]+1000000000;
159.                 w[i]=a[i]-b[i];
160.             }
161.  
162.         }
163.     }
164.     else
165. // jesli liczba ktora chcemy odjac jest wieksza od liczby od ktorej odejmujemy
166. // zamieniamy je miejscami a wynik wypisujemy z minusem
167.     {
168.  
169.         for(int i=0; i<m; i++)
170.         {
171.             if(b[i]>a[i])
172.             {
173.                 w[i]=b[i]-a[i];
174.             }
175.             else // jesli komorka liczby2 jest mniejsza od komorki z liczby1 zapozyczamy z kolejnej
176.                 //komorki liczby2 jedynke i dodajemy jej wartosc do aktualnej komorki
177.             {
178.                 b[i+1]=b[i+1]-1;
179.                 b[i]=b[i]+1000000000;
180.                 w[i]=b[i]-a[i];
181.             }
182.  
183.         }
184.  
185.         //  !printf -?
186.  
187.     }
188.  
189.  
190. }
191.  
192.  
193. void mult()
194. {
195.  
196.     //maxs wieksza z dlugosci liczb
197.     int rozmiar=maxs; // dlugosc podzielonej liczby na dwie czesci
198.  
199.     // int potega = 10^n;
200.  
201.     unsigned int liczbaa1[rozmiar]; // pierwsza czesc liczby a
202.  
203.     unsigned int liczbaa2[rozmiar]; // druga czesc liczbya
204.  
205.  
206.     unsigned int liczbab1[rozmiar]; // pierwsza czesc liczby b
207.  
208.     unsigned int liczbab2[rozmiar]; // druga czesc liczby b
209.  
210.  
211.     unsigned long long karatsuba(unsigned int a[],unsigned int b[])
212.     {
213.  
214.         if(rozmiar==1)
215.         {
216.             liczba1*liczba2
217.  
218.         }
219.  
220.         if(rozmiar%2==0)
221.         {
222.             rozmiar=rozmiar/2;
223.         }
224.         else
225.         {
226.             rozmiar=(rozmiar/2) +1
227.         }
228.  
229.  
230.  
231.         for(int i=0; i<rozmiar; i++)
232.         {
233.  
234.             liczbaa1[i]=a[rozmiar + i];
235.  
236.             liczbaa2[i]=a[i];
237.         }
238.  
239.  
240.         for(int i=0; i<rozmiar; i++)
241.         {
242.  
243.             liczbab1[i]=b[rozmiar + i];
244.  
245.             liczbab2[i]=b[i];
246.         }
247.  
248.         unsigned long long a1b1= karatsuba(liczbaa1[],liczbab1[]);
249.         unsigned long long a2b2= karatsuba(liczbaa2[],liczbab2[]);
250.         unsigned long long e= karatsuba(sum1(liczbaa1[],liczbaa2[]),sum1(liczbab1,liczbab2));
251.         unsigned long long f=sum1(a1b1,a2b2);
252.         unsigned long long g=sub1(e[],f[]);
253.  
254.  
255.         // return w[]?
256.  
257.     }
258.  
259. }
260.  
261. // wyszukiwanie binarne, tablica p[]-poczatek,k[]-koniec,s[]-srodek,r[]-reszta
262.  
263. void div()
264. {
265.    // p->0
266.  
267.  
268.    // k-> 10^(n-m)
269.  
270.     //gdy liczba2 jest wieksza od liczby1 to sie w niej nie miesci wiec wynik dzielenia to 0, a reszta jest cala liczba1
271.     if(m>n)
272.     {
273.         w->0
274.         //r->liczba1
275.  
276.         for(int i=0;i<1100){
277.             r[i]=a[i];
278.         }
279.     }
280.     //inaczej binary search w poszukiwaniuw yniku z dzielenia
281.     else
282.     {
283.     //dopoki poczatek mniejszy od konca
284.         while(p[]<=k[])
285.         {
286.  
287.             srodek=(p+k)/2
288.  
289.             if((srodek*b)<a)
290.             {
291.                 p = srodek + 1
292.             }
293.             else if((srodek*b)>a)
294.             {
295.                 k= srodek -1
296.  
297.             }
298.             else
299.             {
300.                 //wynik z dzielenia nie ma reszty wiec
301.                 //w=k;
302.                 for(int i=0;i<1100;i++){
303.                     w[i]=k[i];
304.                 }
305.             }
306.  
307.         }
308.  
309.         //w znaleziona najwieksza liczbap taka ze p*b>a
310.  
311.         for(int i=0;i<1100;i++){
312.             w[i]=p[i];
313.         }
314.         //reszta z dzielenia
315.  
316.         r=a-(w*b);
317.  
318.     }
319.  
320.  
321.  
322. }
323.  
324.  
325. void save(*fp3)
326. {
327. //x rozmiar tablicy w
328.     for(int i=x; i>=0; i--)
329.     {
330.         //if(w[i]!=NULL)
331.         //trzeba zachowac 9 cyfr w liczbie
332.         fprintf(fp3,"%llu",w[i])
333.  
334.  
335.  
336.     }
337. }
338.  
339.  
340.  
341.  
342.  
343.  
344.