Liste des Groupes | Revenir à cl c++ |
On 22/05/2024 03:06, Tim Rentsch wrote:
>Vir Campestris <vir.campestris@invalid.invalid> writes:>
>I've been playing with this. Has it really been this long? I>
ought to have more time than this... [...]
>
I missed Tim's Mod 30 trick, and that might well help. But I
think I'm bored with this. It would save a lot of memory, but
the extra computation might make it slower.
Two comments. Using the mod 30 encoding can be speed competitive
with simpler encodings. The second comment is, it isn't just
that less memory is used, but that more primes can be found.
Bonita brags about how fast some code is, but it's an apples
and oranges comparison - that code doesn't do the job because
it runs into a memory limit way sooner than using a mod 30
encoding, and trying to run past that limit would make the
code R E A L L Y S L O W.
>Maybe I'll try one day ;)>
I hope you do. If you have some difficulty seeing how to
avoid the seeming speed penalties, feel free to ask, I am
happy to help.
I think I've come to the end of what my code will do. [...]
Firstly the C++ bit:
>
std::vector<bool> is much too slow to be any use.
[various alternatives]
That's the end of the on-topic part.
>
I don't store even numbers. That's an optimisation, and is of course
equivalent to Tim's Mod 30 trick, but with mod 2 instead. And it
doesn't require an divide which may be slow.
When I mask out just 3 I get a pattern like this:
>
2492492492492490
>
There is a single nybble at the end of that which is zero, but the
rest is a 3-nybble repeat. [similarly for 3 and 5, etc...]
However I can build a mask from the ones for 3 and 5, which has a
repeat of 15 (3*5)
6692cd259a4b3490,
96692cd259a4b349,496692cd259a4b34,3496692cd259a4b3,b3496692cd259a4b,
4b3496692cd259a4,a4b3496692cd259a,9a4b3496692cd259,59a4b3496692cd25,
259a4b3496692cd2,d259a4b3496692cd,cd259a4b3496692c,2cd259a4b3496692,
92cd259a4b349669,692cd259a4b34966,6692cd259a4b3496
>
and copy that.
>
In fact I can do that with any number of single prime masks I want.
[...]
Note that although this has been quite a fun thing to play with it's
had almost no C++ content. In fact I found that to get best
performance I had to drop down to C type code.
I kept a class to
manage my buffers though, it's much easier to drop an object that
manages a malloc-ed buffer than to remember exactly when I need to
call free. Correctness trumps speed.
Now Mod 30 - by storing the odd numbers only I'm halving the storage,
and I don't need to do an expensive divide. It's only shifts and ANDs.
>
If I use mod 30 (30 = 2*3*5) conveniently there are 8 candidate
numbers I need to store a mask for.
Sadly my computer likes 64 bit
operations better. But the required storage is now only 27% of the
original mask if all numbers are put in it.
I can carry on with this, but the storage doesn't have any more nice
sizes. [...]
Maybe I'll play with it. But the rain stopped, and I must get on
with the weeding!
Les messages affichés proviennent d'usenet.