16 replies to this topic

[imdadullah]

This is my first post here.
I am working on a research. Its going well for approximately 000000000 number of iterations. But Now its taking a lot of time. The work that I am doing is...

I have lot of number like
101101101
203020401
030201001
000110202
110110110
001101010
010010010

They are different in length.

I do sum them with certain conditions.
Suppose I require a number 222222222 which can be obtained by the number 101101101 and 010010010 (i.e. from list of numbers there were three numbers that ads up to 222222222, they may be more).

for this purpose I am using nested loops.
for i=1 to n
for j=i+1 to n
for k=j+1 to n
for l=k+1 to n
------

Now as number of nested loop increases process slow down.
I also used the recursive technique too but problem is the same, because recursive loop starts from zero combination, while I require of specific size.

Hopefully all of you have understand it well.

I am waiting for positive response.

Thanks in advance.

[josep]

Quote

Can you please explain that a bit further,

Regards,

[josep]

Quote

This is my first post here.
I am working on a research. Its going well for approximately 000000000 number of iterations. But Now its taking a lot of time. The work that I am doing is...

On the first sentence

[abzero]

being that your nested loops gives O(n^4) it will slow down incredably quickly.

[Momerath]

This is close to the Knapsack Problem and I think you'll find it difficult if not impossible to speed up.

[zoranh]

Momerath said:

This is close to the Knapsack Problem and I think you'll find it difficult if not impossible to speed up.

This case seems to be less general than the knapsack problem in that numbers are positive. That can be solved quickly using dynamic programming, as every value in the array is consumed only once. This solution can be built to answer yes/no question "is there a way to sum up numbers into a given sum", or to produce a complete summation sequence that brings to the desired sum.

[bobdark]

try concurrent programming.

[zoranh]

bobdark said:

try concurrent programming.

What do you mean? If you have algorithm running in O(N^p) time and you run it on M CPUs, then it is still O(N^p), regardless of M.

If you have 10^20 steps to execute and you run it on 10 CPUs, it is still equivalent of 10^19 steps - so what would you gain if it executes till the end of the world anyway.

[bobdark]

I thought we were talking about practical inputs. This is a research, the purpose (as I see it) is to get results faster when given input practical for research and not for REAL WORLD PROBLEMS! And I didn't say not to take any other measures.

[zoranh]

If you get only ten numbers between 1 and 10, and request number 100 to be formed, and you search for the solution using brutal force, then you've already got 10^13 iterations on average, which will take hours at least to execute. There's nothing more real world than that, this example is so simple and it can't be solved by force.

Better algorithm with polynomial complexity must be used. If you use dynamic programming solution for the same example, number of iterations is roughly 2000, which can be done on a mobile phone in split second. So no need for any hardware optimizations, only a good algorithmic approach.

[imdadullah]

zoranh said:

This case seems to be less general than the knapsack problem in that numbers are positive. That can be solved quickly using dynamic programming, as every value in the array is consumed only once. This solution can be built to answer yes/no question "is there a way to sum up numbers into a given sum", or to produce a complete summation sequence that brings to the desired sum.

Yes it is from Combinatorial Problem.
Yes there is a way to sum up numbers into a given sum (the simplest one is by using the nested loops)
I have to produce a complete summation sequence that brings to the desired sum.

[imdadullah]

josep said:

On the first sentence

Actually using the nested loop techniques the code that is being used by me takes many of the iterations i.e. in millions. but when nested loops increases more than 5 it becomes almost impossible to run the program because of millions of millions iterations.
I want to avoid to use lot of nested loops. is there any way to solve my problems.