[racket] bytes, bit-vectors and sieving numbers

Jens,

On 01/05/14 10:41, Jens Axel Søgaard wrote:
> https://github.com/plt/racket/blob/6722b7a71e234ab3d41e936ab8605f1ef5e456c8/racket/collects/data/bit-vector.rkt

The Lucid sieving differs from Eratosthenes sieving in this respect:

With primes, you can eliminate previously eliminated non-primes; e.g. when
sieving "3", you eliminate 3, 6, 9, 12 ... even though 6 and 12 have been
eliminated by the "2" pass.

With Lucid numbers, I need to keep walking the list to determine if a
candidate has been crossed off before (the "remaining" part of the
description). Hence I need to keep reading the vector (of bits or bytes);
and I would guess it requires O(N²) reads.

The performance for a simple PRIME sieve (which doesn't do that much
reading, -- O(N), vs. O(N²)) is illustrated with:

https://gist.github.com/tim-brown/789239fa40c734d512e4
cpu time: 1429 real time: 1431 gc time: 0
cpu time: 24 real time: 24 gc time: 0
cpu time: 256 real time: 255 gc time: 0

I assume that the load is in "bit-vector-ref"; there is a lot of
type-checking around it, and a tantalisingly un-provided unsafe version,
too :-)

> I notice that you access the elements in the bit-vector from left to right.
> Maybe something can be done to improve the speed of this particular
> access pattern?

This particular access pattern is, to be honest, for generating some
numbers that seem to have no value other than recreational curiosity; so
I'm afraid that I'm not going be able to spend a lot of time reordering my
search in this case.

> Or perhaps Typed Racket can be used?

My first reaction was that maybe the library was implemented in TR. But it
isn't. Is there anything in the library that makes it friendlier to TR than
to Racket? That might cause it to run faster?

Tim

For reference: the Lucid numbers are:
A003309: http://oeis.org/A003309
Ludic numbers: apply the same sieve as Eratosthenes, but cross off every
k-th /remaining/ number.


-- 
Tim Brown <tim.brown at cityc.co.uk>  | City Computing Limited            |
T: +44 20 8770 2110                | City House, Sutton Park Road      |
F: +44 20 8770 2130                | Sutton, Surrey, SM1 2AE, GB       |
-----------------------------------------------------------------------|
BEAUTY:  What's in your eye when you have a bee in your hand           |
-----------------------------------------------------------------------'
City Computing Limited registered in London No. 1767817.
Registered Office: City House, Sutton Park Road, Sutton, Surrey, SM1 2AE
VAT number 372 8290 34.