best version? #3

New Issue

bitchfemcel · 2024-02-03T17:40:02-05:00

bitchfemcel commented

2024-02-03 17:40:02 -05:00

here's my sieve of era:

/+  *ari-lib
|=  n=@ud
^-  (list @ud)
=/  field 
  ^-  (list (unit @ud))
  (turn (gulf 0 n) some)
:: we can stop at (sqrt n) for math reasons
=/  stop-point  (whole-sqrt n)
=/  index  2
|-
?:  (gth index stop-point)
  =/  unwrapped  (turn (slag 2 field) need)
  (skim unwrapped |=(n=@ud !=(n 0)))
=/  indices  (every-n index field)
%=  $
  field  (clear-composites field indices)
  index  (add 1 index)
==

and the helper functions i made:

|%
++  every-n
  |=  [n=@ud l=(list (unit @ud))]
  =/  times-x  |=(x=@ud (mul x n))
  =/  factors  (div (dec (lent l)) n)
  (turn (gulf 2 factors) times-x)
++  clear-composites
  :: This creates like, n ^ log n copies of the list
  :: (throughout the lifetime of the program)
  :: which has got to be awful for performance, and is why
  :: "trad" sieve of era is kinda shit in pure functional prog
  :: UNLESS, the hoon compiler is smart enough to realize that
  :: the old copies are 1. the same size and 2. never used again
  :: and sneakily mutates the original list behind the scenes
  :: (in which case, this is just as fast as the normal C-style
  :: sieve of era)
  |=  [f=(list (unit @ud)) c=(list @ud)]
  ^-  (list (unit @ud))
  ?:  =(0 (lent c))
    f
  =/  null-unit  `(unit @ud)`(some 0)
  %=  $
    f  (snap f (snag 0 c) null-unit)
    c  (slag 1 c)
  ==
++  whole-sqrt
  |=  n=@ud
  (div `@ud`+:(toi:rs (sqt:rs (sun:rs n))) 2)
--

here's my sieve of era: ```hoon /+ *ari-lib |= n=@ud ^- (list @ud) =/ field ^- (list (unit @ud)) (turn (gulf 0 n) some) :: we can stop at (sqrt n) for math reasons =/ stop-point (whole-sqrt n) =/ index 2 |- ?: (gth index stop-point) =/ unwrapped (turn (slag 2 field) need) (skim unwrapped |=(n=@ud !=(n 0))) =/ indices (every-n index field) %= $ field (clear-composites field indices) index (add 1 index) == ``` and the helper functions i made: ```hoon |% ++ every-n |= [n=@ud l=(list (unit @ud))] =/ times-x |=(x=@ud (mul x n)) =/ factors (div (dec (lent l)) n) (turn (gulf 2 factors) times-x) ++ clear-composites :: This creates like, n ^ log n copies of the list :: (throughout the lifetime of the program) :: which has got to be awful for performance, and is why :: "trad" sieve of era is kinda shit in pure functional prog :: UNLESS, the hoon compiler is smart enough to realize that :: the old copies are 1. the same size and 2. never used again :: and sneakily mutates the original list behind the scenes :: (in which case, this is just as fast as the normal C-style :: sieve of era) |= [f=(list (unit @ud)) c=(list @ud)] ^- (list (unit @ud)) ?: =(0 (lent c)) f =/ null-unit `(unit @ud)`(some 0) %= $ f (snap f (snag 0 c) null-unit) c (slag 1 c) == ++ whole-sqrt |= n=@ud (div `@ud`+:(toi:rs (sqt:rs (sun:rs n))) 2) -- ```

Sign in to join this conversation.

No Label

No Milestone

No Assignees

1 Participants

Notifications

Due Date

The due date is invalid or out of range. Please use the format 'yyyy-mm-dd'.

No due date set.

Dependencies

No dependencies set.

Reference: bitchfemcel/real-eri#3