Part Seven - Euler 44 Nested Recursion: Vectors
Nested C++ Recursion - Introduction (Main Article Page)
Part Six - An Euler 44 Nested Recursive Solution explored an actual nested C++ recursive solution to the Euler 44 Pentagonal Numbers problem. Part Seven here will show a vector-based nested C++ recursive solution to that problem.
The lambda engineering seen here can handle integer vector parameters. C++ vectors operate a lot like arrays, but they add more properties and functions. This recursive C++ Euler 44 solution uses vectors:
1. #include "stdafx.h"
2. #include <chrono>
3. #include <ctime>
4. #include <iostream>
5. #include <functional>
6. #include <math.h>
7. #include <vector>
8.
9. bool is_pentnum(int x) {
10.
11. float testval = (float)(sqrt(24.0f*(float)(x)+1.0f) + 1.0f) / 6.0f;
12. return (((testval - trunc(testval)) == 0.0) ? true : false);
13. };
14.
15. int gen_pentnum(int n) {
16.
17. return (int)(((3 * pow((float)n, 2)) - (float)n) / 2);
18. };
19.
20. int main() {
21.
22. std::function<bool (std::vector<int>&)> innerRecLambda;
23. innerRecLambda = [&innerRecLambda](std::vector<int>& x) {
24.
25. bool inner_is_sum_pentnum = is_pentnum(gen_pentnum(x[1]) + gen_pentnum(x[0]));
26. bool inner_is_diff_pentnum = is_pentnum(gen_pentnum(x[1]) - gen_pentnum(x[0]));
27.
28. if ((x[0] > 1) && (!inner_is_sum_pentnum || !inner_is_diff_pentnum)) {
29.
30. x[0]--;
31.
32. return innerRecLambda(x);
33. } else if ((x[0] == 1) && (!inner_is_sum_pentnum || !inner_is_diff_pentnum)) {
34.
35. return false;
36. } else {
37.
38. return true;
39. }
40. };
41.
42. std::function<std::vector<int>(std::vector<int>&)> outerRecLambda;
43. outerRecLambda = [&outerRecLambda, &innerRecLambda](std::vector<int>& x) {
44.
45. bool outer_is_sum_pentnum = is_pentnum(gen_pentnum(x[1]) + gen_pentnum(x[0]));
46. bool outer_is_diff_pentnum = is_pentnum(gen_pentnum(x[1]) - gen_pentnum(x[0]));
47.
48. if (!outer_is_sum_pentnum || !outer_is_diff_pentnum) {
49.
50. x[0] = x[1] - 1;
51.
52. if (!(innerRecLambda(x))) {
53.
54. x[0] = x[1];
55. x[1]++;
56.
57. return outerRecLambda(x);
58. } else {
59.
60. return (x);
61. }
62. } else {
63.
64. return (x);
65. }
66. };
67.
68. std::vector startValues = { 1, 2 };
69. std::vector finishedValues;
70.
71. auto startTime = std::chrono::high_resolution_clock::now();
72.
73. finishedValues = outerRecLambda(startValues);
74.
75. auto endTime = std::chrono::high_resolution_clock::now();
76. std::chrono::duration timeDifference = endTime - startTime;
77.
78. std::cout << "\n\tThe calculated x vector values --> pentagonal numbers: " << "\n\n";
79. std::cout << "\tx[1] = " << finishedValues[1] << " --> gen_pentnum(x[1]) = gen_pentnum(" << finishedValues[1] << ") = " << gen_pentnum(finishedValues[1]) << "\n";
80. std::cout << "\tx[0] = " << finishedValues[0] << " --> gen_pentnum(x[0]) = gen_pentnum(" << finishedValues[0] << ") = " << gen_pentnum(finishedValues[0]) << "\n\n";
81. std::cout << "\t\t\tgen_pentnum(x[1]) + gen_pentnum(x[0]) = " << gen_pentnum(finishedValues[1]) + gen_pentnum(finishedValues[0]) << "\n";
82. std::cout << "\t\t\tgen_pentnum(" << finishedValues[1] << ") + gen_pentnum(" << finishedValues[0] << ") = " << gen_pentnum(finishedValues[1]) + gen_pentnum(finishedValues[0]) << "\n\n";
83.
84. std::cout << std::boolalpha;
85.
86. std::cout << "\t\t\t" << gen_pentnum(finishedValues[1]) + gen_pentnum(finishedValues[0]) << " is a pentagonal number: " << is_pentnum(gen_pentnum(finishedValues[1]) + gen_pentnum(finishedValues[0])) << "\n\n";
87. std::cout << "\t______________________________________________\n";
88. std::cout << "\t______________________________________________\n\n\n";
89. std::cout << "\tx[1] = " << finishedValues[1] << " --> gen_pentnum(x[1]) = gen_pentnum(" << finishedValues[1] << ") = " << gen_pentnum(finishedValues[1]) << "\n";
90. std::cout << "\tx[0] = " << finishedValues[0] << " --> gen_pentnum(x[0]) = gen_pentnum(" << finishedValues[0] << ") = " << gen_pentnum(finishedValues[0]) << "\n\n";
91. std::cout << "\t\t\tgen_pentnum(x[1]) - gen_pentnum(x[0]) = " << gen_pentnum(finishedValues[1]) - gen_pentnum(finishedValues[0]) << "\n";
92. std::cout << "\t\t\tgen_pentnum(" << finishedValues[1] << ") - gen_pentnum(" << finishedValues[0] << ") = " << gen_pentnum(finishedValues[1]) - gen_pentnum(finishedValues[0]) << "\n\n";
93. std::cout << "\t\t\t" << gen_pentnum(finishedValues[1]) - gen_pentnum(finishedValues[0]) << " is a pentagonal number: " << is_pentnum(gen_pentnum(finishedValues[1]) - gen_pentnum(finishedValues[0])) << "\n\n";
94.
95. std::cout << "\t\t\tCalculation Time = " << timeDifference.count() << " seconds\n\n";
96.
97. system("pause");
98.}
Download the solution files from this GitHub resource. Although this version uses pointers to an integer vector, I changed the Stack Reserve Size to 7000000 (7 megs). The vector data type used here requires more stack resources, as we’ll see shortly. Lines 22, 23, 42, 43, 69, and 70 declare integer vectors. The overall engineering here almost completely clones the previous solution, with one very subtle difference. The lambda signatures at lines 22, 23, 42, and 43 declare the integer vector parameters with a & operator:
std::vector<int>&
As explained above, the & operator defines the parameter data types as reference, or address values. Although the recursion in the previous solution placed copies of the lambdas on the stack as individual stack frames, all lambdas in those frames operated on one integer array. Because arrays operate as memory addresses, we did not need to worry about pointers or the & reference operator for the array parameters. In a similar way, the lambdas in this solution operate on one integer vector. However, vectors don’t automatically work as memory addresses by default. If we forget the & operator, each stack frame will get its own unique copy of the original integer vector. The else block at line 36 will certainly find the correct values, and at line 38, it will return true to outerRecLambda to indicate this. At this point, the innerRecLambda recursive stack frames will start to all unwind as the software pops, or removes those frames from the stack. So far, so good. However, when the outerRecLambda stack frame finally gets to the top of the stack, it sees the x<int> values that it originally pushed on the stack when it called innerRecLambda:
x[1] = 2167
x[0] = 2166
innerRecLambda never changed these values because it received x<int> by value. This diagram shows the stack frames when line 38 executes in this case:
As the software unwinds the stack frames, it ultimately returns the
x[1] = 2167
x[0] = 2166
values to main(). To verify all of this, remove the & operator from the integer vector parameters and run the software. The software will probably have much slower speed. The slow speed makes sense, because more than 1000 stack frames will each have a copy of the integer vector, which will use a lot of extra memory. However, if we pass x<int> to innerRecLambda by reference, the & operator guarantees that each stack frame sees and operates on the exact same integer vector through pointer addressing. Every stack frame that can see x<int> will see the changes that any frame makes to x<int>. This includes stack frames invoked by the outerRecLambda lambda. These outerRecLambda lambda frames can also see x<int>, so they can operate on x<int> as well. In the earlier example, the integer array automatically avoids this problem, because all lambdas in all frames operate on the same array values, through array (pointer) addressing. Of course, we could place the integer vector in a one-cell array and pass this array to the lambdas. However, it probably becomes easier to use the & operator.
Here, we saw a vector-based nested C++ recursive solution to the Euler 44 Pentagonal Numbers problem. Part Eight - Euler 44 Nested Recursion: Classes will how C++ classes can increase recursion engineering efficiency.
Part Six - An Euler 44 Nested Recursive Solution explored an actual nested C++ recursive solution to the Euler 44 Pentagonal Numbers problem. Part Seven here will show a vector-based nested C++ recursive solution to that problem.
The lambda engineering seen here can handle integer vector parameters. C++ vectors operate a lot like arrays, but they add more properties and functions. This recursive C++ Euler 44 solution uses vectors:
1. #include "stdafx.h"
2. #include <chrono>
3. #include <ctime>
4. #include <iostream>
5. #include <functional>
6. #include <math.h>
7. #include <vector>
8.
9. bool is_pentnum(int x) {
10.
11. float testval = (float)(sqrt(24.0f*(float)(x)+1.0f) + 1.0f) / 6.0f;
12. return (((testval - trunc(testval)) == 0.0) ? true : false);
13. };
14.
15. int gen_pentnum(int n) {
16.
17. return (int)(((3 * pow((float)n, 2)) - (float)n) / 2);
18. };
19.
20. int main() {
21.
22. std::function<bool (std::vector<int>&)> innerRecLambda;
23. innerRecLambda = [&innerRecLambda](std::vector<int>& x) {
24.
25. bool inner_is_sum_pentnum = is_pentnum(gen_pentnum(x[1]) + gen_pentnum(x[0]));
26. bool inner_is_diff_pentnum = is_pentnum(gen_pentnum(x[1]) - gen_pentnum(x[0]));
27.
28. if ((x[0] > 1) && (!inner_is_sum_pentnum || !inner_is_diff_pentnum)) {
29.
30. x[0]--;
31.
32. return innerRecLambda(x);
33. } else if ((x[0] == 1) && (!inner_is_sum_pentnum || !inner_is_diff_pentnum)) {
34.
35. return false;
36. } else {
37.
38. return true;
39. }
40. };
41.
42. std::function<std::vector<int>(std::vector<int>&)> outerRecLambda;
43. outerRecLambda = [&outerRecLambda, &innerRecLambda](std::vector<int>& x) {
44.
45. bool outer_is_sum_pentnum = is_pentnum(gen_pentnum(x[1]) + gen_pentnum(x[0]));
46. bool outer_is_diff_pentnum = is_pentnum(gen_pentnum(x[1]) - gen_pentnum(x[0]));
47.
48. if (!outer_is_sum_pentnum || !outer_is_diff_pentnum) {
49.
50. x[0] = x[1] - 1;
51.
52. if (!(innerRecLambda(x))) {
53.
54. x[0] = x[1];
55. x[1]++;
56.
57. return outerRecLambda(x);
58. } else {
59.
60. return (x);
61. }
62. } else {
63.
64. return (x);
65. }
66. };
67.
68. std::vector startValues = { 1, 2 };
69. std::vector finishedValues;
70.
71. auto startTime = std::chrono::high_resolution_clock::now();
72.
73. finishedValues = outerRecLambda(startValues);
74.
75. auto endTime = std::chrono::high_resolution_clock::now();
76. std::chrono::duration timeDifference = endTime - startTime;
77.
78. std::cout << "\n\tThe calculated x vector values --> pentagonal numbers: " << "\n\n";
79. std::cout << "\tx[1] = " << finishedValues[1] << " --> gen_pentnum(x[1]) = gen_pentnum(" << finishedValues[1] << ") = " << gen_pentnum(finishedValues[1]) << "\n";
80. std::cout << "\tx[0] = " << finishedValues[0] << " --> gen_pentnum(x[0]) = gen_pentnum(" << finishedValues[0] << ") = " << gen_pentnum(finishedValues[0]) << "\n\n";
81. std::cout << "\t\t\tgen_pentnum(x[1]) + gen_pentnum(x[0]) = " << gen_pentnum(finishedValues[1]) + gen_pentnum(finishedValues[0]) << "\n";
82. std::cout << "\t\t\tgen_pentnum(" << finishedValues[1] << ") + gen_pentnum(" << finishedValues[0] << ") = " << gen_pentnum(finishedValues[1]) + gen_pentnum(finishedValues[0]) << "\n\n";
83.
84. std::cout << std::boolalpha;
85.
86. std::cout << "\t\t\t" << gen_pentnum(finishedValues[1]) + gen_pentnum(finishedValues[0]) << " is a pentagonal number: " << is_pentnum(gen_pentnum(finishedValues[1]) + gen_pentnum(finishedValues[0])) << "\n\n";
87. std::cout << "\t______________________________________________\n";
88. std::cout << "\t______________________________________________\n\n\n";
89. std::cout << "\tx[1] = " << finishedValues[1] << " --> gen_pentnum(x[1]) = gen_pentnum(" << finishedValues[1] << ") = " << gen_pentnum(finishedValues[1]) << "\n";
90. std::cout << "\tx[0] = " << finishedValues[0] << " --> gen_pentnum(x[0]) = gen_pentnum(" << finishedValues[0] << ") = " << gen_pentnum(finishedValues[0]) << "\n\n";
91. std::cout << "\t\t\tgen_pentnum(x[1]) - gen_pentnum(x[0]) = " << gen_pentnum(finishedValues[1]) - gen_pentnum(finishedValues[0]) << "\n";
92. std::cout << "\t\t\tgen_pentnum(" << finishedValues[1] << ") - gen_pentnum(" << finishedValues[0] << ") = " << gen_pentnum(finishedValues[1]) - gen_pentnum(finishedValues[0]) << "\n\n";
93. std::cout << "\t\t\t" << gen_pentnum(finishedValues[1]) - gen_pentnum(finishedValues[0]) << " is a pentagonal number: " << is_pentnum(gen_pentnum(finishedValues[1]) - gen_pentnum(finishedValues[0])) << "\n\n";
94.
95. std::cout << "\t\t\tCalculation Time = " << timeDifference.count() << " seconds\n\n";
96.
97. system("pause");
98.}
Download the solution files from this GitHub resource. Although this version uses pointers to an integer vector, I changed the Stack Reserve Size to 7000000 (7 megs). The vector data type used here requires more stack resources, as we’ll see shortly. Lines 22, 23, 42, 43, 69, and 70 declare integer vectors. The overall engineering here almost completely clones the previous solution, with one very subtle difference. The lambda signatures at lines 22, 23, 42, and 43 declare the integer vector parameters with a & operator:
std::vector<int>&
As explained above, the & operator defines the parameter data types as reference, or address values. Although the recursion in the previous solution placed copies of the lambdas on the stack as individual stack frames, all lambdas in those frames operated on one integer array. Because arrays operate as memory addresses, we did not need to worry about pointers or the & reference operator for the array parameters. In a similar way, the lambdas in this solution operate on one integer vector. However, vectors don’t automatically work as memory addresses by default. If we forget the & operator, each stack frame will get its own unique copy of the original integer vector. The else block at line 36 will certainly find the correct values, and at line 38, it will return true to outerRecLambda to indicate this. At this point, the innerRecLambda recursive stack frames will start to all unwind as the software pops, or removes those frames from the stack. So far, so good. However, when the outerRecLambda stack frame finally gets to the top of the stack, it sees the x<int> values that it originally pushed on the stack when it called innerRecLambda:
x[1] = 2167
x[0] = 2166
innerRecLambda never changed these values because it received x<int> by value. This diagram shows the stack frames when line 38 executes in this case:
As the software unwinds the stack frames, it ultimately returns the
x[1] = 2167
x[0] = 2166
values to main(). To verify all of this, remove the & operator from the integer vector parameters and run the software. The software will probably have much slower speed. The slow speed makes sense, because more than 1000 stack frames will each have a copy of the integer vector, which will use a lot of extra memory. However, if we pass x<int> to innerRecLambda by reference, the & operator guarantees that each stack frame sees and operates on the exact same integer vector through pointer addressing. Every stack frame that can see x<int> will see the changes that any frame makes to x<int>. This includes stack frames invoked by the outerRecLambda lambda. These outerRecLambda lambda frames can also see x<int>, so they can operate on x<int> as well. In the earlier example, the integer array automatically avoids this problem, because all lambdas in all frames operate on the same array values, through array (pointer) addressing. Of course, we could place the integer vector in a one-cell array and pass this array to the lambdas. However, it probably becomes easier to use the & operator.
Here, we saw a vector-based nested C++ recursive solution to the Euler 44 Pentagonal Numbers problem. Part Eight - Euler 44 Nested Recursion: Classes will how C++ classes can increase recursion engineering efficiency.