PasteRack.org
Paste # 8147
2021-10-11 02:27:54

Fork as a new paste.

Paste viewed 427 times.


Embed:

  1. #lang typed/racket/base
  2. (require
  3.          typed/rackunit
  4.          typed/racket/class)
  5.  
  6. (define prime-sieve% : Object% (class
  7.                       object%
  8.                       (init-field limit : Positive-Integer)
  9.                       (super-new)
  10.                        ;; only need 1/2 b/c evens are not primes (except 2), pretend vector is just odd #s
  11.                       ;; bit-vectors are zero indexed!! must substract one when indexing!
  12.                       (define rawbits : (Vectorof Positive-Integer) (vector (floor (/ (+ 1 limit) 2)) #t)) ; vector of #t and #f vals
  13.  
  14.                       (field [sieve-size : Positive-Integer limit])
  15.  
  16.                       (define prime-counts : (HashTable Positive-Integer Positive-Integer) '#hash((10 . 4)
  17.                                                   (100 . 25)
  18.                                                   (1000 . 168)
  19.                                                   (10000 . 1229)
  20.                                                   (100000 . 9592)
  21.                                                   (1000000 . 78498)
  22.                                                   (10000000 . 664579)
  23.                                                   (100000000 . 5761455)))
  24.                       (: validate-results (-> Boolean))
  25.                       (define (validate-results)
  26.                         ;; checks to see if sieve size is in the prime-counts hash
  27.                         ;; if not return false. else return true
  28.                         (if (hash-has-key? prime-counts sieve-size)
  29.                             (= (hash-ref prime-counts sieve-size) (count-primes))
  30.                             #f))
  31.  
  32.                       (:get-bit (-> Positive-Integer Boolean))
  33.                       (define (get-bit index)
  34.                         ;; gets bit (#t or #f) in bit-vector, but skips all even indexes
  35.                         ;; we divide index by 2 b/c we still loop from start to end of initial sieve size
  36.                         (if (= (modulo index 2) 0) #f (vector-ref rawbits (round (/ (sub1 index) 2)))))
  37.  
  38.                       (:clear-bit (-> Positive-Integer Boolean))
  39.                       (define (clear-bit index)
  40.                         ;; sets a #t value in vector to #f (not prime)
  41.                         (if (= (modulo index 2) 0)
  42.                             #f
  43.                             (vector-set! rawbits (floor (/ (sub1 index) 2)) #f)))
  44.  
  45.                       (:run-sieve (-> Void))
  46.                       (define/public (run-sieve)
  47.                         (define factor 3)
  48.                         ;; iterate to sqrt of sieve-size b/c half values already thrown out (even)
  49.                         (define q (sqrt sieve-size))
  50.                         (let loop ()
  51.                           (for ([num : Integer (in-range [factor : Integer] [sieve-size : Integer])]
  52.                                 #:break (if (eq? (get-bit num) #t) (set! factor num) #f))
  53.                             void)
  54.                           (for ([num : Integer (in-range (* factor 3) sieve-size (* factor 2))])
  55.                             (clear-bit num))
  56.  
  57.                           (set! factor (+ factor 2))
  58.  
  59.                           (unless (> factor q)
  60.                             (loop))))
  61.  
  62.                       (:count-primes (-> Positive-Integer))
  63.                       (define (count-primes)
  64.                         ;; return # of bits set. counts all #t bits
  65.                         (vector-length (vector-filter-not false? vec)))
  66.  
  67.                       (:print-results (-> Boolean Positive-Float Positive-Integer))
  68.                       (define/public (print-results show-results duration passes)
  69.                         (if (eq? show-results #t) (display "2, ") #f)
  70.                         (define count 1)
  71.                         (for ([num : Positive-Integer (in-range 3 sieve-size)])
  72.                           (cond
  73.                             [(and (eq? (get-bit num) #t) (eq? show-results #t)) (begin
  74.                                                                                   ;; use display to keep "" from printing
  75.                                                                                   (display (format "~a, " num))
  76.                                                                                   (set! count (+ count 1)))]
  77.                             [(eq? (get-bit num) #t) (set! count (+ count 1))]))
  78.                         ;; check-equal only complains when there is an error
  79.                         (check-equal? count (count-primes))
  80.                         (displayln "")
  81.  
  82.                         (println (format "passes: ~a, Time: ~a, Avg: ~a, Limit: ~a, Count: ~a, Valid: ~a"
  83.                                          passes duration (/ duration passes) sieve-size count (validate-results)))
  84.  
  85.                         (displayln "")
  86.                         (println (format "diego-e-crespo;~a;~a;l;algorithm=base,faithful=yes" passes duration))
  87.                         )))
  88.  
  89. (let ([start-time (current-inexact-milliseconds)]
  90.       [five-seconds 5]
  91.       [max 100])
  92.   (let loop ([passes 1])
  93.     (define sieve (Instance prime-sieve%) (new prime-sieve% [limit max]))
  94.     (send sieve run-sieve)
  95.     (if (>= (- (/ (current-inexact-milliseconds) 1000) (/ start-time 1000)) 5)
  96.         (send sieve print-results #f (- (/ (current-inexact-milliseconds) 1000) (/ start-time 1000)) passes)
  97.         (loop (+ passes 1)))))

=>