// ///////////////////////////////// // mikbitset.c++ // // Direct computing of A132582 terms. // Approximately 100 lines of C++. // Read the comments at the end. // MIT Licensed source code. // // J.M. Aranda. Madrid. 2021. ///////////////////////////// // #define WIDE 160 ////////////////// #include <cstdlib> #include <cstdio> #include <iostream> #include <iomanip> #include <cstdint> #include <cstdbool> #include <cassert> #include <bitset> #include <array> #include <unordered_map> #include <boost/multiprecision/cpp_int.hpp> using namespace std; using typeposet=bitset<WIDE>; using typesize=boost::multiprecision::uint128_t; static 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 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. #define MAPDIM 352011011 MAP.clear();MAP.reserve(MAPDIM); 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++) { REPUNIT<<=1;REPUNIT|=1; typeposet poset=REPUNIT; //////////////////////////// //// right poset P-cone(x) int highbit=-1; for(int bit=0;bit<WIDE;bit++) if(poset[bit]==1)highbit=bit; for(int i=0;i<=highbit;i++) { if((i&highbit)==i)poset&=~powers[i]; } ///////////////////////////////////////// typesize An=POSETSIZE(poset); cout<<left<<setw(4)<<n; cout<<left<<setw(18)<<An<<endl; } // cout<<"mapsz: "<<MAP.size()<<endl; MAP.clear(); return +1; } // /*********************************** This is my version of the "Splitting result", from "Cardinalities of finite distributive lattices", by P.Koehler and J.Berman. Their program is on page A132581, and with which I compare it. The copyrighted BigInt class does not support hash functions, it is based on 16-bit arithmetic, and it cannot be used as a "const" parameter. It is replaced by - a std::bitset to encode the poset. - a boost::cpp_int for its size. bitset class improves the readability of C++ code, and it is implemented by _builtin functions. Allows a hashmap, a std::unordered_map, of fixed size, smaller and more efficient. (Only 32GB at term 160). The cpp_int class also occupies less memory than BigInt. *******************************************************/