List of combinations

[MaxV]

Hi,
probably I missed something, but...
how can I parrallel a repeat loop? I have computers from 4 to 8 CPUs, and I'd like to use them all to shorten the computation time.

[[-hh]]

You have now an inductive method with file i/o and also a direct recursive method.

You can also start the induction at higher n than 1 by computing combin(n,k) 'directly' with the recursive method for all k for that fixed n and then use the inductive method.

So you have only to manage the file I/O between your CPUs and prepare hundreds of TeraBytes of disk space.

That's like in real life: 60-70% is administration only and 30-40% do the job.

[MaxV]

I was asked to script the "inductive law" for building lists of combinations.
So here it is.
...
Now have fun!

Well, I just understand your code, this is what it does, I suppose:

1. buildcombiBib n create files to reduce calculations, it creates ALL combinations from k=1 to k=n
2. inductiveCombi a looks for files created from buildcombiBib n to create the next file for combinations. It creates just the next combinations file.

Files are named like out(003of009).txt, that means .
So, it would speed up calculation only if I launch many times inductiveCombi n, but just if I already I know to have the previous files.
Is it right?
If so, it take more time than a normal nested repeat loops. If I have 8 CPU, I have 7 sleeping and just one working.

It would be better for any occasion that I could use:

Code: Select all

repeat..
  repeat..
    repeat...
     do this commands on the first CPU available
     ....
    end repeat
  end repeat 
end repeat

[FourthWorld]

@FourthWorld

Why have file I/O inside the loop?

When computing combin(n,k) for k=ceil(n/2) you are, roughly, doubling the size of combin(n-1,k) for k=ceil((n-1)/2).

combin(19,10) has size 2.3 Mbyte
combin(20,10) has size 4.7 MByte
combin(21,11) has size 10.0 MByte
combin(22,11) has size 20.1 MByte

Around (n=32,k=16) you will have crossed 1 GByte size for combin(n,k).
And combin(33,17) is built using combin(32,17) and combin(32,16) ...
And combin(42,21) alone may go close to the limit of your hardware resources (has 538257874440 lines of roughly length 100 each).

If you go high enough, this I/O must be even splitted into parts of files inside the repeat. And other 'compressed' methods of data storing (not decimal bytewise but bitwise) should come in.

Good point on file I/O, but it raises the question: how is this large output to be used? What is the goal of this exercise?

[[-hh]]

@MaxV
inductivecombi n computes a full single step n->n+1:
It needs the files n over k for k=0,...,n as input and computes the files (n+1) over k for k=0,...,n+1.

The input files n over k for k=0,...,n can also be computed directly (using the recursive method).

So, for example

• CPU 1 computes n over k for all k<=n and n up to 20 using inductivecombi.
• CPU 2 starts with n=20 and computes first directly (using the recursive method)
  20 over k for k=0,..,20 and then, with inductivecombi, n over k for all k<=n and n from 21 up to 25.
• CPU 3 starts with n=26 and computes first directly (using the recursive method)
  26 over k for k=0,..,26 and then, with inductivecombi, n over k for all k<=n and n from 27 up to 30.
• ....

You have to find out the optimal "steps" for that.

Or use two CPUs for the direct computations when k is near n/2.

And you need at least one CPU for administrating the callbacks and the queuing of the jobs. And you have soon to split the files if you don't have TeraBytes of RAM.

@FourthWorld

Good point on file I/O, but it raises the question: how is this large output to be used? What is the goal of this exercise?

combin(42,21) alone has length (538257874440 lines of roughly length 60 each*) > 32 Terabytes ... It's a 'virtual' exercise only.

___________
length 100 was wrong, sorry.