Report the bounds along with the search results.

Python code to compute upper bounds on the solution.

Since I now know of two different ways to prove an upper bound, here's
a piece of code which tries both, picks the lowest, and explains which
one gave rise to the number it returns.

Written a post-analyser for the search output.

This converts the floats into rationals by what I think is a more or
less sensible method (selecting the lowest possible denominator and
then double-checking afterwards that the result of rounding to
multiples of 1/d is still a legal dissection and doesn't decrease the
min frag by more than rounding error) and collapses the matrix
dissections into mere descriptions of how the sticks are cut up.

Don't call set_best before setting m and n.

Fixes obvious goof if you run 'main 12 7 -b 2.9' - you get an
immediate termination quoting n_max_frags and m_max_frags as -1.

Introduce a 'make clean' target.

While I'm faffing about with the Makefile anyway, it seemed like a
good idea.

Introduce a 'make test' target.

This checks the expected results for all the easy cases, both in
single-core mode and repeatedly in multicore mode (to try to smoke out
intermittent errors like the negative-max-frags bug fixed a couple of
commits ago).

Compare against n_max_frags with <=, not <.

It would be legal to use < if n_max_frags was exactly equal to n/best
(in that case we would know that dividing a stick into that many
pieces could at best equal the existing best score), but not if it's
merely floor(n/best) since then we might have previously seen an
_uneven_ dissection of a stick into that many pieces, which could be
beaten by an even one.

Reinstates the ability to do 7 into 4 with score 5/3 instead of the
3/2 reported by the previous version.

Fix occasional 'min fragment 1.11022e-16' glitch.

Seems to happen in multicore mode when the first worker reports a
near-zero value of 'best', and then set_best reduces it to a negative
number when it applies the rounding fudge, leading to the max_frags
limits being set to negative things and all other workers' results
being thrown away in preconsider_ok().

fix output reporting again

make -b<startbest> more effective by moving initialisation of {n,m}_max_frags earlier

multicore worker only print read matrix input every second

actually parse -b option

report something to stdout even if no answer

report some more stuff in stderr output

split up stdout heading output line printing (no functional change)

report best_adjmatrix in that form

option for starting best value

document -j option in head comment

fudge the {n,m}_max_frags to deal with rounding errors in glpk results

use "git describe" not "git-describe"

move minham check earlier; this avoids some printing etc

apparent speedup of -j4 9 7 on zealot is about 10%

minimum output match hamming weight; enforce argument ordering

This seems to provide a very dramatic speedup.

.gitignore: profiling output files

commentary: document new criterion introduced in ea5f3526c7c0

commentary: clarify and fix input vs output confusion

add one missing call to FOR_BITS (no functional change)

{n,m}_max_frags: fix fencepost efficiency problem

fixes the bug discovered/exacerbated in 41013cb05383

rename {n,m}_over_best to {n,m}_max_frags to reflect way used in most of the code

introduce m_over_best and use it instead of computing maxminsize

XXX makes things slower, perhaps has bug ?!

move had_max and totalfrags update later in loop body (no functional change)

provide and use FOR_BITS

this seemed like it would make it faster but doesn't appear to have done so

provide CMDLINE_CFLAGS feature

This can be used for profiling etc.

remove some debugging newlines (mistakenly included in previous commit)

multicore: in master, when collecting results, pay no attention to bus and look only at our own best

only report "reporting" if we actually have something

show git version in output

pass weight array to workers (fix semantic conflict between horizontal weight elimination and multicore)

move -lm to LDLIBS where it ought to be

apply floor to n_over_best

add <math.h> and -lm (no functional change)

Merge remote-tracking branch 'sgt/master'

Changes made to the new code in sgt/master:
  - use "-std=gnu99" not "--std=gnu99"
  - n_over_best calculation is in set_best
  - n_over_best initialised properly
 style:
  - use calloc, do not cast return value from int, better sizeof
  - extra blank line

Conflicts:
Makefile
main.c

break out set_best

in multicore, generator periodically checks for new best to avoid generating many pointless suggestions

in mc_iterate_worker, use maxhamweight_ok and preconsider_ok on incoming suggestions (for quicker elimination)

break out maxhamweight_ok (no functional change)

predeclare preconsider_ok and multicore_check_for_new_best (no functional change)

tiresome portability fix for pread on squeeze

multicore support seems to work

.gitignore: core, t.*

introduce progress_eol and make stderr line buffered

in preconsider_ok, check for frags >= maxhamweight so we can force this to pass by setting maxhamweight

break out preconsider_ok

PRINTF is less bodgy now

Add -std=gnu99 to Makefile

break out report()

wip multicore: add argument parsing; currently -j option is actually ignored

Check max Hamming weight in the other direction.

Once we've already got a solution, we can further winnow the set of
possible adjacency matrices, by ensuring the same bit is not set in
too many entries of adjmatrix (since if it were, some length-n stick
would have to be divided into enough pieces to make one at most the
already-known best result). This adds complexity to each step of the
recursion over possible matrices, but by early pruning it seems to cut
down the number of steps by rather more; I estimate a factor of four
speedup in pursuit of (n,m)=(10,7).

Prune by symmetry: constrain 1st adj row to all 1s at low end.

Separate stdout from stderr.

Output the actual dissection, as a matrix.

commentary

assert our arguments

do not leak prob when retrying

search in order by max hamming weight

Revert "loop in reverse order - this is a better search path"

This reverts commit 35e60acecf2f2657a3fd53f89053de9e57a0d7fe.

Doesn't actually seem to help that much.

loop in reverse order - this is a better search path

Revert "mix up the order" and "mix up the order"

This is not correct; I think it doesn't in fact search all relevant
bit patterns.

mix up the order, print better

mix up the order

error fixes; tried interior but doesn't work (EINSTAB) and docs say cannot cope with dense columns of which our X_minimum is one

print best solution

improve maxminsize thing

fix printing more

less printing, optimise

output improvements

wip lp seems to work so far...

wip lp, results, compiles

wip lp, problem setup compiles

wip lp

wip lp notes before condense

wip, builds, before glpk

wip