// ///////////////////////////////// // mikbitsetA1.c++ // // A132581 terms. // (this program is Different from the one // that calculates terms of the A132582 series) // Read the comments at the end. // MIT Licensed source code. // // J.M. Aranda. Madrid. 2021. ///////////////////////////// #include <cstdio> #include <cstdlib> #include <iostream> #include <iomanip> #include <bitset> #include <array> #include <unordered_map> #include <boost/multiprecision/cpp_int.hpp> using namespace std; ///////////////////////////////////////////// #pragma pack(16) #define WIDE 256 using typeposet=bitset<WIDE>; using typesize=boost::multiprecision::uint128_t; static std::unordered_map<typeposet,typesize> MAP; static array<typeposet,WIDE> powers; //////////////////////////////////// // // poset: poset expressed as bitset. // result: size of the poset. static typesize POSETSIZE(const typeposet poset) { if(poset.none())return +1; // (0,+1) if(poset.count()==1)return +2; // (1,+2) // If value known take from map. auto ite=MAP.find(poset); if(ite!=MAP.end())return ite->second; ///////////////////////////////////// // Determine log2(poset) int posethb=-1;typeposet tmp=poset; while(tmp.any()){posethb++;tmp>>=1;} // // Split on left and right posets. typeposet left=poset; // left Poset P-{x} left&=~powers[posethb]; typesize Fleft=POSETSIZE(left); // typeposet right=poset; // right Poset P-cone(x) for(int i=0;i<=posethb;i++) { if((i&posethb)==i)right&=~powers[i]; } typesize Fright=POSETSIZE(right); typesize SUM=Fleft+Fright; MAP.emplace(poset,SUM); return SUM; } // int main (void) { // Init MAP. MAP.clear();MAP.emplace(0,1);MAP.emplace(1,2); // // fill powers array ************************ for(int i=0;i<WIDE;i++) { typeposet tmp;tmp.reset();tmp.set(0);tmp<<=i; powers[i]=tmp; } // main loop typeposet REPUNIT;REPUNIT.reset(); for(int n=0;n<WIDE;n++) { typeposet poset=REPUNIT; typesize An=POSETSIZE(poset); cout<<setw(4)<<n; cout<<right<<setw(18)<< An<<endl; // next must be here REPUNIT<<=1;REPUNIT|=1; } // cout<<"mapsz: "<<MAP.size()<<endl; MAP.clear(); return +1; } // // This is my version of the Algorithm Splitting Result // of P.Koehler and J.Berman, // from "Cardinalities of finite distributive lattices". // With whose program I compare it. // The copyrighted BigInt class is limited to 256 terms, // does not support hash functions, // is based on 16-bit arithmetic, // and cannot be used as a "const" parameter. // It is replaced by // - a std::bitset to encode the poset. // - an std::cpp_int for its size. // the bitset class improves the readability of the code, // and is implemented by _builtin functions. // It allows to use a hashmap, a std::unordered_map, // pre-scalable, smaller and more efficient. // Only 32GB in term 160. // The cpp_int class also takes up less memory than BigInt. /////////////////////////////////////////////////////////// // //