universal-headers
universal-headers copied to clipboard
ziglang
Quine-McCluskey
On stream yesterday Andrew tried to simplify this logic: https://clbin.com/4Rstp it is 1584 lines and 196124 characters
This is the output of Quine-McCluskey: https://clbin.com/vuHiW it is 126 lines and 10120 characters. There is one boolean function being optimized for every segment that a boolean target (i.e. SYS_APPLEAPIOPTS_H) remains constant, there are 18 such segments in the code.
It still does not have nesting which would further reduce the number of characters. The Quine-McCluskey algorithm gives output in a form where it is natural to look for common terms to factor out).
Thanks for sending this! These are some nice results. I will study this algorithm and try to incorporate it...
I put my code here in case you want to look at exactly what I did: https://github.com/carlosdcastillo/simplify-c-defines
I've been thinking about this too. I made a zig impl: https://github.com/travisstaloch/quine-mccluskey.zig
Any ideas about how to make this useful for this project?
I put my code here in case you want to look at exactly what I did: https://github.com/carlosdcastillo/simplify-c-defines
Oh this is cool. I'm going to try and do the same with my zig impl.
I think i need to work out a few bugs before my zig impl is ready. I've ported simplify.py to zig but it appears i'm not seeing the same reductions as with qm.py. Its likely down to not getting the same results from qm.permutations() which is used to generate the dontcares.
I'll let you guys know when i make some more progress. Let me know if you have any questions or want me to share any code.
I've continued working on this and just wanted to report that I've been able to recreate simplify.py in zig with the same output. While the zig quine-mccluskey is yet quite slow, it seems to be correct.
I ditched the O(2^N) algorithm in 5ff8b51b121997df093373c56f17d7a7aea3abfb and started working on a greedy algorithm instead.