123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159 |
- #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){
- // output(m,file);
- //return;
- // 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;
- }
- #define STACK_SIZE (MAX_GENUS*(MAX_GENUS+1))/2
- void walk(int m,int k)
- {
- monoid data[STACK_SIZE], *stack[STACK_SIZE], *current,temp,temp2;
- size_t stack_size=0;
- for (ind_t i=0; i<STACK_SIZE; i++) stack[i] = &(data[i]);
- init_ordinary(data[0],m);
- for(int i=0;i<k;++i){
- auto it = generator_iter<CHILDREN>(data[i]);
- it.move_next();
- ind_t pos=0;
- if(i==0){
- it.move_next();
- pos=1;
- }
- remove_generator(data[i+1],data[i],it.get_gen(),pos);
- }
- //Root @ data[k]
- temp=data[k];
- cout<<"Root : ";
- print_monoid_gen(temp);
-
- auto it = generator_iter<CHILDREN>(temp);
- it.move_next();
- ind_t pos=0;
- if(k==0){
- it.move_next();
- ++pos;
- }
- while (it.move_next()){
- remove_generator(*stack[stack_size], temp, it.get_gen(),pos++);
- cout<<"Pop "<<it.get_gen()<<" : ";
- print_monoid_gen(*stack[stack_size]);
- treat(*stack[stack_size]);
- ++stack_size;
- }
- while (stack_size != 0)
- {
- current = stack[--stack_size];
- /*if(current->conductor>=35){
- cout<<"Pop ";
- print_monoid_gen(*current);
- }*/
-
- if(true or not cut(*current))
- {
- if (current->genus < MAX_GENUS - 1)
- {
- auto it = generator_iter<CHILDREN>(*current);
- ind_t pos=0;
- while (it.move_next())
- {
- swap(stack[stack_size],stack[stack_size+1]);
- //Current is tored @ stack_size+1
- remove_generator(*stack[stack_size], *current, it.get_gen(),pos++);
- treat(*stack[stack_size]);
- ++stack_size;
- }
-
- }
- else
- {
- auto it = generator_iter<CHILDREN>(*current);
- ind_t pos=0;
- while (it.move_next())
- {
- remove_generator(temp2, *current, it.get_gen(),pos++);
- temp2.conductor=0;
- treat(temp2);
- }
- }
- }
- }
- }
- 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;
- }
|