/* Benjamin Parker Jonathan Tolentino CMPS 345 Term Project (Problem #4) Arbitrage Algorithm 12/21/15 DESCRIPTION This program will use an implementation of the Floyd-Warshall algorithm to determine if an arbitrage exists in a matrix of 50 currencies, starting with USD. */ #include <iostream> #include <iomanip> #include <cstdlib> #include <math.h> #include <list> using namespace std; int main() { double rates[50][50]; enum curr { USD = 0, EUR, BIT, ALK, APO, CAD, BPD, CYN, JPY, ALD, AGK, ARD, ABF, AUD, BGT, BLR, BGF, BED, BOB, BAR, BBD, CID, CLP, CRC, CCP, COP, DKK, ETB, FJD, GTQ, HTG, INR, JEP, KES, LKR, MMK, NZD, OMR, PAB, PHP, PLN, RON, SAR, SLL, SEK, THB, TTD, VEF, VND, ZWD }; //Exchange rates from USD to other currencies rates[USD][USD] = 1.00; rates[USD][EUR] = 0.92; rates[USD][BIT] = 0.0028; rates[USD][ALK] = 125.93; rates[USD][APO] = 9.68; rates[USD][CAD] = 1.34; rates[USD][BPD] = 0.66; rates[USD][CYN] = 6.39; rates[USD][JPY] = 122.59; rates[USD][ALD] = 107.25; rates[USD][AGK] = 134.82; rates[USD][ARD] = 484.59; rates[USD][ABF] = 1.79; rates[USD][AUD] = 1.37; rates[USD][BGT] = 75.54; rates[USD][BLR] = 18160.00; rates[USD][BGF] = 36.9309; rates[USD][BED] = 2.00; rates[USD][BOB] = 6.91; rates[USD][BAR] = 3.76; rates[USD][BBD] = 2.00; rates[USD][CID] = 0.82; rates[USD][CLP] = 701.20; rates[USD][CRC] = 531.18; rates[USD][CCP] = 1.00; rates[USD][COP] = 3202.10; rates[USD][DKK] = 0.145; rates[USD][ETB] = 21.09; rates[USD][FJD] = 2.13; rates[USD][GTQ] = 7.61; rates[USD][HTG] = 56.17; rates[USD][INR] = 66.65; rates[USD][JEP] = 0.66; rates[USD][KES] = 102.20; rates[USD][LKR] = 143.12; rates[USD][MMK] = 1247.65; rates[USD][NZD] = 1.48; rates[USD][OMR] = 0.39; rates[USD][PAB] = 1.00; rates[USD][PHP] = 46.99; rates[USD][PLN] = 3.97; rates[USD][RON] = 4.12; rates[USD][SAR] = 3.75; rates[USD][SLL] = 4115.00; rates[USD][SEK] = 8.48; rates[USD][THB] = 35.76; rates[USD][TTD] = 6.38; rates[USD][VEF] = 6.35; rates[USD][VND] = 22480.00; rates[USD][ZWD] = 361.900; double converter; double variation; int plumin; // Randomly generate the other exchange rates with variations // between 0 and 2% for (int i = 1; i < 50; i++) { converter = 1 / rates[USD][i]; for (int j = 0; j < 50; j++) { rates[i][j] = rates[USD][j] * converter; variation = rates[i][j] * (variation / 100); if (plumin == 0) { rates[i][j] = rates[i][j] - variation; } else { rates[i][j] = rates[i][j] + variation; } } }//END for()- Randomly generate the other exchange rates // Convert the exchange rates, x into -log(x) double logRates[50][50]; for (int i = 0; i < 50; i++) { for (int j = 0; j < 50; j++) { } }//END for()- Convert the exchange rates, x into -log(x) //Floyd-Warshall Allogrithm // Initialize the distance and conversion path matricies double d[50][50]; // Exchange rate from currency i to currency j for (int i = 0; i < 50; i++) { for (int j = 0; j < 50; j++) { if (logRates[i][j] != 0) { d[i][j] = logRates[i][j]; } else { d[i][j] = INFINITY; } } }//END for() - Initialize the distance and conversion path matricies // Check all possible currency conversions for (int k = 0; k < 50; k++) { for (int i = 0; i < 50; i++) { for (int j = 0; j < 50; j++) { if (d[i][j] > (d[i][k] + d[k][j])) { d[i][j] = (d[i][k] + d[k][j]); } } } }//END for() - Check all possible currency conversions // Check for the presence of a negative cycle and construct the path of the arbitrage bool nc = false; // Flag to determine if the graph has a negative cycle list<int> cycle; // List of currencies that make up a negative cycle int path; // The path of currencies in the negative cycle int first; // The source currency int last; // The previous currency on the path for (int i = 0; i < 50; i++) { if (d[i][i] < 0) { nc = true; path = last = first = i; do { last = path; cycle.push_back(path); } while (last != first); break; } }//END for() - Check for the presence of a negative cycle // Determine the path of conversions for the arbitrage if(nc) { cout << "An arbitrage was found!" << endl; cout << "The following is the conversion from USD which" << endl; cout << "leads to an arbitrage: " << endl; cout << "USD"; { cout << " -> "; switch (*c) { case 0: { cout << "USD"; break; } case 1: { cout << "EUR"; break; } case 2: { cout << "BIT"; break; } case 3: { cout << "ALK"; break; } case 4: { cout << "APO"; break; } case 5: { cout << "CAD"; break; } case 6: { cout << "BPD"; break; } case 7: { cout << "CYN"; break; } case 8: { cout << "JPY"; break; } case 9: { cout << "ALD"; break; } case 10: { cout << "AGK"; break; } case 11: { cout << "ARD"; break; } case 12: { cout << "ABF"; break; } case 13: { cout << "AUD"; break; } case 14: { cout << "BGT"; break; } case 15: { cout << "BLR"; break; } case 16: { cout << "BGF"; break; } case 17: { cout << "BED"; break; } case 18: { cout << "BOB"; break; } case 19: { cout << "BAR"; break; } case 20: { cout << "BBD"; break; } case 21: { cout << "CID"; break; } case 22: { cout << "CLP"; break; } case 23: { cout << "CRC"; break; } case 24: { cout << "CCP"; break; } case 25: { cout << "COP"; break; } case 26: { cout << "DKK"; break; } case 27: { cout << "ETB"; break; } case 28: { cout << "FJD"; break; } case 29: { cout << "GTQ"; break; } case 30: { cout << "HTG"; break; } case 31: { cout << "INR"; break; } case 32: { cout << "JEP"; break; } case 33: { cout << "KES"; break; } case 34: { cout << "LKR"; break; } case 35: { cout << "MMK"; break; } case 36: { cout << "NZD"; break; } case 37: { cout << "OMR"; break; } case 38: { cout << "PAB"; break; } case 39: { cout << "PHP"; break; } case 40: { cout << "PLN"; break; } case 41: { cout << "RON"; break; } case 42: { cout << "SAR"; break; } case 43: { cout << "SLL"; break; } case 44: { cout << "SEK"; break; } case 45: { cout << "THB"; break; } case 46: { cout << "TTD"; break; } case 47: { cout << "VEF"; break; } case 48: { cout << "VND"; break; } case 49: { cout << "ZWD"; break; } default: { cout << "\n Currency not found." << endl; break; } }//END switch() - currency path } }//END if()- Determine the path of conversions for the arbitrage // No arbitrage exists else { cout << "No arbitrage was found from USD" << endl; } // Since the seed is fixed the path is the same on each run: cout << endl; cout << rates[USD][USD] << "USD * " << rates[USD][BIT] << "BIT * " << rates[BIT][EUR] << "EUR * " << rates[EUR][USD] << "USD = " ; cout << " " << fixed << showpoint << setprecision(4) << rates[USD][BIT] * rates[BIT][EUR] * rates[EUR][USD] << "USD"; cout << endl; //system("pause"); }
Standard input is empty
/* Benjamin Parker Jonathan Tolentino CMPS 345 Term Project (Problem #4) Arbitrage Algorithm 12/21/15 DESCRIPTION This program will use an implementation of the Floyd-Warshall algorithm to determine if an arbitrage exists in a matrix of 50 currencies, starting with USD. */ #include <iostream> #include <iomanip> #include <cstdlib> #include <math.h> #include <list> using namespace std; int main() { double rates[50][50]; enum curr { USD = 0, EUR, BIT, ALK, APO, CAD, BPD, CYN, JPY, ALD, AGK, ARD, ABF, AUD, BGT, BLR, BGF, BED, BOB, BAR, BBD, CID, CLP, CRC, CCP, COP, DKK, ETB, FJD, GTQ, HTG, INR, JEP, KES, LKR, MMK, NZD, OMR, PAB, PHP, PLN, RON, SAR, SLL, SEK, THB, TTD, VEF, VND, ZWD }; //Exchange rates from USD to other currencies rates[USD][USD] = 1.00; rates[USD][EUR] = 0.92; rates[USD][BIT] = 0.0028; rates[USD][ALK] = 125.93; rates[USD][APO] = 9.68; rates[USD][CAD] = 1.34; rates[USD][BPD] = 0.66; rates[USD][CYN] = 6.39; rates[USD][JPY] = 122.59; rates[USD][ALD] = 107.25; rates[USD][AGK] = 134.82; rates[USD][ARD] = 484.59; rates[USD][ABF] = 1.79; rates[USD][AUD] = 1.37; rates[USD][BGT] = 75.54; rates[USD][BLR] = 18160.00; rates[USD][BGF] = 36.9309; rates[USD][BED] = 2.00; rates[USD][BOB] = 6.91; rates[USD][BAR] = 3.76; rates[USD][BBD] = 2.00; rates[USD][CID] = 0.82; rates[USD][CLP] = 701.20; rates[USD][CRC] = 531.18; rates[USD][CCP] = 1.00; rates[USD][COP] = 3202.10; rates[USD][DKK] = 0.145; rates[USD][ETB] = 21.09; rates[USD][FJD] = 2.13; rates[USD][GTQ] = 7.61; rates[USD][HTG] = 56.17; rates[USD][INR] = 66.65; rates[USD][JEP] = 0.66; rates[USD][KES] = 102.20; rates[USD][LKR] = 143.12; rates[USD][MMK] = 1247.65; rates[USD][NZD] = 1.48; rates[USD][OMR] = 0.39; rates[USD][PAB] = 1.00; rates[USD][PHP] = 46.99; rates[USD][PLN] = 3.97; rates[USD][RON] = 4.12; rates[USD][SAR] = 3.75; rates[USD][SLL] = 4115.00; rates[USD][SEK] = 8.48; rates[USD][THB] = 35.76; rates[USD][TTD] = 6.38; rates[USD][VEF] = 6.35; rates[USD][VND] = 22480.00; rates[USD][ZWD] = 361.900; double converter; double variation; int plumin; srand(7); // Randomly generate the other exchange rates with variations // between 0 and 2% for (int i = 1; i < 50; i++) { converter = 1 / rates[USD][i]; for (int j = 0; j < 50; j++) { rates[i][j] = rates[USD][j] * converter; variation = rand() % 3; variation = rates[i][j] * (variation / 100); plumin = rand() % 2; if (plumin == 0) { rates[i][j] = rates[i][j] - variation; } else { rates[i][j] = rates[i][j] + variation; } } }//END for()- Randomly generate the other exchange rates // Convert the exchange rates, x into -log(x) double logRates[50][50]; for (int i = 0; i < 50; i++) { for (int j = 0; j < 50; j++) { logRates[i][j] = -log(rates[i][j]); } }//END for()- Convert the exchange rates, x into -log(x) //Floyd-Warshall Allogrithm // Initialize the distance and conversion path matricies double d[50][50]; // Exchange rate from currency i to currency j int next[50][50]; // Index of the next node for (int i = 0; i < 50; i++) { for (int j = 0; j < 50; j++) { if (logRates[i][j] != 0) { d[i][j] = logRates[i][j]; next[i][j] = j; } else { d[i][j] = INFINITY; next[i][j] = j; } } }//END for() - Initialize the distance and conversion path matricies // Check all possible currency conversions for (int k = 0; k < 50; k++) { for (int i = 0; i < 50; i++) { for (int j = 0; j < 50; j++) { if (d[i][j] > (d[i][k] + d[k][j])) { d[i][j] = (d[i][k] + d[k][j]); next[i][j] = next[i][k]; } } } }//END for() - Check all possible currency conversions // Check for the presence of a negative cycle and construct the path of the arbitrage bool nc = false; // Flag to determine if the graph has a negative cycle list<int> cycle; // List of currencies that make up a negative cycle int path; // The path of currencies in the negative cycle int first; // The source currency int last; // The previous currency on the path for (int i = 0; i < 50; i++) { if (d[i][i] < 0) { nc = true; path = last = first = i; do { path = next[path][i]; last = path; cycle.push_back(path); } while (last != first); break; } }//END for() - Check for the presence of a negative cycle // Determine the path of conversions for the arbitrage if(nc) { cout << "An arbitrage was found!" << endl; cout << "The following is the conversion from USD which" << endl; cout << "leads to an arbitrage: " << endl; cout << "USD"; for (list<int>::iterator c = cycle.begin(); c != cycle.end(); c++) { cout << " -> "; switch (*c) { case 0: { cout << "USD"; break; } case 1: { cout << "EUR"; break; } case 2: { cout << "BIT"; break; } case 3: { cout << "ALK"; break; } case 4: { cout << "APO"; break; } case 5: { cout << "CAD"; break; } case 6: { cout << "BPD"; break; } case 7: { cout << "CYN"; break; } case 8: { cout << "JPY"; break; } case 9: { cout << "ALD"; break; } case 10: { cout << "AGK"; break; } case 11: { cout << "ARD"; break; } case 12: { cout << "ABF"; break; } case 13: { cout << "AUD"; break; } case 14: { cout << "BGT"; break; } case 15: { cout << "BLR"; break; } case 16: { cout << "BGF"; break; } case 17: { cout << "BED"; break; } case 18: { cout << "BOB"; break; } case 19: { cout << "BAR"; break; } case 20: { cout << "BBD"; break; } case 21: { cout << "CID"; break; } case 22: { cout << "CLP"; break; } case 23: { cout << "CRC"; break; } case 24: { cout << "CCP"; break; } case 25: { cout << "COP"; break; } case 26: { cout << "DKK"; break; } case 27: { cout << "ETB"; break; } case 28: { cout << "FJD"; break; } case 29: { cout << "GTQ"; break; } case 30: { cout << "HTG"; break; } case 31: { cout << "INR"; break; } case 32: { cout << "JEP"; break; } case 33: { cout << "KES"; break; } case 34: { cout << "LKR"; break; } case 35: { cout << "MMK"; break; } case 36: { cout << "NZD"; break; } case 37: { cout << "OMR"; break; } case 38: { cout << "PAB"; break; } case 39: { cout << "PHP"; break; } case 40: { cout << "PLN"; break; } case 41: { cout << "RON"; break; } case 42: { cout << "SAR"; break; } case 43: { cout << "SLL"; break; } case 44: { cout << "SEK"; break; } case 45: { cout << "THB"; break; } case 46: { cout << "TTD"; break; } case 47: { cout << "VEF"; break; } case 48: { cout << "VND"; break; } case 49: { cout << "ZWD"; break; } default: { cout << "\n Currency not found." << endl; break; } }//END switch() - currency path } }//END if()- Determine the path of conversions for the arbitrage // No arbitrage exists else { cout << "No arbitrage was found from USD" << endl; } // Since the seed is fixed the path is the same on each run: cout << endl; cout << rates[USD][USD] << "USD * " << rates[USD][BIT] << "BIT * " << rates[BIT][EUR] << "EUR * " << rates[EUR][USD] << "USD = " ; cout << " " << fixed << showpoint << setprecision(4) << rates[USD][BIT] * rates[BIT][EUR] * rates[EUR][USD] << "USD"; cout << endl; //system("pause"); }