Examples¶
NPN canonization¶
The following two examples show NPN canonization on all \(n\) input functions or on a selection of randomly generated functions.
#include <cstdint>
#include <iostream>
#include <unordered_set>
#include <kitty/kitty.hpp>
/* compile time constant for the number of variables */
auto constexpr num_vars = 4;
int main()
{
/* truth table type in this example */
using truth_table = kitty::static_truth_table<num_vars>;
/* set to store all NPN representatives */
std::unordered_set<truth_table, kitty::hash<truth_table>> classes;
/* initialize truth table (constant 0) */
truth_table tt;
do
{
/* apply NPN canonization and add resulting representative to set */
const auto res = kitty::exact_npn_canonization( tt );
classes.insert( std::get<0>( res ) );
/* increment truth table */
kitty::next_inplace( tt );
} while ( !kitty::is_const0( tt ) );
std::cout << "[i] enumerated "
<< ( 1 << ( 1 << tt.num_vars() ) ) << " functions into "
<< classes.size() << " classes." << std::endl;
return 0;
}
Output:
$ time ./examples/npn_enumeration
[i] enumerated 65536 functions into 222 classes.
./examples/npn_enumeration 0.15s user 0.00s system 97% cpu 0.159 total
#include <cstdint>
#include <iostream>
#include <unordered_set>
#include <kitty/kitty.hpp>
/* compile time constant for the number of variables */
auto constexpr num_vars = 6;
/* number of random functions to generate */
auto constexpr num_functions = 10000;
int main()
{
/* truth table type in this example */
using truth_table = kitty::static_truth_table<num_vars>;
/* set to store all NPN representatives */
std::unordered_set<truth_table, kitty::hash<truth_table>> classes;
/* initialize truth table (constant 0) */
kitty::static_truth_table<num_vars> tt;
for ( auto i = 0; i < num_functions; ++i )
{
/* create a random truth table */
kitty::create_random( tt );
/* apply NPN canonization and add resulting representative to set */
const auto res = kitty::exact_npn_canonization( tt );
classes.insert( std::get<0>( res ) );
}
std::cout << "[i] partitioned "
<< num_functions << " random functions into "
<< classes.size() << " classes." << std::endl;
return 0;
}
Output:
$ time ./examples/npn_random
[i] partitioned 10000 random functions into 10000 classes.
./examples/npn_random 2.20s user 0.01s system 99% cpu 2.232 total
ISOP computation¶
The following example reads a truth table from a binary string, computes its ISOP, and prints it.
#include <iostream>
#include <kitty/kitty.hpp>
int main( int argc, char ** argv )
{
/* we initialize TT using a lambda, since we do not know its size yet */
const auto tt = [&]() {
if ( argc == 1 ) /* no command line argument -> chose random */
{
kitty::dynamic_truth_table tt( 10 );
kitty::create_random( tt );
return tt;
}
else /* command line argument is binary string */
{
std::string spec( argv[1] );
auto size = spec.size();
auto num_vars = 0;
/* compute number of variables */
while ( size >>= 1 )
++num_vars;
kitty::dynamic_truth_table tt( num_vars );
kitty::create_from_binary_string( tt, spec );
return tt;
}
}();
/* compute ISOP */
const auto cubes = kitty::isop( tt );
/* print ISOP */
for ( auto cube : cubes )
{
cube.print( tt.num_vars() );
std::cout << std::endl;
}
return 0;
}
Output:
$ time ./examples/isop 11101000
-11
1-1
11-
./examples/isop 11101000 0.00s user 0.00s system 50% cpu 0.005 total