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;
  39.         rates[USD][CAD] = 1.34;
  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.                                 {
  232.                                         cout << "CAD";
  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.                                 {
  502.                                         cout << "n Currency not found." << endl;
  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