is free software
(released under the GNU
) capable of computing
truth tables for boolean functions
involving hundreds of variables. Computations like these are usually
considered intractable, but many are not-intractable with the algorithm
used in NI (hence the acronym).
What can NI do? Almost anything that involves boolean logic. It can
generate truth tables from functions and functions from truth tables.
It can assume hypothetical conditions, and verify truths under those
conditions. It is possible to use NI to easily validate (or invalidate)
argument forms, reduce the guard conditions of loops, and so on. You
can even use as many variables as you want, since the amount of memory
used does not increase exponentially.
How does NI do this? It makes use of compression, cacheing, recursion,
and short-circuit logic to cut corners and avoid calculations whenever
It is being developed on GNU/Linux, and should be easily portable to other
randomly generated function
involving 40 variables and 1024 operations was given to both NI and a
brute-force C program. Both programs calculated all possible outputs of
that function. Which program was faster?
NI finished in 4.6 seconds.
The brute force C program eventually finished over half an hour later
(exactly 32 minutes and
The truth table of another, simpler function (XORing 256 different variables together) took only 0.006 seconds
to compute. A brute force C program doing the same thing would never finish.
6/3/06 - Status update
The next NI release should be coming soon. Several new features have been added to CVS, including the new dot= command (which prints the code necessary to graph the result using the graphviz program). The simplification code is being overhauled (again) since the expected bugs were found in the new implementation. Also, NI now supports fast reading from STDIN using the --pipe command line option; this is a necessary step as the code is moving toward being externally scriptable through perl and the like, rather than containing its own procedural language or providing an overly complicated shared library.
5/3/06 - Simplification code rewrite
One of NI's newer capabilities is that of simplifying truth tables
relative to a bitmask ($MASK). The old code worked... mostly... but
there were some cases where the result wasn't quite as simple as one
could hope. The newer code (just put into CVS today) should do much
better, though I anticipate a few bugs. The old code is still there,
just in case.
4/17/06 - Status update
The latest focus in NI development is meta-commands. These commands can
be used to describe a truth table (or ALTT) directly, without boolean
functions. This puts forth the possiblity of a translation script of
sorts, which would translate boolean expressions of a specific form
into NI meta-commands (which can be evaluated much faster than
expressions). So far, two meta commands/operators are implemented:
resizing (:) and concatenation (+). For example, 0:40 produces an ALTT
containing 2^40 0's, and (0:40) + (1:40) produces 0:40|1:40, the
equivalent of g40 (the 41st general variable).
4/7/06 - Garbage collection
Garbage collection is now implemented and is in CVS. If you wish to
enable it, configure with the --enable-autogc option. A new command
line option for NI has also been added: --no-cache. Specifying
--no-cache will cause NI to not use the result cache. This will
decrease the amount of memory used at the expense of performance. When
used with an autogc enabled NI, the amoutn of memory used will be even
4/4/06 - Status update
The code is in a large point of flux as I try to implement some form of
garbage collection (Segments are accumulating unnecessarily). The CVS
code works great, but contains none of this garbage collection code
(...that's why it still works...). After the bugs have been worked out,
this new code will be uploaded into CVS.
3/26/06 - First release!
The first release (0.2.3) has been made and is downloadable from the
downloads section! Also, the first attempt at documentation more
complicated than a simple syntax reference is inluded with the source
in the forms of a man page and Texinfo manual (which is also viewable
online in the documentation section).
3/16/06 - Boolean algebra
NI is now capable of generating functions from truth tables (using the f= command). If
you type a huge, complicated expression and want to see if NI can think
of a simpler one, try typing f=
and see what NI comes up with. Also, a simplify
command has been added which does NOT simplify equations, it simplifies
ALTTs based on the current assumptions ($MASK). In
effect, after typing some assumptions, an equation, simplify,
and f=, you will get an equation which is a simpler version of your
original equation, and logically equivalent under the given
assumptions. A demonstration of the new boolean algebra capabilities
will be uploaded soon.
3/13/06 - Documentation added
The first documentation has been added! It's just a simple syntax quick
reference and doesn't go over anything in great detail, however more
documentation is in the works that will go over the
basics (a tutorial of sorts).
3/5/06 - Status update
A major bug was found and fixed. Apparently, while making changes to
the code to support threading, etc., a line which was supposed to
return true somehow got rewritten to return false, which caused the XOR
routine to produce faulty results in a special case. Apart from that,
two new commands have been added: suppose and reset, and one new
operator has been added: !=. These (and all of the others) will be
documented in the upcoming syntax reference (which I intend to finish
before this week's end).
3/4/06 - Status update
The documentation is nearing completion. As far as the program itself
goes, an actual source release
should occur as soon as macros (and maybe threads) are implemented.
Just today, I tried to throw a worker-pool thread model together, but
the overhead of adding a job to the pool queue canceled out the speed
gained through true multitasking. Even though that attempt didn't work,
something else is bound to - threads will eventually find their way
into NI as a performance gain somehow.
3/3/06 - "Optimization"
The fastest operation in NI has always been calculating an inverse,
because it involves no calculation; all inverses in NI are
precalculated quickly and immediately upon data creation, thus avoiding
having to calculate them recursively later. I tried to apply this same
principle to certain NAND operations involving general variables, but
the act of precalculating these is actually slower,
so while this optimization attempt is in the code, it is also disabled.
If you want the program to run slower, you can uncomment the #define
line in altt.h and compile, otherwise leave that line as it is and NI
will run just as fast as it did before the change (which may be
completely removed later).
In other news, significant planning has gone into documentation and the
first useful documentation should be available soon, along with the
first actual code release.
3/2/06 - Status update
There have been a few notable changes, the most significant of which
are the addition of an "undef" command (which deletes or UNDEFines
variables) and the beginnings of general-variable NAND precalculation
code which should speed things up even more.
2/25/06 - Added integrated mask
Previously, to apply a restrictive bitmask, you had to create a
variable to store the mask and apply it manually wherever possible. NI
will now do most of the work for you if you use the $MASK
internal variable. After setting $MASK
to any value, the operation &
is automatically performed on all variables, values, and results of
Unfortunately, there is still no way to delete variables and
therefore no way to remove the automatic mask (doing something like 1
=> $MASK actually performs 1
& $MASK => $MASK which has no effect). This
feature should be coded in soon.
2/24/06 - Status update
A few changes have been made in the past few days. Some documentation
has actually been written (a basic syntax reference), but - at least
for now - this documentation is only downloadable with the code through
CVS. (It will be in the not-intractable/docs directory after CVS
checkout.) Apart from the new documentation, a bug has been fixed that
caused an error during parsing when a line contained trailing
whitespace, and work is underway to improve overall performance
(including adding thread support).
2/19/06 - Project accepted
The project has been approved and is now being hosted at Savannah
current source code has been uploaded to CVS, a general
has been created, and a logo for NI (consisting a brush-stroke-like
letter "N" sort of
liquefying and forming the second letter "I") has been rather
serendipitously created with inkscape.
current stable release of NI is version 0.2.3, released 3/26/06, and
the source code can be downloaded here
. It has been tested under GNU/Linux and FreeBSD, and it should compile fine under other Unices.
For you windows-only users, I have cross-compiled a windows version which can be downloaded from here
. Just unzip it and run ni.exe
in a terminal (console) window. Keep in mind, however, that the windows
binary is here for completeness sake. Although compiled from the exact
same source, it does not run as fast as the GNU/Linux version. If you
are interested in solving serious problems or doing serious benchmarks
with NI, please use the GNU/Linux version.
NI is under active development. If you wish, you can also download the
current bleeding-edge source code through anonymous CVS like so:
- The current manual (same manual which comes with
the 0.2.3 source): (HTML)
- The old syntax quick-reference (OUT OF DATE): (text
(C) Michael Jumper 2006
Last updated 6/3/06
Send comments to mikejumper AT astound DOT net