COLLATZ_PARALLEL
Parallel Execution of a Collatz Program

COLLATZ_PARALLEL is a MATLAB program which seeks the length of the longest Collatz sequence between 1 and N, running in parallel under MATLAB's "parfor" command.

A Collatz sequence starting at the integer I computes the next term by halving the number if it is even, or tripling and adding 1 if it is odd. The sequence stops when the value 1 is reached.

The number of steps required to reach 1 varies greatly. No formula has been determined, and in fact, it hasn't actually been proved that the value of 1 will always be reached.

An interesting question, suitable for parallel execution, is to ask for the length of the longest Collatz sequence between 1 and N.

If we multiply N by 10 repeatedly, here are the values we get for an integer with the longest sequence, and the sequence length:

N Initial I Sequence length

10 9 20

100 97 119

1,000 871 179

10,000 6,171 262

100,000 77,031 351

1,000,000 837,799 525

10,000,000 8,400,511 686

N	Initial I	Sequence length
10	9	20
100	97	119
1,000	871	179
10,000	6,171	262
100,000	77,031	351
1,000,000	837,799	525
10,000,000	8,400,511	686

On the Ithaca cluster computer, using the "collatz_ithaca_run.m" script, the following results were observed for the elapsed time in seconds:

N 1+0 1+1 1+2 1+4 1+8 1+16 1+32 1+64

1,000 0.005 0.272 0.240 0.325 0.501 0.477 0.627 0.708

10,000 0.069 0.105 0.061 0.050 0.071 0.155 0.199 0.430

100,000 0.610 0.620 0.336 0.191 0.213 0.136 0.203 0.374

1,000,000 7.442 7.392 3.711 1.903 1.176 0.595 0.358 0.411

10,000,000 88.514 87.541 44.813 22.132 13.053 6.103 3.053 1.598

N	1+0	1+1	1+2	1+4	1+8	1+16	1+32	1+64
1,000	0.005	0.272	0.240	0.325	0.501	0.477	0.627	0.708
10,000	0.069	0.105	0.061	0.050	0.071	0.155	0.199	0.430
100,000	0.610	0.620	0.336	0.191	0.213	0.136	0.203	0.374
1,000,000	7.442	7.392	3.711	1.903	1.176	0.595	0.358	0.411
10,000,000	88.514	87.541	44.813	22.132	13.053	6.103	3.053	1.598

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Related Data and Programs:

BIRTHDAY_REMOTE, a MATLAB program which runs a Monte Carlo simulation of the birthday paradox, and includes instructions on how to run the job, via MATLAB's BATCH facility, on a remote system such as Virginia Tech's ITHACA cluster.

COLLATZ, a MATLAB library which computes and analyzes the Collatz sequence (or "hailstone" sequence or "3n+1 sequence");

FDI_OPT, a MATLAB program which demonstrates the use of MATLAB's FMINCON constrained minimization function, taking advantage of MATLAB's Parallel Computing Toolbox for faster execution.

JTB_CODIST, a MATLAB program which demonstrates how the linear system associated with a finite element problem can be treated as a codistributed array whose entries are assigned to different MATLAB workers, so that the matrix is assembled in parallel.

LINEAR_SOLVE_DISTRIBUTED is a MATLAB program which solves a linear system A*x=b using MATLAB's spmd facility, so that the matrix A is "distributed" across multiple MATLAB workers.

MATLAB_PARALLEL, examples which illustrate "local" parallel programming on a single computer with MATLAB's Parallel Computing Toolbox.

MD_PARALLEL is a MATLAB program which carries out a molecular dynamics simulation in parallel, using MATLAB's "PARFOR" feature.

PRIME_NUMBER_PARALLEL is a MATLAB program which counts the number of primes between 1 and N; it runs in parallel using MATLAB's "parfor" facility.

PRIME_NUMBER_SPMD is a MATLAB program which counts the number of primes between 1 and N; running in parallel using MATLAB's "SPMD" feature.

QUAD_SPMD is a MATLAB program which estimates an integral using quadrature; running in parallel using MATLAB's "SPMD" feature.

SATISFIABILITY_PARALLEL is a MATLAB program which demonstrates, for a particular circuit, an exhaustive search for solutions of the circuit satisfiability problem, running in parallel using MATLAB's "PARFOR" feature.

TIMING_PARALLEL is a directory of MATLAB programs which illustrates how to time a parallel MATLAB program.

Reference:

Jeremy Kepner,
Parallel MATLAB for Multicore and Multinode Computers,
SIAM, 2009,
ISBN13: 978-0-898716-73-3,
LC: QA76.58.K46.
The MathWorks,
Parallel Computing Toolbox 4,
User's Guide.
Michael Quinn,
Parallel Programming in C with MPI and OpenMP,
McGraw-Hill, 2004,
ISBN13: 978-0071232654,
LC: QA76.73.C15.Q55.
Eric Weisstein,
"The Collatz Problem",
CRC Concise Encyclopedia of Mathematics,
CRC Press, 2002,
Second edition,
ISBN: 1584883472,
LC: QA5.W45.

Source Code:

collatz_parallel.m, the program, which includes a "parfor" statements for parallel execution.

Examples and Tests:

COLLATZ_LOCAL_RUN runs the program on a single machine, in "local" mode.

collatz_local_run.m, a script which runs the program on a single machine, in "local" mode.
collatz_local_run_00.txt, output from a run with 0 workers (so all the work is done by the client).
collatz_local_run_01.txt, output from a run with 1 worker.
collatz_local_run_02.txt, output from a run with 2 workers.
collatz_local_run_04.txt, output from a run with 4 workers.

COLLATZ_ITHACA_RUN runs the program on the Ithaca cluster, in "interactive" mode.

collatz_ithaca_run.m, a function to run the program on the Ithaca cluster, from the MATLAB comand line, in which case up to 64 workers can be requested.

COLLATZ_BATCH_RUN runs the program on the Ithaca cluster, using the "batch" command. A sample use might be

batch ( 'collatz_batch_run.m', 'Configuration', 'ithaca', 'matlabpool', 4 )

where the 'ithaca' configuration must be set up and validated first.

collatz_batch_run.m, a script which can be used to run the program in batch mode.

You can go up one level to the MATLAB source codes.