treewalk.cpp 2.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <chrono>
  4. #include <cmath>
  5. #include <cpuid.h>
  6. #include <fstream>
  7. #include "treewalk.hpp"
  8. using namespace std;
  9. using namespace std::chrono;
  10. fstream file;
  11. void treat(const monoid& m){
  12. int w=m.e*m.left-m.conductor;
  13. if(w<=0){
  14. if(m.e!=3 and (m.e!=m.min or m.left_primitive!=1)){
  15. output(m,file);
  16. }
  17. }
  18. }
  19. //static const int mcut=ceil(float(3*(MAX_GENUS+2))/5);
  20. bool cut(const monoid& m){
  21. if(3*m.left_primitive>=m.min) return true;
  22. return false;
  23. }
  24. void walk_children(monoid m)
  25. {
  26. monoid data[MAX_GENUS-1], *stack[MAX_GENUS], *current,temp;
  27. monoid **stack_pointer = stack + 1;
  28. for (ind_t i=1; i<MAX_GENUS; i++) stack[i] = &(data[i-1]); // Nathann's trick to avoid copy
  29. stack[0] = &m;
  30. while (stack_pointer != stack)
  31. {
  32. --stack_pointer;
  33. current = *stack_pointer;
  34. if(not cut(*current))
  35. {
  36. if (current->genus < MAX_GENUS - 1)
  37. {
  38. auto it = generator_iter<CHILDREN>(*current);
  39. ind_t pos=0;
  40. while (it.move_next())
  41. {
  42. // exchange top with top+1
  43. stack_pointer[0] = stack_pointer[1];
  44. remove_generator(**stack_pointer, *current, it.get_gen(),pos++);
  45. treat(**stack_pointer);
  46. stack_pointer++;
  47. }
  48. *stack_pointer = current;
  49. }
  50. else
  51. {
  52. auto it = generator_iter<CHILDREN>(*current);
  53. ind_t pos=0;
  54. while (it.move_next())
  55. {
  56. remove_generator(temp, *current, it.get_gen(),pos++);
  57. treat(temp);
  58. }
  59. }
  60. }
  61. }
  62. }
  63. int main(int argc, char **argv)
  64. {
  65. monoid O,S;
  66. string nproc = "0";
  67. if(argc!=3){
  68. cerr<<"Usage : "<<argv[0]<<" [m] [k] with k in [1,m-1]"<<endl;
  69. exit(-1);
  70. }
  71. int m=atoi(argv[1]);
  72. int k=atoi(argv[2]);
  73. if(k<=0 or k>=m){
  74. cerr<<"k must be in [1,m-1]"<<endl;
  75. exit(-2);
  76. }
  77. unsigned int ax, bx, cx, dx;
  78. if (!__get_cpuid(0x00000001, &ax, &bx, &cx, &dx))
  79. {
  80. cerr << "Unable to determine the processor type !" << endl;
  81. return EXIT_FAILURE;
  82. }
  83. if (!(cx & bit_SSSE3))
  84. {
  85. cerr << "This programm require sse3 instructions set !" << endl;
  86. return EXIT_FAILURE;
  87. }
  88. if (!(cx & bit_POPCNT))
  89. {
  90. cerr << "This programm require popcount instruction !" << endl;
  91. return EXIT_FAILURE;
  92. }
  93. cout << "Testing Wilf's conjecture for numerical semigroups of genus <= "
  94. << MAX_GENUS << " which are sons of O_{"<<m<<"}\\{"<<m+k<<"}."<<endl;
  95. auto begin = high_resolution_clock::now();
  96. init_ordinary(O,m);
  97. remove_generator(S,O,m+k,k);
  98. string filename="wilf_"+to_string(m)+"_"+to_string(k);
  99. file.open(filename.c_str(),ios::out|ios::trunc);
  100. walk_children(S);
  101. auto end = high_resolution_clock::now();
  102. duration<double> ticks = end-begin;
  103. cout << " Computation time = " << std::setprecision(4) << ticks.count() << " s." << endl;
  104. file.close();
  105. return EXIT_SUCCESS;
  106. }