AlgorithmRecursionAndTempering.hpp

Go to the documentation of this file.

#ifndef MTTOOLBOX_ALGORITHM_RECURSION_AND_TEMPERING_HPP
#define MTTOOLBOX_ALGORITHM_RECURSION_AND_TEMPERING_HPP

#include <iostream>
#include <ostream>
#include <iomanip>
#include <vector>
#include <cstdlib>
#include <cerrno>
#include <unistd.h>
#include <time.h>
#include <MTToolBox/TemperingCalculatable.hpp>
#include <MTToolBox/AlgorithmEquidistribution.hpp>
#include <MTToolBox/AlgorithmRecursionSearch.hpp>
#include <MTToolBox/AlgorithmTempering.hpp>
#include <MTToolBox/util.hpp>

namespace MTToolBox {
    template<typename U, typename V = U>
    class AlgorithmRecursionAndTempering {
    public:
        AlgorithmRecursionAndTempering(AbstractGenerator<V>& bg,
            const AlgorithmPrimitivity& primitivity = MersennePrimitivity) {
            baseGenerator = &bg;
            isPrime = &primitivity;
        }
        bool search(TemperingCalculatable<U, V>& lg,
                    AlgorithmTempering<U, V>& st1,
                    AlgorithmTempering<U, V>& st2,
                    bool verbose = false,
                    std::ostream& os = std::cout,
                    bool no_lsb = false) {
            using namespace NTL;
            using namespace std;

            out = &os;
            int veq[bit_size<U>()];
            AlgorithmRecursionSearch<U, V> search(lg, *baseGenerator, *isPrime);
            int mexp = lg.bitSize();
            bool found = false;
            for (int i = 0;; i++) {
                if (search.start(1000 * mexp)) {
                    found = true;
                    break;
                }
                if (verbose) {
                    *out << "not found in " << (i + 1) * 10000 << endl;
                }
            }
            if (!found) {
                return false;
            }
            if (verbose) {
                time_t t = time(NULL);
                *out << "irreducible parameter is found at " << ctime(&t);
            }
            if (verbose) {
                *out << "count = " << search.getCount() << endl;
                *out << lg.getParamString() << endl;
            }
            poly = search.getMinPoly();
            weight = NTL::weight(poly);
            if (verbose) {
                AlgorithmEquidistribution<U, V> sb(lg, bit_size<U>());
                int delta = sb.get_all_equidist(veq);
                print_kv(veq, mexp, bit_size<U>());
                *out << "delta = " << dec << delta << endl;
            }
            if (! no_lsb) {
                st2(lg, verbose);
                if (verbose) {
                    if (st2.isLSBTempering()) {
                        lg.setReverseOutput();
                    }
                    AlgorithmEquidistribution<U, V> sc(lg, bit_size<U>());
                    delta = sc.get_all_equidist(veq);
                    lg.resetReverseOutput();
                    time_t t = time(NULL);
                    *out << "lsb tempering parameters are found at "
                         << ctime(&t) << endl;
                    print_kv(veq, mexp, bit_size<U>());
                    *out << "lsb delta = " << dec << delta << endl;
                }
            }
            st1(lg, verbose);
            AlgorithmEquidistribution<U, V> sc(lg, bit_size<U>());
            delta = sc.get_all_equidist(veq);
            if (verbose) {
                time_t t = time(NULL);
                *out << "tempering parameters are found at " << ctime(&t)
                     << endl;
                *out << lg.getParamString() << endl;
                print_kv(veq, mexp, bit_size<U>());
                *out << "delta = " << dec << delta << endl;
            }
            return true;
        }

        bool search(TemperingCalculatable<U, V>& lg,
                    AlgorithmTempering<U, V>& st,
                    bool verbose = false,
                    std::ostream& os = std::cout) {
            return search(lg, st, st, verbose, os, true);
        }

        int getWeight() {
            return weight;
        }

        int getDelta() {
            return delta;
        }

        const NTL::GF2X& getCharacteristicPolynomial() {
            return poly;
        }
    private:
        int weight;
        int delta;
        NTL::GF2X poly;
        std::ostream * out;
        AbstractGenerator<V> * baseGenerator;
        const AlgorithmPrimitivity *isPrime;
        void print_kv(int veq[], int mexp, int size) {
            using namespace std;
            for (int i = 0; i < size; i++) {
                *out << dec << i + 1 << ":" << veq[i]
                     << "(" << mexp / (i + 1) - veq[i] << ")"
                     << endl;
            }
        }
    };

}
#endif //MTTOOLBOX_ALGORITHM_RECURSION_AND_TEMPERING_HPP