finding largest prime number in a file

[MikeStgt]

@jonnin
Have to switch to vector<bool> because max size of bitset is too restricted (varies depending the compiler). Hoped only available storage would limit it. Alas, now missing the convenient pn.count() to get the number of found primes at once.

[jonnin]

yes, and some cpu optimize count (have instruction for # of bits set to 1 in an integer for ~1 clock cycle per N bits). So that will be a little annoying. You could take an assembly axe to it and make it work on those systems by shoving the vector bool recast as ints into registers and counting 1/64th or 1/128th as many things if you want speed over portable, but I can't think of a way to do it otherwise as counting is so fast any attempt to shuffle it into a c++ count enable solution would be slower than just counting it.

[MikeStgt]

You could take an assembly axe to it

Yes, for sure <grin> aiming with cannons at sparrows. I do all this to learn about C++ and still struggle with its documentation. It's so frustrating to have ideas and no chance to tell the machine about. In Milan without a single word Italian in a bar gelateria I will get exactly the ice cream I like, alas C++ is a bit different.

At the moment I am not able to reference neither a vector<bool> nor a bitset in a function call. How may I do:
bool ChkPrmWIF(tytok number, bitset& sfx)
to get rid of this error: 'bitset' is not a type -- where in this documentation
http://www.cplusplus.com/reference/bitset/bitset/reference/
may I find the type to define in the function call?
(BTW, I returned from vector<bool> to bitset, as it is sufficient for an extend sieved within 0.1 seconds. My sieve is too slow to cover the complete range up to 2⁶⁴.)

(excerpt)
unsigned const SoE_IxArSi(786432);
/* initialize prime number index array first */
    unsigned long p, q;
    bitset<SoE_IxArSi> pnfx;
    pnfx.set();
    for (p = 1; p < sqrt(2*SoE_IxArSi+1)/2; p++)  // there is a hidden +0.5 -- find it ;)
       if (pnfx[n] && (p+p+2 < SoE_IxArSi/p))
            for (q = 2 * p * (p + 1); q < SoE_IxArSi; pnfx[q] = false, q += p + p + 1);

[jonnin]

oh, its just like vector.
you need
bool ChkPrmWIF(tytok number, bitset<type>& sfx)

you can immediately double your sieve's speed by i+=2 and only doing odd values. you already set all the evens to false, or you should...
how long does it take? If you are doing the write to file approach, even if it runs all day, its a do-once and done ...

[MikeStgt]

double your sieve's speed by i+=2

The bitset is "compacted" (some kind of), it contains only flags for odd numbers. So sfx[5] stands for number 2*5+1 = 11. It's a test if this little index calculation could be benefical. Sieving up to 2 * 786432 - 1 takes a bit less than 0.1 seconds on my dated machine.

BTW,
bool ChkPrmWIF(tytok number, bitset<type>& sfx)
results in

84	37 ...	[Error] 'type' was not declared in this scope

Changed it to
bool ChkPrmWIF(tytok number, bitset<long long unsigned int>& sfx)
and... LOL!

84	59 ...	[Error] expected a constant of type 'long long unsigned int', got 'long long unsigned int'

Oh, sorry, got it:
bool ChkPrmWIF(tytok number, bitset<SoE_IxArSi>& sfx)
It compiles, alas it does not run:

Segmentation fault

[jonnin]

that I can't help you with. I haven't been able to do anything with 64 bit sizes either, between seg faults or silent resize of the containers its been pointless. I haven't tried super hard though. I may take a deeper look but you are up against memory fragmentation (I think it needs a solid block) on top of any other limitations.

[MikeStgt]

I can't help you

Anyway, thank you for your time, your bitset<type>& sfx -hint was helpful.
At the moment I see no reason for the Segmentation fault. I have two ideas how to circumvent it, one uncertain if it works, one uncertain if C++ will do that.

First: Similar as I may cluster several variables in a data structure and hand it over as a reference I may do so with a bitset too. Or define an equivalence, called Unions in C++. So the reference will be to a string which in fact is the bitset. Uncertain if this could cure the situation.

Next idea could be more promising, but I have not found yet if C++ offers it. In FORTRAN it is called SAVE. Variables in subroutines are uninitialized on every call to a subroutine -- except for the variables declared SAVE. Those keep their value when leaving the subroutine until next call.

Question: does C++ know something similar? Then I could setup the bitset inside the function and keep it there until next use. This would avoid the doubtful reference.

Edit:
Answer: static does the trick.

MRT counts 78498 primes from 1 to 1000001 within 0.644 seconds.
SPC counts 78498 primes from 1 to 1000001 within 0.247 seconds.
PWW counts 78498 primes from 1 to 1000001 within 0.127 seconds.
CWF counts 78498 primes from 1 to 1000001 within 0.011 seconds.
MRT counts 45166 primes from 4000000000 to 4001000000 within 1.167 seconds.
SPC counts 45166 primes from 4000000000 to 4001000000 within 12.315 seconds.
PWW counts 45166 primes from 4000000000 to 4001000000 within 6.216 seconds.
CWF counts 45167 primes from 4000000000 to 4001000000 within 8.738 seconds.
MRT counts 22475 primes from 18446744073708551615 to 18446744073709551615 within 5.256 seconds.
SPC skipped.
PWW skipped.
CWF not applicable above 2473904308225

[jonnin]

unions are supposed to only be used one way. that is a union of a string and bytes can only be accessed as a string OR as bytes, but not both. however every known compiler seems to ignore this standard rule if you relax the error level when you compile.

you can do the exact same thing with a pointer cast if you are the type that gets bent out over nonstandard code or rule-bending. The union just pretties up the casting, really. and a char* would work also, why do you need the 'string' part? That just hides the memory allocation.

the union will work until you run out of solid blocks of memory up to the size you need or you run out of bytes for std string (max length is ???)

the word you want for save is "static"
int foo()
{
static int x = 0;
return x++; //every call returns the next value.. 0,1,2,3,...
}


And I typed that and you already found it...

entertainment: replace the ifs in the pww with a lookup table for the answer from 0-6. if that does what I think it will to your times, try it on the other tests too?

[MikeStgt]

replace the ifs in the pww with a lookup table for the answer from 0-6.

The gain by replacing

	if ( number  < 2 ) return false;
	if ( number  < 4 ) return true;
	if (!(number % 2)) return false;
	if (!(number % 3)) return false;
	if ( number == 5 ) return true;
	if (!(number % 5)) return false;
	if ( number < 7*7) return true;

by

	static bool fst[]{false, false, true, true, false, true, false};
	if ( number  < 7 ) return fst[number];
	if (!(number % 2)) return false;
	if (!(number % 3)) return false;
	if (!(number % 5)) return false;
	if ( number < 7*7) return true;

is not measurable.

Nevertheless thank you for the info about union.

[jonnin]

its hit or miss on that. some code the compiler can heavily optimize the conditional jumps and some code it can't. Ive seen a single if statement add significant time to a tight loop over billions of things, and ive seen it do nothing. Only way I know of to find out is to try both versions, though.

you could also try gcd(number, 30) for lines 3,4,5 but that seems unlikely to win out. The precompiled gcd is very optimal, but it still does a loop ... but these are 'playing with it' tweaks at this point... % is really fast as well.

[MikeStgt]

Ive seen a single if statement add significant time to a tight loop over billions of things

That could be guesswork -- guesswork what comes next in pipeline. An if could cause a branch that forces to rebuild the pipe content -- https://en.wikipedia.org/wiki/Instruction_pipelining
So even it looks like more work (as you mentioned before already) it could be finished faster than "optimized" with if/else annoyance.

Edit: changed link

[jonnin]

I know. But I don't have any good way to know whether a given piece of code on a given compiler will do better without the ifs. Only way I know is to try it both ways on the target machine OR just write 'ifless' as much as you can.