NI is free software (released under the GNU GPL) 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 possible.

It is being developed on GNU/Linux, and should be easily portable to other platforms.

Benchmarks:

A large, 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?

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.

back to top

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.

back to top

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.

back to top

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).

back to top

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 further decreased.

back to top

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.

back to top

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).

back to top

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.

back to top

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).

back to top

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).

back to top

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.

back to top

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 PRECALC 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.

back to top

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.

back to top

2/25/06 - Added integrated mask support
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 & $MASK is automatically performed on all variables, values, and results of operations.  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.

back to top

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).

back to top

2/19/06 - Project accepted
The project has been approved and is now being hosted at Savannah. The current source code has been uploaded to CVS, a general homepage 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.

back to top

The 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:

cvs -z3 -d:pserver:anonymous@cvs.savannah.nongnu.org:/sources/not-intractable co not-intractable

back to top

• The current manual (same manual which comes with the 0.2.3 source): (HTML) (PDF)
• The old syntax quick-reference (OUT OF DATE): (text format)

back to top