123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152 |
- #include <iostream>
- #include <iomanip>
- #include <chrono>
- #include <cmath>
- #include <cpuid.h>
- #include <fstream>
- #include "treewalk.hpp"
- using namespace std;
- using namespace std::chrono;
- fstream file;
- void treat(const monoid& m){
- // int w=m.e*m.left-m.conductor;
- int q=ceil(float(m.conductor)/float(m.min));
- unsigned int rho=q*m.min-m.conductor;
- if(m.wilf<=rho){
- if((m.wilf<0) or (m.wilf<=rho and m.e>2 and m.left_primitive>1 and q>=4)){
- output(m,file);
- }
- }
- }
- //static const int mcut=ceil(float(3*(MAX_GENUS+2))/5);
- bool cut(const monoid& m){
- if(3*m.left_primitive>=m.min) return true;
- return false;
- }
- void walk(int m,int k)
- {
- monoid data[MAX_GENUS-1], *stack[MAX_GENUS], *current,temp;
- monoid **stack_pointer = stack+1;
- for (ind_t i=1; i<MAX_GENUS; i++) stack[i] = &(data[i-1]);
- init_ordinary(data[0],m);
- for(int i=0;i<k;++i){
- auto it = generator_iter<CHILDREN>(data[i]);
- it.move_next();
- // printq_monoid_gen(data[i]);
- ind_t pos=0;
- if(i==0){
- it.move_next();
- pos=1;
- }
- remove_generator(data[i+1],data[i],it.get_gen(),pos);
- }
- temp=data[k];
- stack[0]=&temp;
- cout<<"Root : ";
- print_monoid_gen(temp);
-
- auto it = generator_iter<CHILDREN>(temp);
- it.move_next();
- ind_t pos=1;
- if(k==0){
- it.move_next();
- ++pos;
- }
- while (it.move_next()){
- stack_pointer[0] = stack_pointer[1];
- remove_generator(**stack_pointer, temp, it.get_gen(),pos++);
- cout<<"Pop "<<it.get_gen()<<" : ";
- print_monoid_gen(**stack_pointer);
- treat(**stack_pointer);
- stack_pointer++;
- }
- while (stack_pointer != stack)
- {
- --stack_pointer;
- current = *stack_pointer;
- if(not cut(*current))
- {
- if (current->genus < MAX_GENUS - 1)
- {
- auto it = generator_iter<CHILDREN>(*current);
- ind_t pos=0;
- while (it.move_next())
- {
- // exchange top with top+1
- stack_pointer[0] = stack_pointer[1];
- remove_generator(**stack_pointer, *current, it.get_gen(),pos++);
- treat(**stack_pointer);
- stack_pointer++;
- }
- *stack_pointer = current;
- }
- else
- {
- auto it = generator_iter<CHILDREN>(*current);
- ind_t pos=0;
- while (it.move_next())
- {
- remove_generator(temp, *current, it.get_gen(),pos++);
- treat(temp);
- }
- }
- }
- }
- }
- int main(int argc, char **argv)
- {
- if(argc!=4){
- cerr<<"Usage : "<<argv[0]<<" [m] [k] filename with k in [0,MAX_GENUS-m]"<<endl;
- exit(-1);
- }
- int m=atoi(argv[1]);
- int k=atoi(argv[2]);
- char* filename_base=argv[3];
- if(k<0 or k>=MAX_GENUS-m){
- cerr<<"k must be in [0,MAX_GENUS-m]"<<endl;
- exit(-2);
- }
- unsigned int ax, bx, cx, dx;
- if (!__get_cpuid(0x00000001, &ax, &bx, &cx, &dx))
- {
- cerr << "Unable to determine the processor type !" << endl;
- return EXIT_FAILURE;
- }
- if (!(cx & bit_SSSE3))
- {
- cerr << "This programm require sse3 instructions set !" << endl;
- return EXIT_FAILURE;
- }
- if (!(cx & bit_POPCNT))
- {
- cerr << "This programm require popcount instruction !" << endl;
- return EXIT_FAILURE;
- }
-
- cout << "Testing Wilf's conjecture for numerical semigroups of genus <= "
- << MAX_GENUS << " for m="<<m<<" and k="<<k<<"."<<endl;
- /*cerr << "Testing Wilf's conjecture for numerical semigroups of genus <= "
- << MAX_GENUS << " for m="<<m<<" and k="<<k<<"."<<endl;*/
- auto begin = high_resolution_clock::now();
- string filename=string(filename_base)+"_wilf_"+to_string(m)+"_"+to_string(k);
- file.open(filename.c_str(),ios::out|ios::trunc);
- walk(m,k);
- auto end = high_resolution_clock::now();
- duration<double> ticks = end-begin;
- cout << " Computation time = " << std::setprecision(4) << ticks.count() << " s." << endl;
- file.close();
- return EXIT_SUCCESS;
- }
|