-This paper illustrates combinatorial summation numbers by means of computer operations. The aim of the research is to give a definition of all different primes which sum is equal 100, where the smallest combination has only two elements and the biggest has nine elements. This paper presents some ways to deal with this problem. There are analyzed two methods. One of them uses nested loops (non-recursive method), second way is connected with stacks (recursive method).
Index Terms—prime, summation, stack, loop, analysis, recursion
The computational complexity of algorithms, one of the most important problem of computer science, is clearly one of the most important aspects of computer science. Although computers repeatedly increased its computing power, still micro machines are working on acceleration of existing algorithms. The problem remains an open question whether the higher performance algorithms are recursive, or may not recursive versions are faster.
There are reported many approaches to increase
computational efficiency. Gabryel presented devoted methods to
implement in data base systems, where implemented method serve
as efficient tool for data management in high performance SQL
environments [
This paper presents benchmark tests on improvements in computer methods by introduction of non recursive algorithm in comparison to its regular version. In the following sections we present different versions of combinatorial algorithm for determining the sum of the set of numbers using primes. Performance tests show the effectiveness of the proposed algorithm operating on the stake.
In the research on efficiency of non recursive approach we have implemented two versions of algorithm used for combinatorial summation of primes that comply condition that a sum is equal 100.
A prime is a number which has only two divisors: 1 and itself. The initial step is isolation primes from first 100 numbers. You can use a algorithm which works like the Sieve of Eratosthenes. By hand, we should create a table with numbers from 0 to 100, where 0 and 1 are not prime and not composite. We are starting our search from next number - 2, which is prime so every multiplies of 2 are composite. Now we can cross off these numbers from the table. Next number which is left on the table is 3. We should remove every multiplies of 3 and repeat the process until you find the last prime number less than 100. These are all steps of the implemented algorithm. To apply it you should create a boolean table (the last element will be ’100’). A loop ’for’ assigns true to all elements. Second 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 loops ’for’. If a combination meets the conditions, a method ’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’ (4elements combinations) is presented in Fig. 12.
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 tests for all programs. The results are the arithmetic average. During the research has been used Intel Xeon CPU E3-1241 v3 3.50GHz.
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 9elements 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 non-recursive method is inefficient, but still the results are acceptable.
Analyzing Table I we can see that searching time connected with 1 to 6-elements combination is relatively low but in case for 7 and 9 elements is several times larger. There exist only one 9-elements combination which meets task’s condition so we have stopped tests after finding a first sequence with correct solution. If you tried apply this idea in similar way for instance to find different primes which sum equals more than 100, you would get results even slower.
we have introduced computational technique that enables self recalling in procedures for more efficient processing. There exists other method to solve our problem. We can use stacks (Last In First Out - LIFO) from namespace System::Collections. As we will see, this solution is more efficient and suitable. It is recursive method. The last algorithm was constructed only for one case (sum primes equals 100). In that situation you can easily change model.
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 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 combinations. You can get solutions faster than for previous approach as it is presented in Tab. II.
You can easy modify this algorithm. Last program was constructed special for primes which sum is 100. In that option you can write other sum - the algorithm is universal. It is presented in Fig. 5 and Fig. 6. Using recursive searching with stacks is most favorable. We were doing also a research with other sum. The program have found primes which sum is equal 200. Results were very good: it was faster than finding last sum in the algorithm "nested loops".
There is a big difference between presented methods. The recursive program with stacks is several times faster than nested loops (non-recursive). We could see in Tab. I that combined minimum time in case of nested loops is 53.2894494 seconds but complete time in case of recursion is 0.0025118 seconds. In addition clarity of results is much better. Moreover, time necessary to finding every primes which sum equals 200 is also smaller than previous sum in nested loops: 0.272592 seconds.
The algorithm in second method is universal but in first case it could add loops which will explore more than 9-elements combinations. Structure of the method in ’nested loops’ is not programmer friendly, since it is easy to get confused while programming this approach, however the general idea can be more clear for beginners. Recursive approach is not as easily understandable for beginners and may cause some problems in understanding, however it’s structure is programmer friendly and easily computed in implemented approach.
We have compared two method implemented to determine summation primes. The recursive algorithm connected with stacks is several times faster and it is useful in other cases. The speed of operation is much better and versatility of this method allow to apply it in every sums. Recursive algorithm is very efficient in combinatorial summation of numbers.
In the next research we plan to improve proposed approach by introduction of parallelization to the code, what can help on more efficient processing and decrease computation time. Moreover it could be interesting to implement similar approach based on computational intelligence, to compare efficiency and discuss possible advantages.