Combinatorial Summation Primes: a Discussion of Different Methods to Solve the Problem Kamil Ksia˛żek Zbigniew Marszałek Faculty of Applied Mathematics Institute of Mathematics Silesian University of Technology Silesian University of Technology Gliwice, Poland Gliwice, Poland Email: kamiksi862@student.polsl.pl Email: Zbigniew.Marszalek@polsl.pl Abstract—This paper illustrates combinatorial summation efficiency in parallelization of processing [6], while Gubias ex- numbers by means of computer operations. The aim of the tended this approach on various structures of input information research is to give a definition of all different primes which sum is [7], and Wozniak et al. proposed devoted versions of sorting equal 100, where the smallest combination has only two elements and the biggest has nine elements. This paper presents some ways methods developed for large data sets by the use of merge sort to deal with this problem. There are analyzed two methods. One [19] and quick sort model [18]. Benchmark tests on improved of them uses nested loops (non-recursive method), second way is versions of merge sort methods were presented by Marszalek connected with stacks (recursive method). et al. [17]. Practical approaches to implement sorting methods are presented by Huang and Langston [8], with extension for Index Terms—prime, summation, stack, loop, analysis, recur- devoted main memory usage by Huang and Langston [9]. sion High efficiency request service models for SQL systems were presented by Wozniak et al. [13]. Similarly advances in man- machine interactions management can significantly improve I. I NTRODUCTION efficiency and quality of service as presented by Polap et al. The computational complexity of algorithms, one of the [15], [16]. most important problem of computer science, is clearly one This paper presents benchmark tests on improvements in of the most important aspects of computer science. Although computer methods by introduction of non recursive algorithm computers repeatedly increased its computing power, still in comparison to its regular version. In the following sections micro machines are working on acceleration of existing al- we present different versions of combinatorial algorithm for gorithms. The problem remains an open question whether determining the sum of the set of numbers using primes. the higher performance algorithms are recursive, or may not Performance tests show the effectiveness of the proposed recursive versions are faster. algorithm operating on the stake. There are reported many approaches to increase computa- tional efficiency. Gabryel presented devoted methods to imple- II. N ESTED LOOPS ’ FOR ’ - NON - RECURSIVE METHOD ment in data base systems, where implemented method serve In the research on efficiency of non recursive approach as efficient tool for data management in high performance SQL we have implemented two versions of algorithm used for environments [1] and human supporting systems for medical combinatorial summation of primes that comply condition that purposes by Wozniak et al. [20] and daily routine assistance a sum is equal 100. by Damasevicius et al. [12]. Grycuk et al. presented devoted architectures to process visual data by clustering based on A. Description inverse frequency [2], and improved approach for multi-layer A prime is a number which has only two divisors: 1 SQL architectures [3]. Czerwinski presented Hadoop imple- and itself. The initial step is isolation primes from first 100 mentation of data filtering [4], where information streaming numbers. You can use a algorithm which works like the was processed by developed system. Nowicki et al. developed Sieve of Eratosthenes. By hand, we should create a table with intelligent processing of information in data mining with more numbers from 0 to 100, where 0 and 1 are not prime and not efficient categorization approach [14]. Similarly to architec- composite. We are starting our search from next number - 2, tures algorithms with dedicated structures and commands have which is prime so every multiplies of 2 are composite. Now we a great impact on development in computer science [10]. can cross off these numbers from the table. Next number which Carlsson et al. presented devoted sublinear sorting methods is left on the table is 3. We should remove every multiplies of 3 [5], Rauh proposed median based method [11]. Cole discussed and repeat the process until you find the last prime number less than 100. These are all steps of the implemented algorithm. To Copyright c 2016 held by the authors. apply it you should create a boolean table (the last element will be ’100’). A loop ’for’ assigns true to all elements. Second 28 loop ’for’ explore numbers from 2 to 100. If a constituent has a true value all its multiplies will be marked false. Every primes (with 0 and 1) are designated true now. The next step is to transfer all primes to separate array - there it will make necessary calculations. After preparing the base for computations the program is finding all combinations which meet the conditions (the sum is equal 100). Nested loops ’for’ (their amount depend on elements of the combinations) are searching every components of array. Conditional statements choose only these different from each other, whose sum is equal 100. Effective procedure requires eight steps - n-elements combinations need n nested Figure 1. Chart of time of summation (Nested loops, sum equals 100, part loops ’for’. If a combination meets the conditions, a method 1) ’Write’ from StreamWriter is saving a result to the files. Every stage is stored in separate places. This method is non-recursive. The Block Diagram of the general part of this program is showed on Fig. 11. An example of nested loops ’for’ (4- elements combinations) is presented in Fig. 12. B. Information about research and benchmark tests Presented methods had been written in C++ CLR Microsoft Visual Studio 2013. We would like to describe two points of view in numbers summation. After the presentation of algorithms we are going to compare these methods. Researches had been done with Stopwatch from System::Diagnostics class. The measurements were performed at two time units: seconds and CPU ticks. CPU clock cycle allow to estimate how fast a processor carries out essential operation. Data based on 100 Figure 2. Chart of time of summation (Nested loops, sum equals 100, CPU clock cycles, part 1) tests for all programs. The results are the arithmetic average. During the research has been used Intel Xeon CPU E3-1241 v3 3.50GHz. C. Analysis of efficiency This solution is not effective enough (compare to Fig. 1 - Fig. 4). The most important disadvantage is the length of calculation. Searching 2-7-elements combinations ends with success. There exist no 8-elements sequence and one 9- elements sequence that fills the conditions. A huge calculation causes slowing of computation. We should notice that the program permutes found combinations. It would be enough to write only one sequence. We have to eliminate duplications in files, ie. by our calculations based on the finding of repeated sequences without removing repetitions. You can see that Figure 3. Chart of time of summation (Nested loops, sum equals 100, part non-recursive method is inefficient, but still the results are 2) acceptable. Analyzing Table I we can see that searching time connected with 1 to 6-elements combination is relatively low but in case we have introduced computational technique that enables self for 7 and 9 elements is several times larger. There exist only recalling in procedures for more efficient processing. one 9-elements combination which meets task’s condition so we have stopped tests after finding a first sequence with correct A. Description solution. If you tried apply this idea in similar way for instance to find different primes which sum equals more than 100, you There exists other method to solve our problem. We can would get results even slower. use stacks (Last In First Out - LIFO) from namespace Sys- tem::Collections. As we will see, this solution is more efficient III. S TACKS - RECURSIVE METHOD and suitable. It is recursive method. The last algorithm was Let us now discuss possible improvement by application constructed only for one case (sum primes equals 100). In of recursive approach, where instead of repetition of cycles that situation you can easily change model. 29 Table I A NALYSIS OF EFFICIENCY - N ESTED LOOPS number of elements 2 3 4 5 6 7 9 average (in seconds) 0.000038197 0.00095737 0.00338778 0.0552465 1.1553366 31.1835792 21.2075880 minimum (in seconds) 0,000019900 0.00005150 0.00229490 0.0427253 1.1486146 30.9947676 21.1009756 average (in CPU ticks) 130.9 327 11576 148634 3947798 106554599 72466562 minimum (in CPU ticks) 68 158 7842 145993 3924829 105909462 72102266 Combined Minimum Time (in seconds) 53.2894494 Combined Average Time (in seconds) 53.6052720 Combined Minimum Time (in CPU ticks) 182090618 Combined Average Time (in CPU ticks) 183129627 Figure 4. Chart of time of summation (Nested loops, sum equals 100, CPU clock cycles, part 2) The first step is also finding all primes between 0 and 100. We can solve the problem similarly as before. The next stage is different. We should create two stacks: one "temporary" stack (a place, where we could store numbers) and nested stack which will collect sums equal 100. The construction is shown on Fig. 5. There could be used recursion connected with the amount of numbers. If the sum in "temporary" stack is more than 100, the algorithm will end the operation. A loop ’for’ gives to the stack primes (for instance "i") and runs recursion to "i-1". If the sum on the stack is equal 100, this result is added to nested stack (a collection of every solutions of our problem). The loop removes number "i" from the stack. The main part of the program is presented on Fig. 6. Optimal Figure 5. Block Diagram of the recursive program ’Stacks’ results are printed to the file. 1) Analysis of efficiency: This method is very efficient. Results are printed in one file and there is no repetition of our IV. C OMPARISON AND DISCUSSION combinations. You can get solutions faster than for previous There is a big difference between presented methods. The approach as it is presented in Tab. II. recursive program with stacks is several times faster than You can easy modify this algorithm. Last program was nested loops (non-recursive). We could see in Tab. I that constructed special for primes which sum is 100. In that option combined minimum time in case of nested loops is 53.2894494 you can write other sum - the algorithm is universal. It is seconds but complete time in case of recursion is 0.0025118 presented in Fig. 5 and Fig. 6. Using recursive searching with seconds. In addition clarity of results is much better. Moreover, stacks is most favorable. We were doing also a research with time necessary to finding every primes which sum equals 200 other sum. The program have found primes which sum is equal is also smaller than previous sum in nested loops: 0.272592 200. Results were very good: it was faster than finding last sum seconds. in the algorithm "nested loops". The algorithm in second method is universal but in first case 30 Table II A NALYSIS OF EFFICIENCY - S TACKS algorithm arithmetic mean (in seconds) arithmetic mean (CPU ticks) minimum (in seconds) minimum (in CPU ticks) 100 - recursion 0.00282584 9656.09 0.0025118 8583 200 - recursion 0.28448827 97212.83 0.272592 93415 Figure 8. Chart of time of summation (Stack, sum equals 100, CPU clock cycles) Figure 6. Block Diagram of the recursion in searching a specific sum. Figure 9. Chart of time of summation (Stack, sum equals 200) Figure 7. Chart of time of summation (Stack, sum equals 100) Figure 10. Chart of time of summation (Stack, sum equals 200, CPU clock cycles) 31 it could add loops which will explore more than 9-elements [13] M. Woźniak, M. Gabryel, R. K. Nowicki, and B. Nowak, “An application combinations. Structure of the method in ’nested loops’ is not of firefly algorithm to position traffic in nosql database systems,” Advances in Intelligent Systems and Computing - KICSS’2014, vol. 416, programmer friendly, since it is easy to get confused while pp. 259–272, 2016, DOI: 10.1007/978-3-319-27478-2_18. programming this approach, however the general idea can be [14] R. K. Nowicki, B. Nowak, and M. Woźniak, “Application of rough more clear for beginners. Recursive approach is not as easily sets in k nearest neighbours algorithm for classification of incomplete samples,” Advances in Intelligent Systems and Computing - KICSS’2014, understandable for beginners and may cause some problems in vol. 416, pp. 243–257, 2016, DOI: 10.1007/978-3-319-27478-2_17. understanding, however it’s structure is programmer friendly [15] D. Połap, M. Woźniak, C. Napoli, and E. Tramontana, “Is swarm and easily computed in implemented approach. intelligence able to create mazes?” International Journal of Electronics and Telecommunications, vol. 61, no. 4, pp. 305–310, 2015, DOI: 10.1515/eletel-2015-0039. V. C ONCLUSIONS [16] D. Połap, M. Woźniak, C. Napoli, and E. Tramontana, “Real-time We have compared two method implemented to determine cloud-based game management system via cuckoo search algorithm,” International Journal of Electronics and Telecommunications, vol. 61, summation primes. The recursive algorithm connected with no. 4, pp. 333–338, 2015, DOI: 10.1515/eletel-2015-0043. stacks is several times faster and it is useful in other cases. [17] Z. Marszałek, G. Woźniak, M. Borowik, R. Wazirali, C. Napoli, G. Pap- The speed of operation is much better and versatility of this palardo, and E. Tramontana, “Benchmark tests on improved merge for big data processing,” in Asia-Pacific Conference on Computer Aided method allow to apply it in every sums. Recursive algorithm System Engineering – APCASE’2015. 14-16 July, Quito, Ecuador: is very efficient in combinatorial summation of numbers. IEEE, 2015, pp. 96–101, DOI: 10.1109/APCASE.2015.24. [18] M. Woźniak, Z. Marszałek, M. Gabryel, and R. K. Nowicki, “Prepro- In the next research we plan to improve proposed approach cessing large data sets by the use of quick sort algorithm,” Advances by introduction of parallelization to the code, what can help in Intelligent Systems and Computing: Knowledge, Information and on more efficient processing and decrease computation time. Creativity Support Systems: Recent Trends, Advances and Solutions - KICSS’2013, vol. 364, pp. 111–121, 2015, DOI: 10.1007/978-3-319- Moreover it could be interesting to implement similar approach 19090-7_9. based on computational intelligence, to compare efficiency and [19] M. Woźniak, Z. Marszałek, M. Gabryel, and R. K. Nowicki, “Modified discuss possible advantages. merge sort algorithm for large scale data sets,” Lecture Notes in Artificial Intelligence - ICAISC’2013, vol. 7895, pp. 612–622, 2013, R EFERENCES DOI: 10.1007/978-3-642-38610-7_56. [20] M. Woźniak, D. Połap, R. K. Nowicki, C. Napoli, G. Pappalardo, and [1] M. Gabryel, “The bag-of-features algorithm for practical applications E. Tramontana, “Novel approach toward medical signals classifier,” in using the mysql database,” Lecture Notes in Artificial Intelligence - IEEE IJCNN 2015 - 2015 IEEE International Joint Conference on ICAISC’2016, vol. 9693, pp. 635–646, 2016, DOI: 10.1007/978-3-319- Neural Networks, Proceedings. 12-17 July, Killarney, Ireland: IEEE, 39384-1_56. 2015, pp. 1924–1930, DOI: 10.1109/IJCNN.2015.7280556. [2] R. Grycuk, M. Gabryel, M. Korytkowski, and R. Scherer, “Content- based image indexing by data clustering and inverse document fre- quency,” Communications in Computer and Information Science - BDAS’2014, vol. 424, pp. 374–383, 2014, DOI: 10.1007/978-3-319- 06932-6. [3] R. Grycuk, M. Gabryel, R. Scherer, and S. Voloshynovskiy, “Multi-layer architecture for storing visual data based on WCF and microsoft SQL server database,” Lecture Notes in Artificial Intelligence - ICAISC’2015, vol. 9119, pp. 715–726, 2015, DOI: 10.1007/978-3-319-19324-3. [4] D. Czerwinski, “Digital filter implementation in hadoop data mining system,” Communications in Computer and Information Sciences - CN’2015, vol. 522, pp. 410–420, 2015, DOI: 10.1007/978-3-319-19419- 6_39. [5] S. Carlsson, C. Levcopoulos, and O. Petersson, “Sublinear merging and natural merge sort,” Lecture Notes on Computer Science - SIGAL’1990, vol. 450, pp. 251–260, 1990, DOI: 10.1007/3-540-52921-7_74. [6] R. Cole, “Parallel merge sort,” SIAM Journal on Computing, vol. 17, no. 4, pp. 770–785, 1988, DOI: 10.1137/0217049. [7] L. Gubias, “Sorting unsorted and partially sorted lists using the natural merge sort,” Software Practice and Experience, vol. 11, no. 12, pp. 1339–1340, 2006, DOI: 10.1002/spe.4380111211. [8] B. Huang and M. Langston, “Practical in-place merging,” Com- munications of ACM, vol. 31, no. 3, pp. 348–352, 1998, DOI: 10.1002/spe.4380111211. [9] B. Huang and M. Langston, “Merging sorted runs using main mem- ory,” Acta Informatica, vol. 27, no. 3, pp. 195–215, 1989, DOI: 10.1007/BF00572988. [10] M. Lutz, L. Wegner, and J. Teuhola, “The external heap sort,” IEEE Transactions on Software Engineering, vol. 15, no. 7, pp. 917–925, 1989, DOI: 0098-5589/89/0700-0917. [11] A. Rauh and G. Arce, “A fast weighted median algorithm based on quick select,” in Proceedings of the IEEE 17th International Conference on Image Processing. 26-29 September, 2010, Hong Kong: IEEE, 2010, pp. 105–108. [12] R. Damaševic̆ius, M. Vasiljevas, J. Salkevicius, and M. Woźniak, “Hu- man activity recognition in aal environments using random projections,” Computational and Mathematical Methods in Medicine, vol. 2016, pp. 4 073 584:1–4 073 584:17, 2016, DOI: 10.1155/2016/4073584. 32 Figure 11. Block Diagram of the Program ’Nested loops’ 33 Figure 12. Example of loops for 4-elements combinations. 34