From Newsgroup: comp.lang.c++

Bonita Montero <Bonita.Montero@gmail.com> writes:

Am 25.02.2024 um 09:48 schrieb Tim Rentsch:

Bonita Montero <Bonita.Montero@gmail.com> writes:

Am 23.02.2024 um 14:51 schrieb Tim Rentsch:

Bonita Montero <Bonita.Montero@gmail.com> writes:

Am 16.02.2024 um 17:06 schrieb Tim Rentsch:

[...]

Also how long does the program take to determine all
primes up to 3 trillion? Here again I am interested
in the single-thread version.

C:\Users\Boni\Documents\Source\bitmapSieve>timep
"x64\Release-clang++\bitmapSieve.exe" 3000000000 "" 1
real 1.234s
user 1.203s
sys 0.031s
cylces 5.523.677.002

What I asked for was 3 trillion with a T, not 3 billion with
a B. Not 3000000000 but 3000000000000.

That would in a bitmap of 375GiB, which won't fit into my memory.

Sounds like you're using 1 bit per number, most of which are
wasted. If you use a different encoding the memory requirements
can be much smaller. How much memory do you have on the box?
If you have 64G you should be able to determine all primes
less than 1.5 trillion, using a simple encoding.

I've mentioned this encoding before but let me give it again.
If numbers are considered mod 30, there are only 8 residues
that are not divisible by 2, 3, or 5. The 8 residues are
1, 7, 11, 13, 17, 19, 23, and 29. So a single byte can
hold all the information needed for 30 numbers, which means

1500000000000 / 30 = 50000000000

which is to say 50 gigabytes should suffice.
--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.c++

Am 11.03.2024 um 18:10 schrieb Tim Rentsch:

Sounds like you're using 1 bit per number, most of which are
wasted. If you use a different encoding the memory requirements
can be much smaller. How much memory do you have on the box?
If you have 64G you should be able to determine all primes
less than 1.5 trillion, using a simple encoding.

I'm omitting even numbers and I handle the number two as a
special case; that's the fastest solution.

I've mentioned this encoding before but let me give it again.
If numbers are considered mod 30, there are only 8 residues
that are not divisible by 2, 3, or 5. The 8 residues are
1, 7, 11, 13, 17, 19, 23, and 29. So a single byte can
hold all the information needed for 30 numbers, which means

1500000000000 / 30 = 50000000000

which is to say 50 gigabytes should suffice.

Show me the code.

--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.c++

On Tue, 2024-03-12 at 10:15 +0100, Bonita Montero wrote:

Am 11.03.2024 um 18:10 schrieb Tim Rentsch:

Sounds like you're using 1 bit per number, most of which are
wasted.  If you use a different encoding the memory requirements
can be much smaller.  How much memory do you have on the box?
If you have 64G you should be able to determine all primes
less than 1.5 trillion, using a simple encoding.

I'm omitting even numbers and I handle the number two as a
special case; that's the fastest solution.

I've mentioned this encoding before but let me give it again.
If numbers are considered mod 30, there are only 8 residues
that are not divisible by 2, 3, or 5.  The 8 residues are
1, 7, 11, 13, 17, 19, 23, and 29.  So a single byte can
hold all the information needed for 30 numbers, which means

    1500000000000 / 30 = 50000000000

which is to say 50 gigabytes should suffice.

Show me the code.

Every 30 natural numbers (or more) can be coded in one byte(8 bits): //----------------------------------------
#include <Wy.stdlib.h>
#include <CSCall/VLInt.h>
// [Syn] PrimeTab is a table for prime numbers
//
class PrimeTab {
public:
typedef uint64_t NumType;
private:
WY_ENSURE(sizeof(NumType)<=sizeof(size_t));
Wy::VLInt m_ptab;
NumType m_maxn;
// [Syn] Get the bit position storing info. for n
// 0= pos for n (n is composite) is not available
//
static size_t bpos(NumType n) {
constexpr NumType Lcm=2*3*5;
const NumType grp= 8*(n/Lcm);
switch(n%30) {
case 1: return grp;
case 7: return grp+1;
case 11: return grp+2;
case 13: return grp+3;
case 17: return grp+4;
case 19: return grp+5;
case 23: return grp+6;
case 29: return grp+7;
default: return 0;
}
};
public:
WY_DECL_REPLY;
PrimeTab() : m_ptab(), m_maxn(0) {};
PrimeTab(const PrimeTab& s) : m_ptab(s.m_ptab), m_maxn(s.m_maxn) {};
PrimeTab(PrimeTab& s, Wy::ByMove_t) : m_ptab(s.m_ptab,Wy::ByMove),
m_maxn(s.m_maxn) {};
explicit PrimeTab(NumType maxn) : m_ptab(), m_maxn(maxn) {
for(NumType n=2; n<=m_maxn; ++n) {
size_t p= bpos(n);
if(p==0) {
continue; // composite number
}
if(m_ptab.bit(p)) {
continue; // composite number
}
for(NumType m=n+n; m<=m_maxn; m+=n) {
Wy::Errno r=m_ptab.set_bit(bpos(m),true);
if(r!=Wy::Ok) {
WY_THROW( Reply(r) );
}
}
};
};
NumType max_num() const { return m_maxn; };
bool is_prime(NumType n) const {
if(n>m_maxn) {
WY_THROW( Reply(EINVAL) );
}
if(n<=6) {
switch(n) {
case 1: // FALLTHROUGH
case 2: // FALLTHROUGH
case 3: // FALLTHROUGH
case 5: return true;
default: return false;
}
}
size_t p= bpos(n);
if(p==0) {
return false;
}
return !m_ptab.bit(p);
};
void swap(PrimeTab& ano) {
m_ptab.swap(ano.m_ptab);
Wy::swap(m_maxn, ano.m_maxn);
};
void reset() {
m_ptab.reset();
};
Wy::Errno reset(NumType maxn) try {
PrimeTab tmp(maxn);
this->swap(tmp);
return Wy::Ok;
}
catch(const Wy::Errno& e) {
WY_RETURN(e);
};
Wy::Errno reset(const PrimeTab& rhs) {
WY_RETURN(m_ptab.reset(rhs.m_ptab));
};
PrimeTab& operator=(const PrimeTab& rhs) {
Wy::Errno r=m_ptab.reset(rhs.m_ptab);
if(r!=Wy::Ok) {
WY_THROW( Reply(r) );
}
return *this;
};
};
--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.c++

Am 14.03.2024 um 05:44 schrieb wij:

On Tue, 2024-03-12 at 10:15 +0100, Bonita Montero wrote:

Am 11.03.2024 um 18:10 schrieb Tim Rentsch:

Sounds like you're using 1 bit per number, most of which are
wasted.  If you use a different encoding the memory requirements
can be much smaller.  How much memory do you have on the box?
If you have 64G you should be able to determine all primes
less than 1.5 trillion, using a simple encoding.

I'm omitting even numbers and I handle the number two as a
special case; that's the fastest solution.

I've mentioned this encoding before but let me give it again.
If numbers are considered mod 30, there are only 8 residues
that are not divisible by 2, 3, or 5.  The 8 residues are
1, 7, 11, 13, 17, 19, 23, and 29.  So a single byte can
hold all the information needed for 30 numbers, which means

    1500000000000 / 30 = 50000000000

which is to say 50 gigabytes should suffice.

Show me the code.

Every 30 natural numbers (or more) can be coded in one byte(8 bits):

Show me a working sieve with that that beats my code.

//----------------------------------------
#include <Wy.stdlib.h>
#include <CSCall/VLInt.h>

// [Syn] PrimeTab is a table for prime numbers
//
class PrimeTab {
public:
typedef uint64_t NumType;

private:
WY_ENSURE(sizeof(NumType)<=sizeof(size_t));
Wy::VLInt m_ptab;
NumType m_maxn;

// [Syn] Get the bit position storing info. for n
// 0= pos for n (n is composite) is not available
//
static size_t bpos(NumType n) {
constexpr NumType Lcm=2*3*5;
const NumType grp= 8*(n/Lcm);
switch(n%30) {
case 1: return grp;
case 7: return grp+1;
case 11: return grp+2;
case 13: return grp+3;
case 17: return grp+4;
case 19: return grp+5;
case 23: return grp+6;
case 29: return grp+7;
default: return 0;
}
};

public:
WY_DECL_REPLY;
PrimeTab() : m_ptab(), m_maxn(0) {};
PrimeTab(const PrimeTab& s) : m_ptab(s.m_ptab), m_maxn(s.m_maxn) {};
PrimeTab(PrimeTab& s, Wy::ByMove_t) : m_ptab(s.m_ptab,Wy::ByMove),
m_maxn(s.m_maxn) {};
explicit PrimeTab(NumType maxn) : m_ptab(), m_maxn(maxn) {
for(NumType n=2; n<=m_maxn; ++n) {
size_t p= bpos(n);
if(p==0) {
continue; // composite number
}
if(m_ptab.bit(p)) {
continue; // composite number
}

for(NumType m=n+n; m<=m_maxn; m+=n) {
Wy::Errno r=m_ptab.set_bit(bpos(m),true);
if(r!=Wy::Ok) {
WY_THROW( Reply(r) );
}
}
};
};
NumType max_num() const { return m_maxn; };
bool is_prime(NumType n) const {
if(n>m_maxn) {
WY_THROW( Reply(EINVAL) );
}
if(n<=6) {
switch(n) {
case 1: // FALLTHROUGH
case 2: // FALLTHROUGH
case 3: // FALLTHROUGH
case 5: return true;
default: return false;
}
}
size_t p= bpos(n);
if(p==0) {
return false;
}
return !m_ptab.bit(p);
};
void swap(PrimeTab& ano) {
m_ptab.swap(ano.m_ptab);
Wy::swap(m_maxn, ano.m_maxn);
};
void reset() {
m_ptab.reset();
};

Wy::Errno reset(NumType maxn) try {
PrimeTab tmp(maxn);
this->swap(tmp);
return Wy::Ok;
}
catch(const Wy::Errno& e) {
WY_RETURN(e);
};
Wy::Errno reset(const PrimeTab& rhs) {
WY_RETURN(m_ptab.reset(rhs.m_ptab));
};
PrimeTab& operator=(const PrimeTab& rhs) {
Wy::Errno r=m_ptab.reset(rhs.m_ptab);
if(r!=Wy::Ok) {
WY_THROW( Reply(r) );
}
return *this;
};
};

--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.c++

On Thu, 2024-03-14 at 07:25 +0100, Bonita Montero wrote:

Am 14.03.2024 um 05:44 schrieb wij:

On Tue, 2024-03-12 at 10:15 +0100, Bonita Montero wrote:

Am 11.03.2024 um 18:10 schrieb Tim Rentsch:

Sounds like you're using 1 bit per number, most of which are
wasted.  If you use a different encoding the memory requirements
can be much smaller.  How much memory do you have on the box?
If you have 64G you should be able to determine all primes
less than 1.5 trillion, using a simple encoding.

I'm omitting even numbers and I handle the number two as a
special case; that's the fastest solution.

I've mentioned this encoding before but let me give it again.
If numbers are considered mod 30, there are only 8 residues
that are not divisible by 2, 3, or 5.  The 8 residues are
1, 7, 11, 13, 17, 19, 23, and 29.  So a single byte can
hold all the information needed for 30 numbers, which means

     1500000000000 / 30 = 50000000000

which is to say 50 gigabytes should suffice.

Show me the code.

Every 30 natural numbers (or more) can be coded in one byte(8 bits):

Show me a working sieve with that that beats my code.

I am not "Tim Rentsch". I did not intend to beat your code but try to make things (what I saw) clear, and thought you might be confused. In general, 
I cannot fully understand your code. Last time I copied your code, it did 
not compile on my Linux machine.

//----------------------------------------
#include <Wy.stdlib.h>
#include <CSCall/VLInt.h>

// [Syn] PrimeTab is a table for prime numbers
//
class PrimeTab {
   public:
     typedef uint64_t NumType;

   private:
     WY_ENSURE(sizeof(NumType)<=sizeof(size_t));
     Wy::VLInt m_ptab;
     NumType m_maxn;

     // [Syn] Get the bit position storing info. for n
     //       0= pos for n (n is composite) is not available      //
     static size_t bpos(NumType n) {
       constexpr NumType Lcm=2*3*5;
       const NumType grp= 8*(n/Lcm);
       switch(n%30) {
         case  1: return grp;
         case  7: return grp+1;
         case 11: return grp+2;
         case 13: return grp+3;
         case 17: return grp+4;
         case 19: return grp+5;
         case 23: return grp+6;
         case 29: return grp+7;
         default: return 0;
       }
     };

   public:
     WY_DECL_REPLY;
     PrimeTab() : m_ptab(), m_maxn(0) {};
     PrimeTab(const PrimeTab& s) : m_ptab(s.m_ptab), m_maxn(s.m_maxn) {};
     PrimeTab(PrimeTab& s, Wy::ByMove_t) : m_ptab(s.m_ptab,Wy::ByMove),        m_maxn(s.m_maxn) {};
     explicit PrimeTab(NumType maxn) : m_ptab(), m_maxn(maxn) {        for(NumType n=2; n<=m_maxn; ++n) {
         size_t p= bpos(n);
         if(p==0) {
           continue;   // composite number
         }
         if(m_ptab.bit(p)) {
           continue;   // composite number
         }

         for(NumType m=n+n; m<=m_maxn; m+=n) {
           Wy::Errno r=m_ptab.set_bit(bpos(m),true);            if(r!=Wy::Ok) {
             WY_THROW( Reply(r) );
           }
         }
       };
     };
     NumType max_num() const { return m_maxn; };
     bool is_prime(NumType n) const {
       if(n>m_maxn) {
         WY_THROW( Reply(EINVAL) );
       }
       if(n<=6) {
         switch(n) {
           case 1: // FALLTHROUGH
           case 2: // FALLTHROUGH
           case 3: // FALLTHROUGH
           case 5: return true;
           default: return false;
         }
       }
       size_t p= bpos(n);
       if(p==0) {
         return false;
       }
       return !m_ptab.bit(p);
     };
     void swap(PrimeTab& ano) {
       m_ptab.swap(ano.m_ptab);
       Wy::swap(m_maxn, ano.m_maxn);
     };
     void reset() {
       m_ptab.reset();
     };

     Wy::Errno reset(NumType maxn) try {
       PrimeTab tmp(maxn);
       this->swap(tmp);
       return Wy::Ok;
     }
     catch(const Wy::Errno& e) {
       WY_RETURN(e);
     };
     Wy::Errno reset(const PrimeTab& rhs) {
       WY_RETURN(m_ptab.reset(rhs.m_ptab));
     };
     PrimeTab& operator=(const PrimeTab& rhs) {
       Wy::Errno r=m_ptab.reset(rhs.m_ptab);
       if(r!=Wy::Ok) {
         WY_THROW( Reply(r) );
       }
       return *this;
     };
};

--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.c++

On Thu, 2024-03-14 at 17:20 +0800, wij wrote:

On Thu, 2024-03-14 at 07:25 +0100, Bonita Montero wrote:

Am 14.03.2024 um 05:44 schrieb wij:

On Tue, 2024-03-12 at 10:15 +0100, Bonita Montero wrote:

Am 11.03.2024 um 18:10 schrieb Tim Rentsch:

Sounds like you're using 1 bit per number, most of which are wasted.  If you use a different encoding the memory requirements
can be much smaller.  How much memory do you have on the box?
If you have 64G you should be able to determine all primes
less than 1.5 trillion, using a simple encoding.

I'm omitting even numbers and I handle the number two as a
special case; that's the fastest solution.

I've mentioned this encoding before but let me give it again.
If numbers are considered mod 30, there are only 8 residues
that are not divisible by 2, 3, or 5.  The 8 residues are
1, 7, 11, 13, 17, 19, 23, and 29.  So a single byte can
hold all the information needed for 30 numbers, which means

     1500000000000 / 30 = 50000000000

which is to say 50 gigabytes should suffice.

Show me the code.

Every 30 natural numbers (or more) can be coded in one byte(8 bits):

Show me a working sieve with that that beats my code.

I am not "Tim Rentsch". I did not intend to beat your code but try to make things (what I saw) clear, and thought you might be confused. In general, 
I cannot fully understand your code. Last time I copied your code, it did  not compile on my Linux machine.

//----------------------------------------
#include <Wy.stdlib.h>
#include <CSCall/VLInt.h>

// [Syn] PrimeTab is a table for prime numbers
//
class PrimeTab {
   public:
     typedef uint64_t NumType;

   private:
     WY_ENSURE(sizeof(NumType)<=sizeof(size_t));
     Wy::VLInt m_ptab;
     NumType m_maxn;

     // [Syn] Get the bit position storing info. for n
     //       0= pos for n (n is composite) is not available      //
     static size_t bpos(NumType n) {
       constexpr NumType Lcm=2*3*5;
       const NumType grp= 8*(n/Lcm);
       switch(n%30) {
         case  1: return grp;
         case  7: return grp+1;
         case 11: return grp+2;
         case 13: return grp+3;
         case 17: return grp+4;
         case 19: return grp+5;
         case 23: return grp+6;
         case 29: return grp+7;
         default: return 0;
       }
     };

   public:
     WY_DECL_REPLY;
     PrimeTab() : m_ptab(), m_maxn(0) {};
     PrimeTab(const PrimeTab& s) : m_ptab(s.m_ptab), m_maxn(s.m_maxn) {};
     PrimeTab(PrimeTab& s, Wy::ByMove_t) : m_ptab(s.m_ptab,Wy::ByMove),
       m_maxn(s.m_maxn) {};
     explicit PrimeTab(NumType maxn) : m_ptab(), m_maxn(maxn) {        for(NumType n=2; n<=m_maxn; ++n) {
         size_t p= bpos(n);
         if(p==0) {
           continue;   // composite number
         }
         if(m_ptab.bit(p)) {
           continue;   // composite number
         }

         for(NumType m=n+n; m<=m_maxn; m+=n) {            Wy::Errno r=m_ptab.set_bit(bpos(m),true);            if(r!=Wy::Ok) {
             WY_THROW( Reply(r) );
           }
         }
       };
     };
     NumType max_num() const { return m_maxn; };
     bool is_prime(NumType n) const {
       if(n>m_maxn) {
         WY_THROW( Reply(EINVAL) );
       }
       if(n<=6) {
         switch(n) {
           case 1: // FALLTHROUGH
           case 2: // FALLTHROUGH
           case 3: // FALLTHROUGH
           case 5: return true;
           default: return false;
         }
       }
       size_t p= bpos(n);
       if(p==0) {
         return false;
       }
       return !m_ptab.bit(p);
     };
     void swap(PrimeTab& ano) {
       m_ptab.swap(ano.m_ptab);
       Wy::swap(m_maxn, ano.m_maxn);
     };
     void reset() {
       m_ptab.reset();
     };

     Wy::Errno reset(NumType maxn) try {
       PrimeTab tmp(maxn);
       this->swap(tmp);
       return Wy::Ok;
     }
     catch(const Wy::Errno& e) {
       WY_RETURN(e);
     };
     Wy::Errno reset(const PrimeTab& rhs) {
       WY_RETURN(m_ptab.reset(rhs.m_ptab));
     };
     PrimeTab& operator=(const PrimeTab& rhs) {
       Wy::Errno r=m_ptab.reset(rhs.m_ptab);
       if(r!=Wy::Ok) {
         WY_THROW( Reply(r) );
       }
       return *this;
     };
};

#include <Wy.stdio.h>
#include "PrimeTab.h"

using namespace Wy;

void t1() {
size_t pcnt;
PrimeTab ptab(1LL<<31);
pcnt=0;
for(size_t n=0; n<ptab.max_num(); ++n) {
if(ptab.is_prime(n)) {
++pcnt;
}
}
cout << "pcnt=" << pcnt << WY_ENDL;
};

int main()
try {
t1();
cout << "OK" WY_ENDL;
return 0;
}
catch(const Errno& e) {
cerr << wrd(e) << WY_ENDL;
return -1;
}
catch(...) {
cerr << "main caught(...)" WY_ENDL;
return -1;
};

//----------------------
[]$ g++ t.cpp -lwy -O2
[]$ time ./a.out
pcnt=105097566
OK

real 0m34.223s
user 0m33.975s
sys 0m0.079s

PrimeTab(1LL<<31) should be able to test number <= 2^32
--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.c++

On Thu, 2024-03-14 at 17:35 +0800, wij wrote:

On Thu, 2024-03-14 at 17:20 +0800, wij wrote:

On Thu, 2024-03-14 at 07:25 +0100, Bonita Montero wrote:

Am 14.03.2024 um 05:44 schrieb wij:

On Tue, 2024-03-12 at 10:15 +0100, Bonita Montero wrote:

Am 11.03.2024 um 18:10 schrieb Tim Rentsch:

Sounds like you're using 1 bit per number, most of which are wasted.  If you use a different encoding the memory requirements can be much smaller.  How much memory do you have on the box?
If you have 64G you should be able to determine all primes
less than 1.5 trillion, using a simple encoding.

I'm omitting even numbers and I handle the number two as a
special case; that's the fastest solution.

I've mentioned this encoding before but let me give it again.
If numbers are considered mod 30, there are only 8 residues
that are not divisible by 2, 3, or 5.  The 8 residues are
1, 7, 11, 13, 17, 19, 23, and 29.  So a single byte can
hold all the information needed for 30 numbers, which means

     1500000000000 / 30 = 50000000000

which is to say 50 gigabytes should suffice.

Show me the code.

Every 30 natural numbers (or more) can be coded in one byte(8 bits):

Show me a working sieve with that that beats my code.

I am not "Tim Rentsch". I did not intend to beat your code but try to make things (what I saw) clear, and thought you might be confused. In general,  I cannot fully understand your code. Last time I copied your code, it did  not compile on my Linux machine.

//----------------------------------------
#include <Wy.stdlib.h>
#include <CSCall/VLInt.h>

// [Syn] PrimeTab is a table for prime numbers
//
class PrimeTab {
   public:
     typedef uint64_t NumType;

   private:
     WY_ENSURE(sizeof(NumType)<=sizeof(size_t));
     Wy::VLInt m_ptab;
     NumType m_maxn;

     // [Syn] Get the bit position storing info. for n
     //       0= pos for n (n is composite) is not available      //
     static size_t bpos(NumType n) {
       constexpr NumType Lcm=2*3*5;
       const NumType grp= 8*(n/Lcm);
       switch(n%30) {
         case  1: return grp;
         case  7: return grp+1;
         case 11: return grp+2;
         case 13: return grp+3;
         case 17: return grp+4;
         case 19: return grp+5;
         case 23: return grp+6;
         case 29: return grp+7;
         default: return 0;
       }
     };

   public:
     WY_DECL_REPLY;
     PrimeTab() : m_ptab(), m_maxn(0) {};
     PrimeTab(const PrimeTab& s) : m_ptab(s.m_ptab), m_maxn(s.m_maxn) {};
     PrimeTab(PrimeTab& s, Wy::ByMove_t) : m_ptab(s.m_ptab,Wy::ByMove),
       m_maxn(s.m_maxn) {};
     explicit PrimeTab(NumType maxn) : m_ptab(), m_maxn(maxn) {        for(NumType n=2; n<=m_maxn; ++n) {
         size_t p= bpos(n);
         if(p==0) {
           continue;   // composite number
         }
         if(m_ptab.bit(p)) {
           continue;   // composite number
         }

         for(NumType m=n+n; m<=m_maxn; m+=n) {            Wy::Errno r=m_ptab.set_bit(bpos(m),true);            if(r!=Wy::Ok) {
             WY_THROW( Reply(r) );
           }
         }
       };
     };
     NumType max_num() const { return m_maxn; };
     bool is_prime(NumType n) const {
       if(n>m_maxn) {
         WY_THROW( Reply(EINVAL) );
       }
       if(n<=6) {
         switch(n) {
           case 1: // FALLTHROUGH
           case 2: // FALLTHROUGH
           case 3: // FALLTHROUGH
           case 5: return true;
           default: return false;
         }
       }
       size_t p= bpos(n);
       if(p==0) {
         return false;
       }
       return !m_ptab.bit(p);
     };
     void swap(PrimeTab& ano) {
       m_ptab.swap(ano.m_ptab);
       Wy::swap(m_maxn, ano.m_maxn);
     };
     void reset() {
       m_ptab.reset();
     };

     Wy::Errno reset(NumType maxn) try {
       PrimeTab tmp(maxn);
       this->swap(tmp);
       return Wy::Ok;
     }
     catch(const Wy::Errno& e) {
       WY_RETURN(e);
     };
     Wy::Errno reset(const PrimeTab& rhs) {
       WY_RETURN(m_ptab.reset(rhs.m_ptab));
     };
     PrimeTab& operator=(const PrimeTab& rhs) {
       Wy::Errno r=m_ptab.reset(rhs.m_ptab);
       if(r!=Wy::Ok) {
         WY_THROW( Reply(r) );
       }
       return *this;
     };
};

#include <Wy.stdio.h>
#include "PrimeTab.h"

using namespace Wy;

void t1() {
 size_t pcnt;
 PrimeTab ptab(1LL<<31); 
 pcnt=0;
 for(size_t n=0; n<ptab.max_num(); ++n) {
   if(ptab.is_prime(n)) {
     ++pcnt;
   }
 }
 cout << "pcnt=" << pcnt << WY_ENDL;
};

int main()
try {
 t1();
 cout << "OK" WY_ENDL;
 return 0;
}
catch(const Errno& e) {
 cerr << wrd(e) << WY_ENDL;
 return -1;
}
catch(...) {
 cerr << "main caught(...)" WY_ENDL;
 return -1;
};

//----------------------
[]$ g++ t.cpp -lwy -O2
[]$ time ./a.out
pcnt=105097566
OK

real 0m34.223s
user 0m33.975s
sys 0m0.079s

PrimeTab(1LL<<31) should be able to test number <= 2^32

Correction: PrimeTab(1LL<<31) should be able to test number <= 2^62
--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.c++

Am 14.03.2024 um 10:35 schrieb wij:

On Thu, 2024-03-14 at 17:20 +0800, wij wrote:

On Thu, 2024-03-14 at 07:25 +0100, Bonita Montero wrote:

Am 14.03.2024 um 05:44 schrieb wij:

On Tue, 2024-03-12 at 10:15 +0100, Bonita Montero wrote:

Am 11.03.2024 um 18:10 schrieb Tim Rentsch:

Sounds like you're using 1 bit per number, most of which are
wasted.  If you use a different encoding the memory requirements
can be much smaller.  How much memory do you have on the box?
If you have 64G you should be able to determine all primes
less than 1.5 trillion, using a simple encoding.

I'm omitting even numbers and I handle the number two as a
special case; that's the fastest solution.

I've mentioned this encoding before but let me give it again.
If numbers are considered mod 30, there are only 8 residues
that are not divisible by 2, 3, or 5.  The 8 residues are
1, 7, 11, 13, 17, 19, 23, and 29.  So a single byte can
hold all the information needed for 30 numbers, which means

     1500000000000 / 30 = 50000000000

which is to say 50 gigabytes should suffice.

Show me the code.

Every 30 natural numbers (or more) can be coded in one byte(8 bits):

Show me a working sieve with that that beats my code.

I am not "Tim Rentsch". I did not intend to beat your code but try to make >> things (what I saw) clear, and thought you might be confused. In general,
I cannot fully understand your code. Last time I copied your code, it did
not compile on my Linux machine.

//----------------------------------------
#include <Wy.stdlib.h>
#include <CSCall/VLInt.h>

// [Syn] PrimeTab is a table for prime numbers
//
class PrimeTab {
   public:
     typedef uint64_t NumType;

   private:
     WY_ENSURE(sizeof(NumType)<=sizeof(size_t));
     Wy::VLInt m_ptab;
     NumType m_maxn;

     // [Syn] Get the bit position storing info. for n
     //       0= pos for n (n is composite) is not available >>>>      //
     static size_t bpos(NumType n) {
       constexpr NumType Lcm=2*3*5;
       const NumType grp= 8*(n/Lcm);
       switch(n%30) {
         case  1: return grp;
         case  7: return grp+1;
         case 11: return grp+2;
         case 13: return grp+3;
         case 17: return grp+4;
         case 19: return grp+5;
         case 23: return grp+6;
         case 29: return grp+7;
         default: return 0;
       }
     };

   public:
     WY_DECL_REPLY;
     PrimeTab() : m_ptab(), m_maxn(0) {};
     PrimeTab(const PrimeTab& s) : m_ptab(s.m_ptab), m_maxn(s.m_maxn) {};
     PrimeTab(PrimeTab& s, Wy::ByMove_t) : m_ptab(s.m_ptab,Wy::ByMove),
       m_maxn(s.m_maxn) {};
     explicit PrimeTab(NumType maxn) : m_ptab(), m_maxn(maxn) {
       for(NumType n=2; n<=m_maxn; ++n) {
         size_t p= bpos(n);
         if(p==0) {
           continue;   // composite number
         }
         if(m_ptab.bit(p)) {
           continue;   // composite number
         }

         for(NumType m=n+n; m<=m_maxn; m+=n) {
           Wy::Errno r=m_ptab.set_bit(bpos(m),true);
           if(r!=Wy::Ok) {
             WY_THROW( Reply(r) );
           }
         }
       };
     };
     NumType max_num() const { return m_maxn; };
     bool is_prime(NumType n) const {
       if(n>m_maxn) {
         WY_THROW( Reply(EINVAL) );
       }
       if(n<=6) {
         switch(n) {
           case 1: // FALLTHROUGH
           case 2: // FALLTHROUGH
           case 3: // FALLTHROUGH
           case 5: return true;
           default: return false;
         }
       }
       size_t p= bpos(n);
       if(p==0) {
         return false;
       }
       return !m_ptab.bit(p);
     };
     void swap(PrimeTab& ano) {
       m_ptab.swap(ano.m_ptab);
       Wy::swap(m_maxn, ano.m_maxn);
     };
     void reset() {
       m_ptab.reset();
     };

     Wy::Errno reset(NumType maxn) try {
       PrimeTab tmp(maxn);
       this->swap(tmp);
       return Wy::Ok;
     }
     catch(const Wy::Errno& e) {
       WY_RETURN(e);
     };
     Wy::Errno reset(const PrimeTab& rhs) {
       WY_RETURN(m_ptab.reset(rhs.m_ptab));
     };
     PrimeTab& operator=(const PrimeTab& rhs) {
       Wy::Errno r=m_ptab.reset(rhs.m_ptab);
       if(r!=Wy::Ok) {
         WY_THROW( Reply(r) );
       }
       return *this;
     };
};

#include <Wy.stdio.h>
#include "PrimeTab.h"

using namespace Wy;

void t1() {
size_t pcnt;
PrimeTab ptab(1LL<<31);
pcnt=0;
for(size_t n=0; n<ptab.max_num(); ++n) {
if(ptab.is_prime(n)) {
++pcnt;
}
}
cout << "pcnt=" << pcnt << WY_ENDL;
};

int main()
try {
t1();
cout << "OK" WY_ENDL;
return 0;
}
catch(const Errno& e) {
cerr << wrd(e) << WY_ENDL;
return -1;
}
catch(...) {
cerr << "main caught(...)" WY_ENDL;
return -1;
};

//----------------------
[]$ g++ t.cpp -lwy -O2
[]$ time ./a.out
pcnt=105097566
OK

real 0m34.223s
user 0m33.975s
sys 0m0.079s

PrimeTab(1LL<<31) should be able to test number <= 2^32

For my code this takes 1.7 seconds on a single Zen4 core with 5.7GHz.
With all 32 threads this takes 0,165 seconds. Any questions ? There's
a lot to do with your code ...

--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.c++

Am 14.03.2024 um 10:41 schrieb wij:

On Thu, 2024-03-14 at 17:35 +0800, wij wrote:

On Thu, 2024-03-14 at 17:20 +0800, wij wrote:

On Thu, 2024-03-14 at 07:25 +0100, Bonita Montero wrote:

Am 14.03.2024 um 05:44 schrieb wij:

On Tue, 2024-03-12 at 10:15 +0100, Bonita Montero wrote:

Am 11.03.2024 um 18:10 schrieb Tim Rentsch:

Sounds like you're using 1 bit per number, most of which are
wasted.  If you use a different encoding the memory requirements >>>>>>> can be much smaller.  How much memory do you have on the box?
If you have 64G you should be able to determine all primes
less than 1.5 trillion, using a simple encoding.

I'm omitting even numbers and I handle the number two as a
special case; that's the fastest solution.

I've mentioned this encoding before but let me give it again.
If numbers are considered mod 30, there are only 8 residues
that are not divisible by 2, 3, or 5.  The 8 residues are
1, 7, 11, 13, 17, 19, 23, and 29.  So a single byte can
hold all the information needed for 30 numbers, which means

     1500000000000 / 30 = 50000000000

which is to say 50 gigabytes should suffice.

Show me the code.

Every 30 natural numbers (or more) can be coded in one byte(8 bits):

Show me a working sieve with that that beats my code.

I am not "Tim Rentsch". I did not intend to beat your code but try to make >>> things (what I saw) clear, and thought you might be confused. In general, >>> I cannot fully understand your code. Last time I copied your code, it did >>> not compile on my Linux machine.

//----------------------------------------
#include <Wy.stdlib.h>
#include <CSCall/VLInt.h>

// [Syn] PrimeTab is a table for prime numbers
//
class PrimeTab {
   public:
     typedef uint64_t NumType;

   private:
     WY_ENSURE(sizeof(NumType)<=sizeof(size_t));
     Wy::VLInt m_ptab;
     NumType m_maxn;

     // [Syn] Get the bit position storing info. for n
     //       0= pos for n (n is composite) is not available >>>>>      //
     static size_t bpos(NumType n) {
       constexpr NumType Lcm=2*3*5;
       const NumType grp= 8*(n/Lcm);
       switch(n%30) {
         case  1: return grp;
         case  7: return grp+1;
         case 11: return grp+2;
         case 13: return grp+3;
         case 17: return grp+4;
         case 19: return grp+5;
         case 23: return grp+6;
         case 29: return grp+7;
         default: return 0;
       }
     };

   public:
     WY_DECL_REPLY;
     PrimeTab() : m_ptab(), m_maxn(0) {};
     PrimeTab(const PrimeTab& s) : m_ptab(s.m_ptab), m_maxn(s.m_maxn) {};
     PrimeTab(PrimeTab& s, Wy::ByMove_t) : m_ptab(s.m_ptab,Wy::ByMove),
       m_maxn(s.m_maxn) {};
     explicit PrimeTab(NumType maxn) : m_ptab(), m_maxn(maxn) { >>>>>        for(NumType n=2; n<=m_maxn; ++n) {
         size_t p= bpos(n);
         if(p==0) {
           continue;   // composite number
         }
         if(m_ptab.bit(p)) {
           continue;   // composite number
         }

         for(NumType m=n+n; m<=m_maxn; m+=n) {
           Wy::Errno r=m_ptab.set_bit(bpos(m),true);
           if(r!=Wy::Ok) {
             WY_THROW( Reply(r) );
           }
         }
       };
     };
     NumType max_num() const { return m_maxn; };
     bool is_prime(NumType n) const {
       if(n>m_maxn) {
         WY_THROW( Reply(EINVAL) );
       }
       if(n<=6) {
         switch(n) {
           case 1: // FALLTHROUGH
           case 2: // FALLTHROUGH
           case 3: // FALLTHROUGH
           case 5: return true;
           default: return false;
         }
       }
       size_t p= bpos(n);
       if(p==0) {
         return false;
       }
       return !m_ptab.bit(p);
     };
     void swap(PrimeTab& ano) {
       m_ptab.swap(ano.m_ptab);
       Wy::swap(m_maxn, ano.m_maxn);
     };
     void reset() {
       m_ptab.reset();
     };

     Wy::Errno reset(NumType maxn) try {
       PrimeTab tmp(maxn);
       this->swap(tmp);
       return Wy::Ok;
     }
     catch(const Wy::Errno& e) {
       WY_RETURN(e);
     };
     Wy::Errno reset(const PrimeTab& rhs) {
       WY_RETURN(m_ptab.reset(rhs.m_ptab));
     };
     PrimeTab& operator=(const PrimeTab& rhs) {
       Wy::Errno r=m_ptab.reset(rhs.m_ptab);
       if(r!=Wy::Ok) {
         WY_THROW( Reply(r) );
       }
       return *this;
     };
};

#include <Wy.stdio.h>
#include "PrimeTab.h"

using namespace Wy;

void t1() {
 size_t pcnt;
 PrimeTab ptab(1LL<<31);
 pcnt=0;
 for(size_t n=0; n<ptab.max_num(); ++n) {
   if(ptab.is_prime(n)) {
     ++pcnt;
   }
 }
 cout << "pcnt=" << pcnt << WY_ENDL;
};

int main()
try {
 t1();
 cout << "OK" WY_ENDL;
 return 0;
}
catch(const Errno& e) {
 cerr << wrd(e) << WY_ENDL;
 return -1;
}
catch(...) {
 cerr << "main caught(...)" WY_ENDL;
 return -1;
};

//----------------------
[]$ g++ t.cpp -lwy -O2
[]$ time ./a.out
pcnt=105097566
OK

real 0m34.223s
user 0m33.975s
sys 0m0.079s

PrimeTab(1LL<<31) should be able to test number <= 2^32

Correction: PrimeTab(1LL<<31) should be able to test number <= 2^62

You don't have that much memory, even with your compression.

--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.c++

On Thu, 2024-03-14 at 19:20 +0100, Bonita Montero wrote:

Am 14.03.2024 um 10:41 schrieb wij:

On Thu, 2024-03-14 at 17:35 +0800, wij wrote:

On Thu, 2024-03-14 at 17:20 +0800, wij wrote:

On Thu, 2024-03-14 at 07:25 +0100, Bonita Montero wrote:

Am 14.03.2024 um 05:44 schrieb wij:

On Tue, 2024-03-12 at 10:15 +0100, Bonita Montero wrote:

Am 11.03.2024 um 18:10 schrieb Tim Rentsch:

Sounds like you're using 1 bit per number, most of which are wasted.  If you use a different encoding the memory requirements
can be much smaller.  How much memory do you have on the box? If you have 64G you should be able to determine all primes
less than 1.5 trillion, using a simple encoding.

I'm omitting even numbers and I handle the number two as a special case; that's the fastest solution.

I've mentioned this encoding before but let me give it again. If numbers are considered mod 30, there are only 8 residues that are not divisible by 2, 3, or 5.  The 8 residues are
1, 7, 11, 13, 17, 19, 23, and 29.  So a single byte can
hold all the information needed for 30 numbers, which means

      1500000000000 / 30 = 50000000000

which is to say 50 gigabytes should suffice.

Show me the code.

Every 30 natural numbers (or more) can be coded in one byte(8 bits):

Show me a working sieve with that that beats my code.

I am not "Tim Rentsch". I did not intend to beat your code but try to make
things (what I saw) clear, and thought you might be confused. In general,
I cannot fully understand your code. Last time I copied your code, it did
not compile on my Linux machine.

//----------------------------------------
#include <Wy.stdlib.h>
#include <CSCall/VLInt.h>

// [Syn] PrimeTab is a table for prime numbers
//
class PrimeTab {
    public:
      typedef uint64_t NumType;

    private:
      WY_ENSURE(sizeof(NumType)<=sizeof(size_t));
      Wy::VLInt m_ptab;
      NumType m_maxn;

      // [Syn] Get the bit position storing info. for n       //       0= pos for n (n is composite) is not available
      //
      static size_t bpos(NumType n) {
        constexpr NumType Lcm=2*3*5;
        const NumType grp= 8*(n/Lcm);
        switch(n%30) {
          case  1: return grp;
          case  7: return grp+1;
          case 11: return grp+2;
          case 13: return grp+3;
          case 17: return grp+4;
          case 19: return grp+5;
          case 23: return grp+6;
          case 29: return grp+7;
          default: return 0;
        }
      };

    public:
      WY_DECL_REPLY;
      PrimeTab() : m_ptab(), m_maxn(0) {};
      PrimeTab(const PrimeTab& s) : m_ptab(s.m_ptab), m_maxn(s.m_maxn) {};
      PrimeTab(PrimeTab& s, Wy::ByMove_t) : m_ptab(s.m_ptab,Wy::ByMove),
        m_maxn(s.m_maxn) {};
      explicit PrimeTab(NumType maxn) : m_ptab(), m_maxn(maxn) {
        for(NumType n=2; n<=m_maxn; ++n) {           size_t p= bpos(n);
          if(p==0) {
            continue;   // composite number           }
          if(m_ptab.bit(p)) {
            continue;   // composite number           }

          for(NumType m=n+n; m<=m_maxn; m+=n) {             Wy::Errno r=m_ptab.set_bit(bpos(m),true);             if(r!=Wy::Ok) {
              WY_THROW( Reply(r) );             }
          }
        };
      };
      NumType max_num() const { return m_maxn; };
      bool is_prime(NumType n) const {
        if(n>m_maxn) {
          WY_THROW( Reply(EINVAL) );
        }
        if(n<=6) {
          switch(n) {
            case 1: // FALLTHROUGH             case 2: // FALLTHROUGH             case 3: // FALLTHROUGH             case 5: return true;
            default: return false;
          }
        }
        size_t p= bpos(n);
        if(p==0) {
          return false;
        }
        return !m_ptab.bit(p);
      };
      void swap(PrimeTab& ano) {
        m_ptab.swap(ano.m_ptab);
        Wy::swap(m_maxn, ano.m_maxn);
      };
      void reset() {
        m_ptab.reset();
      };

      Wy::Errno reset(NumType maxn) try {
        PrimeTab tmp(maxn);
        this->swap(tmp);
        return Wy::Ok;
      }
      catch(const Wy::Errno& e) {
        WY_RETURN(e);
      };
      Wy::Errno reset(const PrimeTab& rhs) {
        WY_RETURN(m_ptab.reset(rhs.m_ptab));
      };
      PrimeTab& operator=(const PrimeTab& rhs) {         Wy::Errno r=m_ptab.reset(rhs.m_ptab);
        if(r!=Wy::Ok) {
          WY_THROW( Reply(r) );
        }
        return *this;
      };
};

#include <Wy.stdio.h>
#include "PrimeTab.h"

using namespace Wy;

void t1() {
  size_t pcnt;
  PrimeTab ptab(1LL<<31);
  pcnt=0;
  for(size_t n=0; n<ptab.max_num(); ++n) {
    if(ptab.is_prime(n)) {
      ++pcnt;
    }
  }
  cout << "pcnt=" << pcnt << WY_ENDL;
};

int main()
try {
  t1();
  cout << "OK" WY_ENDL;
  return 0;
}
catch(const Errno& e) {
  cerr << wrd(e) << WY_ENDL;
  return -1;
}
catch(...) {
  cerr << "main caught(...)" WY_ENDL;
  return -1;
};

//----------------------
[]$ g++ t.cpp -lwy -O2
[]$ time ./a.out
pcnt=105097566
OK

real 0m34.223s
user 0m33.975s
sys 0m0.079s

PrimeTab(1LL<<31) should be able to test number <= 2^32

Correction: PrimeTab(1LL<<31) should be able to test number <= 2^62

You don't have that much memory, even with your compression.

//----- factorize.cpp
#include <Wy.stdio.h>
#include <Wy.unistd.h>
#include "PrimeTab.h"
using namespace Wy;
uint64_t read_number() { // Read uint64_t from cin
Errno r;
String buf;
uint64_t res;
cin >> buf;
if((r=strnum(res,buf.c_str()))!=EBADMSG) {
WY_THROW(r);
}
return res;
};
void t1() {
cout << "Setup ptab ... wait (70s on my machine)" WY_ENDL WY_ENDL;
PrimeTab ptab(1LL<<32);
uint64_t num;
for(;;) { // Read number (uint64_t) and print the prime factorization
cout << "Number=";
num= read_number();
cout << num << "= ";
for(uint64_t dvr=2; dvr<=ptab.max_num(); ) {
if(ptab.is_prime(dvr)==false) {
++dvr; continue;
}
if(num%dvr) {
++dvr; continue;
}
cout << dvr << '*';
num/=dvr;
if(num<dvr) {
break;
}
}
if(num>1) {
cout << num;
}
cout << WY_ENDL;
}
};
int main()
try {
t1();
cout << "OK" WY_ENDL;
return 0;
}
catch(const Errno& e) {
cerr << wrd(e) << WY_ENDL;
return -1;
}
catch(...) {
cerr << "main caught(...)" WY_ENDL;
return -1;
};
---------------------------------
[]$ g++ factorize.cpp -lwy -O2
[]$ ./a.out
Setup ptab ... wait (70s on my machine)
Number=18446744073709551615
18446744073709551615= 3*5*17*257*641*65537*6700417*
Number=18446744073709551557
18446744073709551557= 18446744073709551557
Number=
-----------
Note: 18446744073709551615= 2^64-1
Note: 18446744073709551557 is the greatest prime found less than 2^64.
This shoud be the worst case (took about 5 sec.)
Note: Constructing PrimeTab ptab(1LL<<32) consumes about (2^32)/30= 143 (Mbytes)
I know you are addressing hard-ware programming, but IMO, the performance/cost ratio is very low.
--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.c++

Am 15.03.2024 um 09:30 schrieb wij:

Number=18446744073709551615
18446744073709551615= 3*5*17*257*641*65537*6700417* Number=18446744073709551557
18446744073709551557= 18446744073709551557
Number=

-----------
Note: 18446744073709551615= 2^64-1
Note: 18446744073709551557 is the greatest prime found less than 2^64.
This shoud be the worst case (took about 5 sec.)
Note: Constructing PrimeTab ptab(1LL<<32) consumes about (2^32)/30= 143 (Mbytes)

I know you are addressing hard-ware programming, but IMO, the performance/cost
ratio is very low.

Then you don't calculate the whole range from two up to your upper
bound. If you have 30 numbers per 8 bits you'd need 1.073.741.824
Gigabytes for that.

--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.c++

On Fri, 2024-03-15 at 11:21 +0100, Bonita Montero wrote:

Am 15.03.2024 um 09:30 schrieb wij:

Number=18446744073709551615
18446744073709551615= 3*5*17*257*641*65537*6700417* Number=18446744073709551557
18446744073709551557= 18446744073709551557
Number=

-----------
Note: 18446744073709551615= 2^64-1
Note: 18446744073709551557 is the greatest prime found less than 2^64.        This shoud be the worst case (took about 5 sec.)
Note: Constructing PrimeTab ptab(1LL<<32) consumes about (2^32)/30= 143 (Mbytes)

I know you are addressing hard-ware programming, but IMO, the performance/cost
ratio is very low.

Then you don't calculate the whole range from two up to your upper
bound. If you have 30 numbers per 8 bits you'd need 1.073.741.824
Gigabytes for that.

Don't know what the upper bound and "1.073.741.824" mean. If I have 8-giga RAM, I can setup a
primetable for number <= 8G*30= 2.4*10^11. From this table, I can
factorize number <= (2.4*10^11)^2= 5.76*10^22 (a 76-bit number).
As I remember, your program does not use integer greater than uint64_t, why you ask for such
a big number?
--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.c++

Am 15.03.2024 um 12:07 schrieb wij:

On Fri, 2024-03-15 at 11:21 +0100, Bonita Montero wrote:

Am 15.03.2024 um 09:30 schrieb wij:

Number=18446744073709551615
18446744073709551615= 3*5*17*257*641*65537*6700417*
Number=18446744073709551557
18446744073709551557= 18446744073709551557
Number=

-----------
Note: 18446744073709551615= 2^64-1
Note: 18446744073709551557 is the greatest prime found less than 2^64.
       This shoud be the worst case (took about 5 sec.)
Note: Constructing PrimeTab ptab(1LL<<32) consumes about (2^32)/30= 143 (Mbytes)

I know you are addressing hard-ware programming, but IMO, the performance/cost
ratio is very low.

Then you don't calculate the whole range from two up to your upper
bound. If you have 30 numbers per 8 bits you'd need 1.073.741.824
Gigabytes for that.

Don't know what the upper bound and "1.073.741.824" mean. If I have 8-giga RAM, I can setup a
primetable for number <= 8G*30= 2.4*10^11. From this table, I can
factorize number <= (2.4*10^11)^2= 5.76*10^22 (a 76-bit number).

Maybe, but you can't store the whole range in memory but just
calculate segments beyond sqrt( max ) fitting into memory.

As I remember, your program does not use integer greater than uint64_t, why you ask for such
a big number?

--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.c++

Bonita Montero <Bonita.Montero@gmail.com> writes:

Am 11.03.2024 um 18:10 schrieb Tim Rentsch:

Sounds like you're using 1 bit per number, most of which are
wasted. If you use a different encoding the memory requirements
can be much smaller. How much memory do you have on the box?
If you have 64G you should be able to determine all primes
less than 1.5 trillion, using a simple encoding.

I'm omitting even numbers and I handle the number two as a
special case; that's the fastest solution.

I've mentioned this encoding before but let me give it again.
If numbers are considered mod 30, there are only 8 residues
that are not divisible by 2, 3, or 5. The 8 residues are
1, 7, 11, 13, 17, 19, 23, and 29. So a single byte can
hold all the information needed for 30 numbers, which means

1500000000000 / 30 = 50000000000

which is to say 50 gigabytes should suffice.

Show me the code.

Apparently you have missed the point.
--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.c++

Am 20.04.2024 um 17:35 schrieb Tim Rentsch:

Bonita Montero <Bonita.Montero@gmail.com> writes:

Am 11.03.2024 um 18:10 schrieb Tim Rentsch:

Sounds like you're using 1 bit per number, most of which are
wasted. If you use a different encoding the memory requirements
can be much smaller. How much memory do you have on the box?
If you have 64G you should be able to determine all primes
less than 1.5 trillion, using a simple encoding.

I'm omitting even numbers and I handle the number two as a
special case; that's the fastest solution.

I've mentioned this encoding before but let me give it again.
If numbers are considered mod 30, there are only 8 residues
that are not divisible by 2, 3, or 5. The 8 residues are
1, 7, 11, 13, 17, 19, 23, and 29. So a single byte can
hold all the information needed for 30 numbers, which means

1500000000000 / 30 = 50000000000

which is to say 50 gigabytes should suffice.

Show me the code.

Apparently you have missed the point.

I want to see the code for your idea.

--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.c++

Am 20.04.2024 um 18:34 schrieb Bonita Montero:

Am 20.04.2024 um 17:35 schrieb Tim Rentsch:

Bonita Montero <Bonita.Montero@gmail.com> writes:

Am 11.03.2024 um 18:10 schrieb Tim Rentsch:

Sounds like you're using 1 bit per number, most of which are
wasted.  If you use a different encoding the memory requirements
can be much smaller.  How much memory do you have on the box?
If you have 64G you should be able to determine all primes
less than 1.5 trillion, using a simple encoding.

I'm omitting even numbers and I handle the number two as a
special case;  that's the fastest solution.

I've mentioned this encoding before but let me give it again.
If numbers are considered mod 30, there are only 8 residues
that are not divisible by 2, 3, or 5.  The 8 residues are
1, 7, 11, 13, 17, 19, 23, and 29.  So a single byte can
hold all the information needed for 30 numbers, which means

     1500000000000 / 30 = 50000000000

which is to say 50 gigabytes should suffice.

Show me the code.

Apparently you have missed the point.

I want to see the code for your idea.

Eh, wij's idea ...

--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.c++

Bonita Montero <Bonita.Montero@gmail.com> writes:

Am 20.04.2024 um 17:35 schrieb Tim Rentsch:

Bonita Montero <Bonita.Montero@gmail.com> writes:

[...]

Show me the code.

Apparently you have missed the point.

I want to see the code for your idea.

Yes I already understood what you want. That is what
led me to conclude that you have missed the point.
--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.c++

Am 24.04.2024 um 21:28 schrieb Tim Rentsch:

Bonita Montero <Bonita.Montero@gmail.com> writes:

Am 20.04.2024 um 17:35 schrieb Tim Rentsch:

Bonita Montero <Bonita.Montero@gmail.com> writes:

[...]

Show me the code.

Apparently you have missed the point.

I want to see the code for your idea.

Yes I already understood what you want. That is what
led me to conclude that you have missed the point.

I don't have "missed the point"; I just want to see the code
basing on the mentioned idea that is faster than my code.
--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.c++

Bonita Montero <Bonita.Montero@gmail.com> writes:

Am 24.04.2024 um 21:28 schrieb Tim Rentsch:

Bonita Montero <Bonita.Montero@gmail.com> writes:

Am 20.04.2024 um 17:35 schrieb Tim Rentsch:

Bonita Montero <Bonita.Montero@gmail.com> writes:

[...]

Show me the code.

Apparently you have missed the point.

I want to see the code for your idea.

Yes I already understood what you want. That is what
led me to conclude that you have missed the point.

I don't have "missed the point"; [...]

There is more than one school of thought on that question.
--- Synchronet 3.20a-Linux NewsLink 1.114