TheAlgorithms · raklaptudirm · Mar 2, 2022 · Mar 2, 2022 · Mar 2, 2022 · Mar 2, 2022
@@ -1,11 +1,62 @@
-// Returns the value of x to the power of y
+/**
+ * @function powLinear
+ * @description - The powLinear function is a power function with Linear O(n) complexity
+ * @param {number} base
+ * @param {number} exponent
+ * @returns {number}
+ * @example - powLinear(2, 2) => 4 --> 2 * 2
+ * @example - powLinear(3, 3) => 27 --> 3 * 3
+ */
+const powLinear = (base, exponent) => {
+  if (exponent < 0) {
+    base = 1 / base
+    exponent = -exponent
+  }
 
-const pow = (x, y) => {
   let result = 1
-  for (let i = 1; i <= y; i++) {
-    result *= x
+
+  while (exponent--) { // Break the execution while the exponent will 0
+    result *= base
   }
+
   return result
 }
 
-export { pow }
+/**
+ * @function powFaster
+ * @description - The powFaster function is a power function with O(logN) complexity
+ * @param {number} base
+ * @param {number} exponent
+ * @returns {number}
+ * @example - powFaster(2, 2) => 4 --> 2 * 2
+ * @example - powFaster(3, 3) => 27 --> 3 * 3
+ */
+const powFaster = (base, exponent) => {
+  if (exponent < 2) { // explanation below - 1
+    return base && ([1, base][exponent] || powFaster(1 / base, -exponent))
+  }
+
+  if (exponent & 1) { // if the existing exponent is odd
+    return base * powFaster(base * base, exponent >> 1) // explanation below - 2
+  }
+
+  return powFaster(base * base, exponent / 2)
+}
+
+/**
+ * 1 - Magic of short circuit evaluation (&&, ||)
+ * if the base is 0 then it returns 0 cause 0 is falsy
+ * if the base is not 0 then it's must be truthy. after that, it will be executed the right portion of the && (AND) operator
+ * Now it checks the exponent by the help array index, is it 0 or 1.
+ * if the exponent is not 0 or 1 it's definitely less than 0, and a negative number is not a valid index number so it returns "undefined"
+ * if the expression is undefined mean -> falsy, the || (OR) operator evaluates the right portion that is a recursive function.
+ */
+
+/**
+ * 2 - Play with right shift bitwise operator (>>)
+ * right shift with any odd numbers it returns the floor number instead of float.
+ * E.g. if the number is 5, after right shifting with 1 it's will give us 2, not 2.5
+ * cause the right shift formula is --> x >> y = |x| / 2^y
+ */
+
+export { powLinear, powFaster }
@@ -1,15 +1,41 @@
-import { pow } from '../Pow'
+import { powLinear, powFaster } from '../Pow'
 
-describe('Pow', () => {
+describe('Testing powLinear function', () => {
   it('should return 1 for numbers with exponent 0', () => {
-    expect(pow(2, 0)).toBe(1)
+    expect(powLinear(2, 0)).toBe(1)
+  })
+
+  it('should return 0.5 for numbers with exponent -1', () => {
+    expect(powLinear(2, -1)).toBe(0.5)
+  })
+
+  it('should return 0 for numbers with base 0', () => {
+    expect(powLinear(0, 23)).toBe(0)
+  })
+
+  it('should return the base to the exponent power', () => {
+    expect(powLinear(24, 4)).toBe(331776)
+  })
+})
+
+describe('Testing powFaster function', () => {
+  it('should return 1 for numbers with exponent 0', () => {
+    expect(powFaster(2, 0)).toBe(1)
+  })
+
+  it('should return 0.5 for numbers with exponent -1', () => {
+    expect(powFaster(2, -1)).toBe(0.5)
   })
 
   it('should return 0 for numbers with base 0', () => {
-    expect(pow(0, 23)).toBe(0)
+    expect(powFaster(0, 23)).toBe(0)
   })
 
   it('should return the base to the exponent power', () => {
-    expect(pow(24, 4)).toBe(331776)
+    expect(powFaster(24, 4)).toBe(331776)
+  })
+
+  it('should return the result in O(lonN) complexity', () => {
+    expect(powFaster(2, 64)).toBe(18446744073709552000) // execution time Math.log2(64) -> 6
   })
 })