FilesExpand file tree

 master

/

power.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

150 lines (131 loc) · 3.18 KB

 master

/

power.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

150 lines (131 loc) · 3.18 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

/*

* Copyright(c) 2019 Jiau Zhang

* For more information see <https://github.com/JiauZhang/algorithms>

*

* This repo is free software: you can redistribute it and/or modify

* it under the terms of the GNU General Public License as published by

* the Free Software Foundation

*

* It is distributed in the hope that it will be useful,

* but WITHOUT ANY WARRANTY; without even the implied warranty of

* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the

* GNU General Public License for more details.

*

* You should have received a copy of the GNU General Public License

* along with THIS repo. If not, see <http://www.gnu.org/licenses/>.

*/

#include <iostream>

using namespace std;

double power_v1(double base, int exp)

{

double res = 1.0;

while(exp) {

res = res * base;

exp--;

}

return res;

}

//计算机内表示小数时都有误差，不能直接判断某个小数和某个小数是否相等

//只能通过两个数的差值是否足够小来判断它俩是否相等

bool equal(double num1, double num2)

{

if((num1-num2>-0.0000001)&&(num1-num2<0.0000001))

return true;

return false;

}

double power_v2(double base, int exp)

{

double res = 1.0;

bool negative = 0;

if(equal(base, 0.0))

return base;

if(base==1.0)

return 1.0;

if(exp<0) {

exp = -exp;

negative = 1;

}

if(exp==0) {

return res;

} else if(exp==1) {

if(negative)

return 1/base;

return base;

} else if(exp%2) { //更高效的做法是用 exp&0x01 进行判断

res = power_v2(base, (exp-1)/2);

res = res * res;

if(negative)

return 1/(res*base);

return res*base;

} else {

res = power_v2(base, exp/2);

if(negative)

return 1/(res*res);

return res*res;

}

}

double power_v3(double base, int exp)

{

// only test algorithm, dont care safty !

if (exp == 0)

return 1;

if(equal(base, 0.0)) // && exp > 0)

return base;

double part1 = 1.0;

double part2 = 1.0;

bool negative = false;

if (exp < 0) {

negative = true;

exp = -exp;

}

if (exp & 0x01) {

part1 = base;

exp -= 1;

}

if (exp) {

part2 = base;

exp = exp >> 1;

}

while (exp) {

part2 = part2 * part2;

exp = exp >> 1;

}

if (negative) {

return 1 / (part1 * part2);

} else {

return part1 * part2;

}

}

void Test(double base)

{

cout << "power_v2" << endl;

cout << power_v2(base, 0) << endl;

cout << power_v2(base, 1) << endl;

cout << power_v2(base, 2) << endl;

cout << power_v2(base, 5) << endl;

cout << "power_v3" << endl;

cout << power_v3(base, 0) << endl;

cout << power_v3(base, 1) << endl;

cout << power_v3(base, 2) << endl;

cout << power_v3(base, 5) << endl;

cout << "power_v2" << endl;

cout << power_v2(base, -0) << endl;

cout << power_v2(base, -1) << endl;

cout << power_v2(base, -2) << endl;

cout << power_v2(base, -5) << endl;

cout << "power_v3" << endl;

cout << power_v3(base, -0) << endl;

cout << power_v3(base, -1) << endl;

cout << power_v3(base, -2) << endl;

cout << power_v3(base, -5) << endl;

}

int main(int argc, char** argv)

{

double test1 = 5.5;

double test2 = 1.0;

double test3 = 0.0;

Test(test1);

Test(test2);

Test(test3);

return 0;

}