-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathexponential.cpp
More file actions
98 lines (80 loc) · 2.13 KB
/
exponential.cpp
File metadata and controls
98 lines (80 loc) · 2.13 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
// Exponential
#include <iostream>
using namespace std;
#include<stdio.h>
#include<cmath>
// Approach 1 : Iterative Exponential
// O(n)
// int exponential(int n)
// {
// int f[n]={1};
// int i;
// f[0] = n;
// cout << f[0] << ", ";
// for (i = 1; i <= n; i++)
// {
// f[i] *= f[n-i];
// cout << f[i] << ", ";
// }
// return f[n];
// }
// int ceil(int x, int y) {
// return x / y + (x % y != 0);
// or q = 1 + ((x - 1) / y); // if x != 0
// }
// Approach 2 : Recursive Exponential
// O(n)
int exponential(int n, int p, int &i){
if(i==p) return 1;
return n*exponential(n,p,++i);
}
// Approach 3 : Divide and Conquer Exponential
// power(x, n) = power(x, n / 2) × power(x, n / 2); // otherwise, n is even
// power(x, n) = x × power(x, n / 2) × power(x, n / 2); // if n is odd
// O(n)
int exponential_dc(int n, int p)
{
if(p<=1) return n;
// cout <<"\n" << floor(p/2) << 3/2 << (1+(p-1)/2) ;
// ceil outwatds roufning mode // https://stackoverflow.com/questions/2745074/fast-ceiling-of-an-integer-division-in-c-c
return exponential_dc(n,floor(p/2)) * exponential_dc(n, 1+(p-1)/2);
}
// Approach 5 : Optimized Divide and Conquer Exponential
// O(logn)
int exponential_dc2(int n, int p){
// base condition
if (p == 0) {
return 1;
}
// calculate subproblem recursively
int pow = exponential_dc2(n, p / 2);
if (p & 1) { // if `p` is odd
return n * pow * pow;
}
// otherwise, `p` is even
return pow * pow;
}
// Approach 6 : Faster Exponential by successive sqauring in computing even expoenetials
int square(int x){
return x*x;
}
int exponential_sq(int n, int p){
if(p<=1) return n ;
if(p%2==0) return square(exponential_sq(n ,p/2));
else return n*exponential_sq(n,p-1);
}
int main ()
{
int n = 2; int p =3; // ans 2^3 = 8
int i = 0;
printf("Final %d", exponential(n, p, i));
printf("\n DC %d", exponential_dc(n, p));
printf("\n exponential_sq %d", exponential_sq(n, p));
return 0;
}
// g++ -o exponential.out exponential.cpp
// ./exponential.out
// outout
// Final 8
// DC 8
// exponential_sq 8%