Hallo, folks!

My name is Oliver, I'm interested in maths, computer science, and combinatorial problems.

I've been studying The Art of Computer Programming by Donald E. Knuth, working on some of the exercises and some of the open problems. In Volume 4A, chapter 7.1.2 the topic of boolean chains comes up. Basically, it's about a chain of boolean operations on some input values x_1, ..., x_n and intermediate results of those operations, such that a set of desired functions f_1, ..., f_m on those inputs can be evaluated. The goal is to make such a chain as small as possible, because that makes for small circuitry with fewer parts.

One example Knuth chose is the segments of a digital display, as we know it from (somewhat dated) alarm clocks or quartz watches. The inputs are the four bits of a number 0 to 15 (we want hexadecimal digits) and the seven output functions are whether each of the segments of the display should be turned on or off for that digit.



My goal is to find the minimal boolean chain for this problem, hoping to come up with some new algorithms or speed improvements to make this feasible; so that similar problems can be solved in the future. I've already found shorter boolean chains with an algorithm described on the website below, but to prove it is optimal I need to do an exhaustive search. I also suspect that there still are chains that are ONE step shorter than the one I found, based on the trajectory of smaller problems already solved, but for that I also need the exhaustive search.
Details of the project: https://orunge.org/boolean-chains/

I've already covered a large search space with my own machine and AWS Batch, but that approach will be too costly. That's where I hope BOINC Central can help!
Results can be tracked here: https://orunge.org/boolean-chains/#results-full

Please reach out if you are interested in more details.

Oliver

In reply to or's message of 29 Apr 2025:

Hallo, folks!

My name is Oliver, I'm interested in maths, computer science, and combinatorial problems.

I've been studying The Art of Computer Programming by Donald E. Knuth, working on some of the exercises and some of the open problems. In Volume 4A, chapter 7.1.2 the topic of boolean chains comes up. Basically, it's about a chain of boolean operations on some input values x_1, ..., x_n and intermediate results of those operations, such that a set of desired functions f_1, ..., f_m on those inputs can be evaluated. The goal is to make such a chain as small as possible, because that makes for small circuitry with fewer parts.

One example Knuth chose is the segments of a digital display, as we know it from (somewhat dated) alarm clocks or quartz watches. The inputs are the four bits of a number 0 to 15 (we want hexadecimal digits) and the seven output functions are whether each of the segments of the display should be turned on or off for that digit.



My goal is to find the minimal boolean chain for this problem, hoping to come up with some new algorithms or speed improvements to make this feasible; so that similar problems can be solved in the future. I've already found shorter boolean chains with an algorithm described on the website below, but to prove it is optimal I need to do an exhaustive search. I also suspect that there still are chains that are ONE step shorter than the one I found, based on the trajectory of smaller problems already solved, but for that I also need the exhaustive search.
Details of the project: https://orunge.org/boolean-chains/

I've already covered a large search space with my own machine and AWS Batch, but that approach will be too costly. That's where I hope BOINC Central can help!
Results can be tracked here: https://orunge.org/boolean-chains/#results-full

Please reach out if you are interested in more details.

Oliver

the wu in progress on the project concern chain boolean?

Yay! Great to see that we've completed at least 5% already.
I hope it's okay that I copied this information here: https://boincsynergy.ca/wiki/index.php/BOINC_Central

---

In reply to fzs600's message of 29 Apr 2025:

In reply to or's message of 29 Apr 2025:
the wu in progress on the project concern chain boolean?

Hey, I didn't have notifications on, so I just saw this.
I'm not sure what you mean, is "wu" work unit? In that case yes, all the jobs are looking for boolean chains as described on the site.

In reply to Contact's message of 2 May 2025:

Yay! Great to see that we've completed at least 5% already.
I hope it's okay that I copied this information here: https://boincsynergy.ca/wiki/index.php/BOINC_Central

That's cool, thank you.

And now the search space is 100% done for N=15, max length 17, very cool!
I've since started a few batches to look for N=16, L=18, which is the actual goal. If there is such a chain, then the exhaustive search for length 17 proves L=18 is optimal.

I noticed the work units have max # of error/total/success tasks set to 1, 1, 1. Doesn't an aborted or failed task create gaps in your progress?

Good observation! Short answer: I partition the search space into many random chunks, and if some of them fail, then I can just collect them and group them in a new batch later.

Unfortunately it's not easy to predict the processing duration of one chunk, some might turn out to take 10 times longer than others. I try to mitigate this by making much smaller chunks and grouping many of them randomly into one job, so on average the jobs take roughly the same time.

In previous batches when I allowed more retries, some batches didn't complete for quite a while, due to the last few jobs that kept retrying and failing because the chunk was too big for the expected duration.

In recent batches with the smaller chunks the failed ones are usually due to some client issues, but even if it is because the chunk is too big, I can make a new batch that breaks the chunks up even further.

Thanks for the explanation!

In reply to or's message of 28 Jul 2025:

Good observation! Short answer: I partition the search space into many random chunks, and if some of them fail, then I can just collect them and group them in a new batch later.

Unfortunately it's not easy to predict the processing duration of one chunk, some might turn out to take 10 times longer than others. I try to mitigate this by making much smaller chunks and grouping many of them randomly into one job, so on average the jobs take roughly the same time.

In previous batches when I allowed more retries, some batches didn't complete for quite a while, due to the last few jobs that kept retrying and failing because the chunk was too big for the expected duration.

In recent batches with the smaller chunks the failed ones are usually due to some client issues, but even if it is because the chunk is too big, I can make a new batch that breaks the chunks up even further.

Hello Oliver,
Please see the post regarding the topic of wastage:
https://boinc.berkeley.edu/central/forum_thread.php?id=75
If the task only have quorum of 1, when a task is in progress by the first host and not yet expired, the task should not be replicated and send to a second host during that time, at least in theory. Somehow a few us are seeing this issue. Anyway, I found a temporary solution by reducing the work cache to about 1 day. Initially I had more than a day of work and some of my older tasks (not yet expired) are been sent to other hosts during that time causing my returned completed tasks not getting any credit as the second host crunched the same task and completed ahead of me.

If you need to have all the tasks in a batch to be completed quickly, probably the best way is to reduce the deadline but this will upset folks with very slower computer or reduce the size of the work cache per host but some experience boinc volunteers know how to bypass that limitation.

The search for a boolean chain of length 18 is now complete! No such search was found, in over 450 years of computing, proving the chain of length 19 to be optimal.

The results are here: https://orunge.org/boolean-chains/#results-full (there's also a section below explaining methodology around verification and dealing with some corrupt results).
Summary: https://orunge.org/boolean-chains/#conclusion

Thanks to everybody providing computation time to make this result possible!

In reply to or's message of 9 Mar 2026:

The search for a boolean chain of length 18 is now complete! No such search was found, in over 450 years of computing, proving the chain of length 19 to be optimal.

The results are here: https://orunge.org/boolean-chains/#results-full (there's also a section below explaining methodology around verification and dealing with some corrupt results).
Summary: https://orunge.org/boolean-chains/#conclusion

Thanks to everybody providing computation time to make this result possible!

Great. So is this project completed and no plan for a new search in the near future?

In reply to pututu's message of 9 Mar 2026:

In reply to or's message of 9 Mar 2026:
Great. So is this project completed and no plan for a new search in the near future?

The main problem I set out to solve is done. But there are some adjacent problems that could be solved with the same program, I'll look into that sometime. I might do a few batches of those, but nothing of the scale of the full search we just completed.

If I have something bigger, then I'll make a post and give more details!

In reply to or's message of 10 Mar 2026:

In reply to pututu's message of 9 Mar 2026:

In reply to or's message of 9 Mar 2026:
Great. So is this project completed and no plan for a new search in the near future?

The main problem I set out to solve is done. But there are some adjacent problems that could be solved with the same program, I'll look into that sometime. I might do a few batches of those, but nothing of the scale of the full search we just completed.

If I have something bigger, then I'll make a post and give more details!

So, is the project finished?