malloc82 / quine-mccluskey-method Goto Github PK
View Code? Open in Web Editor NEWQuine-McCluskey method implemented using Common Lisp
Quine-McCluskey method implemented using Common Lisp
(quine-mccluskey:quine-mccluskey "abcd" '(17 19 21 23 25 27 29 31 49 51 53 55 57 59 61 63 81 83 85 87 89 91 93 95 113
115 117 119 121 123 125 127 145 147 149 151 153 155 157 159 177 179 181 183
185 187 189 191 209 211 213 215 217 219 221 223 241 243 245 247 249 251 253
255))
for example never terminates. It should be well within the realm of this implementation.
For further testing, here the application code I use to compute the logic for n-bit multipliers.
It runs up to nbits = 3 but hangs for nbits = 4 (and the above call is for bit0 in a 4 bit multiplier).
(require :quine-mccluskey)
(defun create-n-bit-multiplier-problem (&optional (nbits 2))
(let ((max-val (- (expt 2 nbits) 1)))
(values
(loop
for a upto max-val
appending
(loop
for b upto max-val
collecting
(list a b (* a b))))
(list :nbit-in nbits :nbit-out (ash nbits 1)))))
(defun create-minterms-for-bit (bit-position
problem
problem-spec)
(when (<= 0
bit-position
(- (getf problem-spec :nbit-out) 1))
(let ((mask (ash 1 bit-position))
(nbit-in (getf problem-spec :nbit-in)))
(let ((one-terms
(remove-if #'(lambda (term)
(destructuring-bind (a b o) term
(declare (ignorable a b))
(= 0 (logand o mask))))
problem)))
(format
t "1-terms (~D): ~A~%"
(length one-terms) one-terms)
(values
(loop
for term in one-terms
collecting
(logior (ash (first term) nbit-in)
(second term))))))))
(defun make-sample-string (nbit-in)
(let ((input-width (ash nbit-in 1)))
(with-output-to-string (stream)
(loop
for i below input-width
do (princ (code-char (+ (char-code #\a) i))
stream)))))
(defun solve-n-bit-multiplier-problem (&optional (nbits 2))
(multiple-value-bind (terms spec)
(create-n-bit-multiplier-problem nbits)
(let ((nbit-out (getf spec :nbit-out))
(sample-str (make-sample-string
(getf spec :nbit-in))))
(loop
for bit below nbit-out
collecting
(list
:bit bit
:result (quine-mccluskey:quine-mccluskey
sample-str
(create-minterms-for-bit
bit
terms
spec)))))))
(defun expected-time-complexity (nbits)
(/ (expt 3 nbits)
(log nbits)))
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.