# pastebin

Paste Search Dynamic
Recent pastes
rates
1. /*
2.  Benjamin Parker
3.  Jonathan Tolentino
4.  CMPS 345 Term Project (Problem #4)
5.  Arbitrage Algorithm
6.  12/21/15
7.
8.  DESCRIPTION
9.  This program will use an implementation of the Floyd-Warshall algorithm to
10.  determine if an arbitrage exists in a matrix of 50 currencies, starting
11.  with USD.
12. */
13.
14. #include <iostream>
15. #include <iomanip>
16. #include <cstdlib>
17. #include <math.h>
18. #include <list>
19. using namespace std;
20.
21. int main()
22. {
23.         double rates[50][50];
24.         enum curr
25.         {
26.                 USD = 0, EUR, BIT, ALK, APO, CAD, BPD, CYN, JPY, ALD,
27.                 AGK, ARD, ABF, AUD, BGT, BLR, BGF, BED, BOB, BAR,
28.                 BBD, CID, CLP, CRC, CCP, COP, DKK, ETB, FJD, GTQ,
29.                 HTG, INR, JEP, KES, LKR, MMK, NZD, OMR, PAB, PHP,
30.                 PLN, RON, SAR, SLL, SEK, THB, TTD, VEF, VND, ZWD
31.         };
32.
33.         //Exchange rates from USD to other currencies
34.         rates[USD][USD] = 1.00;
35.         rates[USD][EUR] = 0.92;
36.         rates[USD][BIT] = 0.0028;
37.         rates[USD][ALK] = 125.93;
38.         rates[USD][APO] = 9.68;
40.         rates[USD][BPD] = 0.66;
41.         rates[USD][CYN] = 6.39;
42.         rates[USD][JPY] = 122.59;
43.         rates[USD][ALD] = 107.25;
44.         rates[USD][AGK] = 134.82;
45.         rates[USD][ARD] = 484.59;
46.         rates[USD][ABF] = 1.79;
47.         rates[USD][AUD] = 1.37;
48.         rates[USD][BGT] = 75.54;
49.         rates[USD][BLR] = 18160.00;
50.         rates[USD][BGF] = 36.9309;
51.         rates[USD][BED] = 2.00;
52.         rates[USD][BOB] = 6.91;
53.         rates[USD][BAR] = 3.76;
54.         rates[USD][BBD] = 2.00;
55.         rates[USD][CID] = 0.82;
56.         rates[USD][CLP] = 701.20;
57.         rates[USD][CRC] = 531.18;
58.         rates[USD][CCP] = 1.00;
59.         rates[USD][COP] = 3202.10;
60.         rates[USD][DKK] = 0.145;
61.         rates[USD][ETB] = 21.09;
62.         rates[USD][FJD] = 2.13;
63.         rates[USD][GTQ] = 7.61;
64.         rates[USD][HTG] = 56.17;
65.         rates[USD][INR] = 66.65;
66.         rates[USD][JEP] = 0.66;
67.         rates[USD][KES] = 102.20;
68.         rates[USD][LKR] = 143.12;
69.         rates[USD][MMK] = 1247.65;
70.         rates[USD][NZD] = 1.48;
71.         rates[USD][OMR] = 0.39;
72.         rates[USD][PAB] = 1.00;
73.         rates[USD][PHP] = 46.99;
74.         rates[USD][PLN] = 3.97;
75.         rates[USD][RON] = 4.12;
76.         rates[USD][SAR] = 3.75;
77.         rates[USD][SLL] = 4115.00;
78.         rates[USD][SEK] = 8.48;
79.         rates[USD][THB] = 35.76;
80.         rates[USD][TTD] = 6.38;
81.         rates[USD][VEF] = 6.35;
82.         rates[USD][VND] = 22480.00;
83.         rates[USD][ZWD] = 361.900;
84.
85.
86.         double converter;
87.         double variation;
88.         int plumin;
89.         srand(7);
90.
91.         // Randomly generate the other exchange rates with variations
92.         // between 0 and 2%
93.         for (int i = 1; i < 50; i++)
94.         {
95.                 converter = 1 / rates[USD][i];
96.                 for (int j = 0; j < 50; j++)
97.                 {
98.                         rates[i][j] = rates[USD][j] * converter;
99.                         variation = rand() % 3;
100.                         variation = rates[i][j] * (variation / 100);
101.                         plumin = rand() % 2;
102.                         if (plumin == 0)
103.                         {
104.                                 rates[i][j] = rates[i][j] - variation;
105.                         }
106.                         else
107.                         {
108.                                 rates[i][j] = rates[i][j] + variation;
109.                         }
110.                 }
111.         }//END for()- Randomly generate the other exchange rates
112.
113.
114.         // Convert the exchange rates, x into -log(x)
115.         double logRates[50][50];
116.
117.         for (int i = 0; i < 50; i++)
118.         {
119.                 for (int j = 0; j < 50; j++)
120.                 {
121.                         logRates[i][j] = -log(rates[i][j]);
122.                 }
123.         }//END for()- Convert the exchange rates, x into -log(x)
124.
125.                                         //Floyd-Warshall Allogrithm
126.         // Initialize the distance and conversion path matricies
127.         double d[50][50];                       // Exchange rate from currency i to currency j
128.         int next[50][50];                       // Index of the next node
129.
130.         for (int i = 0; i < 50; i++)
131.         {
132.                 for (int j = 0; j < 50; j++)
133.                 {
134.                         if (logRates[i][j] != 0)
135.                         {
136.                                 d[i][j] = logRates[i][j];
137.                                 next[i][j] = j;
138.                         }
139.
140.                         else
141.                         {
142.                                 d[i][j] = INFINITY;
143.                                 next[i][j] = j;
144.                         }
145.                 }
146.         }//END for() - Initialize the distance and conversion path matricies
147.
148.         // Check all possible currency conversions
149.         for (int k = 0; k < 50; k++)
150.         {
151.                 for (int i = 0; i < 50; i++)
152.                 {
153.                         for (int j = 0; j < 50; j++)
154.                         {
155.                                 if (d[i][j] > (d[i][k] + d[k][j]))
156.                                 {
157.                                         d[i][j] = (d[i][k] + d[k][j]);
158.                                         next[i][j] = next[i][k];
159.                                 }
160.                         }
161.                 }
162.         }//END for() - Check all possible currency conversions
163.
164.         // Check for the presence of a negative cycle and construct the path of the arbitrage
165.         bool nc = false;        // Flag to determine if the graph has a negative cycle
166.         list<int> cycle;        // List of currencies that make up a negative cycle
167.         int path;                       // The path of currencies in the negative cycle
168.         int first;                      // The source currency
169.         int last;                       // The previous currency on the path
170.
171.         for (int i = 0; i < 50; i++)
172.         {
173.                 if (d[i][i] < 0)
174.                 {
175.                         nc = true;
176.                         path = last = first = i;
177.                         do {
178.                                 path = next[path][i];
179.                                 last = path;
180.                                 cycle.push_back(path);
181.                         } while (last != first);
182.                         break;
183.                 }
184.
185.         }//END for() - Check for the presence of a negative cycle
186.
187.         // Determine the path of conversions for the arbitrage
188.         if(nc)
189.         {
190.                 cout << "An arbitrage was found!" << endl;
191.                 cout << "The following is the conversion from USD which" << endl;
192.                 cout << "leads to an arbitrage: " << endl;
193.                 cout << "USD";
194.                 for (list<int>::iterator c = cycle.begin(); c != cycle.end(); c++)
195.                 {
196.                         cout << " -> ";
197.
198.                         switch (*c)
199.                         {
200.                                 case 0:
201.                                 {
202.                                         cout << "USD";
203.                                         break;
204.                                 }
205.
206.                                 case 1:
207.                                 {
208.                                         cout << "EUR";
209.                                         break;
210.                                 }
211.
212.                                 case 2:
213.                                 {
214.                                         cout << "BIT";
215.                                         break;
216.                                 }
217.
218.                                 case 3:
219.                                 {
220.                                         cout << "ALK";
221.                                         break;
222.                                 }
223.
224.                                 case 4:
225.                                 {
226.                                         cout << "APO";
227.                                         break;
228.                                 }
229.
230.                                 case 5:
231.                                 {
233.                                         break;
234.                                 }
235.
236.                                 case 6:
237.                                 {
238.                                         cout << "BPD";
239.                                         break;
240.                                 }
241.
242.                                 case 7:
243.                                 {
244.                                         cout << "CYN";
245.                                         break;
246.                                 }
247.
248.                                 case 8:
249.                                 {
250.                                         cout << "JPY";
251.                                         break;
252.                                 }
253.
254.                                 case 9:
255.                                 {
256.                                         cout << "ALD";
257.                                         break;
258.                                 }
259.
260.                                 case 10:
261.                                 {
262.                                         cout << "AGK";
263.                                         break;
264.                                 }
265.
266.                                 case 11:
267.                                 {
268.                                         cout << "ARD";
269.                                         break;
270.                                 }
271.
272.                                 case 12:
273.                                 {
274.                                         cout << "ABF";
275.                                         break;
276.                                 }
277.
278.                                 case 13:
279.                                 {
280.                                         cout << "AUD";
281.                                         break;
282.                                 }
283.
284.                                 case 14:
285.                                 {
286.                                         cout << "BGT";
287.                                         break;
288.                                 }
289.
290.                                 case 15:
291.                                 {
292.                                         cout << "BLR";
293.                                         break;
294.                                 }
295.
296.                                 case 16:
297.                                 {
298.                                         cout << "BGF";
299.                                         break;
300.                                 }
301.
302.                                 case 17:
303.                                 {
304.                                         cout << "BED";
305.                                         break;
306.                                 }
307.
308.                                 case 18:
309.                                 {
310.                                         cout << "BOB";
311.                                         break;
312.                                 }
313.
314.                                 case 19:
315.                                 {
316.                                         cout << "BAR";
317.                                         break;
318.                                 }
319.
320.                                 case 20:
321.                                 {
322.                                         cout << "BBD";
323.                                         break;
324.                                 }
325.
326.                                 case 21:
327.                                 {
328.                                         cout << "CID";
329.                                         break;
330.                                 }
331.
332.                                 case 22:
333.                                 {
334.                                         cout << "CLP";
335.                                         break;
336.                                 }
337.
338.                                 case 23:
339.                                 {
340.                                         cout << "CRC";
341.                                         break;
342.                                 }
343.
344.                                 case 24:
345.                                 {
346.                                         cout << "CCP";
347.                                         break;
348.                                 }
349.
350.                                 case 25:
351.                                 {
352.                                         cout << "COP";
353.                                         break;
354.                                 }
355.
356.                                 case 26:
357.                                 {
358.                                         cout << "DKK";
359.                                         break;
360.                                 }
361.
362.                                 case 27:
363.                                 {
364.                                         cout << "ETB";
365.                                         break;
366.                                 }
367.
368.                                 case 28:
369.                                 {
370.                                         cout << "FJD";
371.                                         break;
372.                                 }
373.
374.                                 case 29:
375.                                 {
376.                                         cout << "GTQ";
377.                                         break;
378.                                 }
379.
380.                                 case 30:
381.                                 {
382.                                         cout << "HTG";
383.                                         break;
384.                                 }
385.
386.                                 case 31:
387.                                 {
388.                                         cout << "INR";
389.                                         break;
390.                                 }
391.
392.                                 case 32:
393.                                 {
394.                                         cout << "JEP";
395.                                         break;
396.                                 }
397.
398.                                 case 33:
399.                                 {
400.                                         cout << "KES";
401.                                         break;
402.                                 }
403.
404.                                 case 34:
405.                                 {
406.                                         cout << "LKR";
407.                                         break;
408.                                 }
409.
410.                                 case 35:
411.                                 {
412.                                         cout << "MMK";
413.                                         break;
414.                                 }
415.
416.                                 case 36:
417.                                 {
418.                                         cout << "NZD";
419.                                         break;
420.                                 }
421.
422.                                 case 37:
423.                                 {
424.                                         cout << "OMR";
425.                                         break;
426.                                 }
427.
428.                                 case 38:
429.                                 {
430.                                         cout << "PAB";
431.                                         break;
432.                                 }
433.
434.                                 case 39:
435.                                 {
436.                                         cout << "PHP";
437.                                         break;
438.                                 }
439.
440.                                 case 40:
441.                                 {
442.                                         cout << "PLN";
443.                                         break;
444.                                 }
445.
446.                                 case 41:
447.                                 {
448.                                         cout << "RON";
449.                                         break;
450.                                 }
451.
452.                                 case 42:
453.                                 {
454.                                         cout << "SAR";
455.                                         break;
456.                                 }
457.
458.                                 case 43:
459.                                 {
460.                                         cout << "SLL";
461.                                         break;
462.                                 }
463.
464.                                 case 44:
465.                                 {
466.                                         cout << "SEK";
467.                                         break;
468.                                 }
469.
470.                                 case 45:
471.                                 {
472.                                         cout << "THB";
473.                                         break;
474.                                 }
475.
476.                                 case 46:
477.                                 {
478.                                         cout << "TTD";
479.                                         break;
480.                                 }
481.
482.                                 case 47:
483.                                 {
484.                                         cout << "VEF";
485.                                         break;
486.                                 }
487.
488.                                 case 48:
489.                                 {
490.                                         cout << "VND";
491.                                         break;
492.                                 }
493.
494.                                 case 49:
495.                                 {
496.                                         cout << "ZWD";
497.                                         break;
498.                                 }
499.
500.                                 default:
501.                                 {
503.                                         break;
504.                                 }
505.                         }//END switch() - currency path
506.                 }
507.         }//END if()- Determine the path of conversions for the arbitrage
508.
509.          // No arbitrage exists
510.         else
511.         {
512.                 cout << "No arbitrage was found from USD" << endl;
513.         }
514.
515.         // Since the seed is fixed the path is the same on each run:
516.         cout << endl;
517.         cout << rates[USD][USD] << "USD * " << rates[USD][BIT] << "BIT * " << rates[BIT][EUR] << "EUR * " << rates[EUR][USD] << "USD = " ;
518.         cout << " " << fixed << showpoint << setprecision(4) << rates[USD][BIT] * rates[BIT][EUR] * rates[EUR][USD] << "USD";
519.
520.         cout << endl;
521.         //system("pause");
522. }
Parsed in 0.055 seconds