Examples

NPN canonization

The following two examples show NPN canonization on all \(n\) input functions or on a selection of randomly generated functions.

examples/npn_enumeration.cpp

#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

examples/npn_random.cpp

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

examples/isop.cpp

#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