// ==================================== // CodeName : ipow (another method) // Author : Babak Sheykhan // Created : Apr 17, 2018 // /* Notable consideration: Although this one needs containers to hold intemediate calculations, it's quicker than my last code (Fast_ipow) for an acceptable range of inputs. This code is going to be modified for my next project as part of a toolkit. I will add an input validating and also some ERROR code feedback routines to it as before. Any feedback and suggestion will be appreciated. ** Special thanks to JPM7 ** */ // Input note: Same as before, enter base and exponent one after another. // // !!! JUST DON'T ENTER NEGATIVE AND FLOATING POINT INPUT !!! // ==================================== #include #include #include #include using namespace std; typedef unsigned long long ull; struct custom_t { double result; int bigO; bool isError; }; /*-----------------------------*/ /* */ /* PSEUDOCODE */ /* FOR IPOW_64 */ /* */ /*-----------------------------*/ /* Input: two unsigned integer as base and exponent. Let A be an empty list of unsigned integer type and reserve 32 cells. Let B be an empty list with the same property as A. Loop i = 1 To i <= exponent : Add i to list A. Add base to list B. base := base * base. i := i * 2. End Loop Let R be an unsigned integer variable initialized to 1. Loop j = A's last element To j >= 0 : If A[j] <= exponent : exponent := exponent - A[j]. R := R * B[j]. j := j - 1. End If End Loop Output: R as the result of exponentiation. */ custom_t _ipow(ull _val, ull _exp) { custom_t ct; ct.isError = false; ct.bigO = 0; if (_val == 0 && _exp == 0) { cout << "\nMath ERROR\n"; ct.result = 0; // not necessary ct.isError = true; return ct; } // Make lists of power and the value to that power // By reserving the memory ahead of time(if upper bound is fix), push_back() ops will be witnessed a ~2X increased performance. // with a power of 1,000,000 it requires 20 empty space in each list. So, I set it to 32 just in case if the power exceedes 20. Also by doing so, expanding the list is gonna take less overhead (powers of two are machine-friendly!). unsigned size = 32; vector powers; powers.reserve(size); vector val2pow; val2pow.reserve(size); // Start with the power 1 and value^1 ull lastPow = 1; double lastVal = static_cast(_val); // filling two lists as the following order // // powers // +----+----+----+---- // | 1 | 2 | 4 | 8 ... // +----+----+----+---- // // val2pow for value = 5 // +----+----+-----+---- // |5.0 |25.0|625.0| 390,625.0 ... // +----+----+-----+---- while (lastPow <= _exp) { powers.push_back(lastPow); // ~12 cycles with reserve (~21 cycles without reserve) val2pow.push_back(lastVal); // ~12 cycles lastPow <<= 1; // 1 cycle lastVal *= lastVal; // 4 cycles ++ct.bigO; // 1 cycle } // Combine values to make the required power. // /* Example: Suppose value = 5 and exp = 6. The following for block try to pick those powers by which we can get 6 as our desired exp. The above while block filled the power list up to 4 because next power would be 8 and it's greater than 6. powers +----+----+----+ | 1 | 2 | 4 | +----+----+----+ val2pow +----+----+-----+ |5.0 |25.0|625.0| +----+----+-----+ Then, the following for loop starts off by looking at the last (biggest) power in the power list which is 4. After which, it subtracts the value 4 from current exp value (6) and stores the result (2) in exp again. As can be seen, powIdx can point to the same power and its respective value (on val2pow list) at same time. It's an effective way to apply the current produced value by power to the result. The loop continues til powIdx == 0 (first element of list). The complexity of that is O(log(n)). Overall complexity of this program is O(log(n)) + O(log(n)) = O(2log(n)) = O(log(n)) */ ct.result = 1.0; // Get the index of the largest power that is smaller than exponent. for (unsigned powIdx = powers.size() - 1; powIdx >= 0 && powIdx < powers.size(); --powIdx) { // See if this power fits within exponent. // Performance note: at() is slower than operator[] because of boundary checking and exception handling stuff. if (powers[powIdx] <= _exp) { // avg 10 cycles _exp -= powers[powIdx]; // 1 cycle ct.result *= val2pow[powIdx]; // 4 cycles } ++ct.bigO; // 1 cycle } return ct; } int main() { ull value; ull exponent; cout << "Enter positive integers for value(base) and exponent.\n"; cout << "Value: "; cin >> value; cout << "Exponent: "; cin >> exponent; custom_t t = _ipow(value, exponent); stringstream ss; string result_str; ss << t.result; result_str = ss.str(); cout << endl << value << "^" << exponent << " = " << (t.isError ? "-1" : result_str); cout << "\nTime complexity is O(" << t.bigO << ")\n"; }