=Paper=
{{Paper
|id=Vol-1730/p05
|storemode=property
|title=Combinatorial Summation Primes: a Discussion of Different Methods to Solve the Problem
|pdfUrl=https://ceur-ws.org/Vol-1730/p05.pdf
|volume=Vol-1730
|authors=Kamil Ksiazek,Zbigniew Marszałek
|dblpUrl=https://dblp.org/rec/conf/system/KsiazekM16
}}
==Combinatorial Summation Primes: a Discussion of Different Methods to Solve the Problem==
https://ceur-ws.org/Vol-1730/p05.pdf
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