Commit Graph
27 Commits
Author SHA1 Message Date
starcells e632fb4824 Rewrite the searcher: bit planes, and the last block searched backwards
The BFS used to walk the whole 1<<CELL_SIZE table for every edge, keep the
states in an unordered_set and the parents in a second unordered_map.  For
the six plane full adder layer 4 is 642729 states, and layer 5 never
finished (75s, heading for GBs).

A state is now CELL_SIZE bit planes, each a truth table over only the
inputs that influence the answer, so a state is CELL_SIZE * 2^K bits --
48 bits for every adder-shaped problem -- and a block is a handful of
64-bit ops.  The instruction list also lost its duplicated encodings
(378 instead of 762 for six planes).

The bigger win is not expanding the last layer at all.  A block clears its
own plane, so for the goal to be its target goal[s] must be 0; the
preimages of the goal under each such block are enumerated exactly and
looked up in the BFS table.  For full_add that is 9.3e3 lookups instead of
7.4e9 edges, which turns "unreachable" into "5 blocks, proven shortest,
7 seconds".

Results (r8veritas<6>, max_depth 5, MSVC /O2):

    copy          2   33 states
    clb_and       3   3398
    clb_half_add  4   32898
    half_add      4   32898
    full_add_S    4   656528
    full_add_Co   5   20388515
    full_add      5   20388515      7.2s

All of those lengths are proven minimal, and the old bit_raw_add needed
eight blocks for the same slice.

Richer instruction sets were tried as well -- per destination OR/XOR, and
adding set_0 on top (6144 blocks) -- and neither admits a four-block full
adder, so five is not an artifact of the model.

CELL_SIZE stays a template parameter; the truth table compression picks K
at run time and dispatches on it.  CMake flags got the same fix as r8asm:
stop clobbering CMAKE_CXX_FLAGS so Debug keeps /RTC1 and MSVC keeps /EHsc.
2026-11-05 23:35:56 +08:00
starcells e1912694ad 202608241718 2026-08-24 17:18:10 +08:00
starcells 237dde9c36 202608231343 2026-08-23 13:43:54 +08:00
starcells de3f2b220b sorted all_ins,now ins with less operand in mask will be calculated preferentially 2026-08-23 09:28:23 +08:00
starcells bb49cff992 removed remembered_stats 2026-08-16 13:32:10 +08:00
starcells 0e16b24a5c encapsulated r8veritas class 2026-08-14 18:21:59 +08:00
starcells 03889e7874 [err]202608141801 2026-08-14 18:01:06 +08:00
starcells 9346a5ad89 removed visited_stat,SAVED 2/3 OF RUNTIME 2026-08-14 01:26:28 +08:00
starcells 33b22276fb 202608081522 2026-08-08 15:23:14 +08:00
starcells a75704a4c0 202607301828 2026-07-30 18:28:19 +08:00
starcells 95f27efb43 202607292009 2026-07-29 20:09:23 +08:00
starcells 39f426fcb3 202607292006 2026-07-29 20:06:51 +08:00
starcells eb8051206e Added debug output format. 2026-07-29 17:51:18 +08:00
starcells 09871417c9 Improved make flag 2026-07-25 19:02:10 +08:00
starcells 72b7bf89a2 bit_add 2026-07-25 18:14:05 +08:00
starcells 3e873c4f8e [err]202607251724 2026-07-25 17:24:35 +08:00
starcells 50480ffe04 [err]202607251632 2026-07-25 16:32:47 +08:00
starcells edc2c63f14 use remembered_stat 2026-07-25 01:08:13 +08:00
starcells 39ff890215 use visited_cell to decrease stats 2026-07-25 00:46:46 +08:00
starcells 8f0cc306b5 use unordered_set for stat_pool to speed up 2026-07-24 23:42:47 +08:00
starcells d441982dad use stat_ref and stat_pool instead of stat 2026-07-24 23:17:36 +08:00
starcells f42aca2e4f 202607242142 2026-07-24 21:42:48 +08:00
starcells ef35a553b3 [err]202607242120 2026-07-24 21:20:15 +08:00
starcells 491e8a86eb [err]202607242108 2026-07-24 21:08:47 +08:00
starcells a46246810c [err]202607242043 2026-07-24 20:43:34 +08:00
starcells d87d69686b 202607240143 2026-07-24 01:43:18 +08:00
starcells 2358c9a3e6 [err]202607231240 2026-07-23 12:40:40 +08:00