Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit8116aa7

Browse files
committed
Refactor fast powering algorithm.
1 parent8676c1b commit8116aa7

File tree

5 files changed

+38
-25
lines changed

5 files changed

+38
-25
lines changed

‎README.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -67,6 +67,7 @@ a set of rules that precisely define a sequence of operations.
6767
*`B`[Pascal's Triangle](src/algorithms/math/pascal-triangle)
6868
*`B`[Complex Number](src/algorithms/math/complex-number) - complex numbers and basic operations with them
6969
*`B`[Radian & Degree](src/algorithms/math/radian) - radians to degree and backwards conversion
70+
*`B`[Fast Powering](src/algorithms/math/fast-powering)
7071
*`A`[Integer Partition](src/algorithms/math/integer-partition)
7172
*`A`[Liu Hui π Algorithm](src/algorithms/math/liu-hui) - approximate π calculations based on N-gons
7273
*`A`[Discrete Fourier Transform](src/algorithms/math/fourier-transform) - decompose a function of time (a signal) into the frequencies that make it up
@@ -163,6 +164,7 @@ algorithm is an abstraction higher than a computer program.
163164
*`B`[Tree Depth-First Search](src/algorithms/tree/depth-first-search) (DFS)
164165
*`B`[Graph Depth-First Search](src/algorithms/graph/depth-first-search) (DFS)
165166
*`B`[Jump Game](src/algorithms/uncategorized/jump-game)
167+
*`B`[Fast Powering](src/algorithms/math/fast-powering)
166168
*`A`[Permutations](src/algorithms/sets/permutations) (with and without repetitions)
167169
*`A`[Combinations](src/algorithms/sets/combinations) (with and without repetitions)
168170
***Dynamic Programming** - build up a solution using previously found sub-solutions

‎src/algorithms/math/compute-power/__test__/computePower.test.js

Lines changed: 0 additions & 16 deletions
This file was deleted.

‎src/algorithms/math/compute-power/README.mdrenamed to‎src/algorithms/math/fast-powering/README.md

Lines changed: 5 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
#Power(a,b)
1+
#Fast Powering Algorithm
22

33
This computes power of (a,b)
44
eg: power(2,3) = 8
@@ -33,3 +33,7 @@ power(2,5) = 2 * power(2,2) * power(2,2) = 2 * 4 * 4 = 32
3333
Complexity relation: T(n) = T(n/2) + 1
3434

3535
Time complexity of the algorithm: O(logn)
36+
37+
##References
38+
39+
Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
importfastPoweringfrom'../fastPowering';
2+
3+
describe('fastPowering',()=>{
4+
it('should compute power in log(n) time',()=>{
5+
expect(fastPowering(1,1)).toBe(1);
6+
expect(fastPowering(2,0)).toBe(1);
7+
expect(fastPowering(2,2)).toBe(4);
8+
expect(fastPowering(2,3)).toBe(8);
9+
expect(fastPowering(2,4)).toBe(16);
10+
expect(fastPowering(2,5)).toBe(32);
11+
expect(fastPowering(2,6)).toBe(64);
12+
expect(fastPowering(2,7)).toBe(128);
13+
expect(fastPowering(2,8)).toBe(256);
14+
expect(fastPowering(3,4)).toBe(81);
15+
expect(fastPowering(190,2)).toBe(36100);
16+
expect(fastPowering(11,5)).toBe(161051);
17+
expect(fastPowering(13,11)).toBe(1792160394037);
18+
expect(fastPowering(9,16)).toBe(1853020188851841);
19+
expect(fastPowering(16,16)).toBe(18446744073709552000);
20+
expect(fastPowering(7,21)).toBe(558545864083284000);
21+
expect(fastPowering(100,9)).toBe(1000000000000000000);
22+
});
23+
});

‎src/algorithms/math/compute-power/power.jsrenamed to‎src/algorithms/math/fast-powering/fastPowering.js

Lines changed: 8 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -1,22 +1,22 @@
11
/**
2-
*@param {number1} number
3-
*@param {number2} number
4-
*@return {number1^number2}
2+
* Recursive implementation to compute power.
3+
*
4+
*@param {number} number1
5+
*@param {number} number2
6+
*@return {number}
57
*/
6-
7-
// recursive implementation to compute power
8-
exportdefaultfunctioncomputePower(number1,number2){
8+
exportdefaultfunctionfastPowering(number1,number2){
99
letval=0;
1010
letres=0;
1111
if(number2===0){// if number2 is 0
1212
val=1;
1313
}elseif(number2===1){// if number2 is 1 return number 1 as it is
1414
val=number1;
1515
}elseif(number2%2===0){// if number2 is even
16-
res=computePower(number1,number2/2);
16+
res=fastPowering(number1,number2/2);
1717
val=res*res;
1818
}else{// if number2 is odd
19-
res=computePower(number1,Math.floor(number2/2));
19+
res=fastPowering(number1,Math.floor(number2/2));
2020
val=res*res*number1;
2121
}
2222
returnval;

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp