[racket] bytes, bit-vectors and sieving numbers

Hi Tim,

The code in question is here:

https://github.com/plt/racket/blob/6722b7a71e234ab3d41e936ab8605f1ef5e456c8/racket/collects/data/bit-vector.rkt

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?

Or perhaps Typed Racket can be used?

/Jens Axel


2014-05-01 10:17 GMT+02:00 Tim Brown <tim.brown at cityc.co.uk>:
> Folks,
>
> I've just posted an implementation for "Lucid Numbers" on rosettacode.org
> for Racket. It sieves numbers using using a "bytes" variable, which, for
> this purpose is what I consider to be a "vector of bytes".
>
> The code is different from a "sieve of Eratosthenes", in that (at least my
> implementation), each number has to be revisited once for every Lucid
> number less than it. Even so, I hardly notice it building the sieve for
> 25,000 numbers.
>
> However, this representation requires 1 byte per number considered; and
> lucidity is a boolean state... representable by nothing more than a bit.
> And ooh! Racket has bit-vectors.
>
> I tried transcribing my program, using data/bit-vector - and the same
> 25,000 entry sieve takes a significant (19 s, or so) to execute. This came
> as a shock, since I'd've only expected there to be a layer of shifting and
> ANDing to byte (and/or fixnum) vectors.
>
> The GIST of it is here:
> https://gist.github.com/tim-brown/87b05c16f41aa86a1421
>
>
> Am I missing something fundamental here?
> Can I (require data/bit-vector) in a different way or something like that?
> Am I better off hand-rolling this?
>
> I would like to use bit-vectors for things like cellular automata; but the
> performance cost seems to be prohibitive (or at least very discouraging).
>
> In the meantime, I have seven spare bits for each entry in my sieve... any
> suggestions as to what I might want to flag in there?
>
> Regards,
>
> Tim
>
> --
> 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.
> ____________________
>  Racket Users list:
>  http://lists.racket-lang.org/users



-- 
--
Jens Axel Søgaard