Re: Help with an algorithm

[Dirk Laurie <dirk.laurie@...>]

2013/5/26 Vaughan McAlley <vaughan@mcalley.net.au>:

> I’m laying an area of pavers 8 wide by 5 down, with dark and light pavers
> available. I wanted to do an ‘interesting’ pattern... being fond of the
> golden ratio and noticing 8 & 5 are Fibbonaccci numbers, I thought I could
> encode a 40-bit number that when read from the (right) side, is the golden
> ratio away from when it is read from the bottom.

Aha! We have a definition of "interesting". This task can be done with
much less computation.

Try all possible first rows. For each, fill the remaining elements
with all zeros and all ones. Multiply the number by phi. If the smallest
result is greater than 2^40, throw away that row. Otherwise, convert
those smallest and largest values to 40 bits. They'll agree to 7 bits,
so that gives you the first column. If it disagrees with the first row
where they cross, throw away that first row. Otherwise, you have 7 bits
of the second row to try. Etc.