AlgorithmReducibleRT.hpp

[詳解]

#ifndef MTTOOLBOX_ALGORITHM_REDUCIBLE_RT_HPP
#define MTTOOLBOX_ALGORITHM_REDUCIBLE_RT_HPP

#include <iostream>
#include <ostream>
#include <iomanip>
#include <vector>
#include <cstdlib>
#include <cerrno>
#include <unistd.h>
#include <time.h>
#include <MTToolBox/ReducibleTemperingCalculatable.hpp>
#include <MTToolBox/AlgorithmReducibleEquidistribution.hpp>
#include <MTToolBox/AlgorithmReducibleRecursionSearch.hpp>
#include <MTToolBox/AlgorithmTempering.hpp>
#include <MTToolBox/AlgorithmCalculateParity.hpp>
#include <MTToolBox/util.hpp>

namespace MTToolBox {
    template<typename U, typename G>
    class AlgorithmReducibleRecursionAndTempering {
    public:
        AlgorithmReducibleRecursionAndTempering(AbstractGenerator<U>& bg) {
            baseGenerator = &bg;
        }

        bool search(G& rg,
                    AlgorithmTempering<U>& st1,
                    AlgorithmTempering<U>& 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>()];
            AlgorithmReducibleRecursionSearch<U> search(rg, *baseGenerator);
            AlgorithmCalculateParity<U, G> cp;
            int mexp = rg.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 << rg.getParamString() << endl;
            }
            poly = search.getIrreducibleFactor();
            parity = cp.searchParity(rg, poly);
            weight = NTL::weight(poly);
            GF2X lcm(0, 1);
            calcCharacteristicPolynomial(&rg, lcm);
            NTL::GF2X quotient = lcm / poly;
            annihilate(&rg, quotient);
            if (verbose) {
                AlgorithmEquidistribution<U> sb(rg, 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(rg, verbose);
                if (verbose) {
                    if (st2.isLSBTempering()) {
                        rg.setReverseOutput();
                    }
                    AlgorithmEquidistribution<U> sc(rg, bit_size<U>());
                    delta = sc.get_all_equidist(veq);
                    rg.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(rg, verbose);
            AlgorithmEquidistribution<U> sc(rg, 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 << rg.getParamString() << endl;
                print_kv(veq, mexp, bit_size<U>());
                *out << "delta = " << dec << delta << endl;
            }
            return true;
        }

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

        int getDelta() {
            return delta;
        }

        const NTL::GF2X& getIrreducibleFactor() {
            return poly;
        }

        U getParity() const {
            return parity;
        }

    private:
        int weight;
        int delta;
        U parity;
        NTL::GF2X poly;
        //NTL::GF2X characteristic;
        std::ostream * out;
        AbstractGenerator<U> * baseGenerator;

        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_Reducible_RT_HPP