13
\$\begingroup\$

I'm trying to learn the golfing language Vyxal because I occasionally contribute to it, and I'm slightly ashamed I can't even use it. To do this, I started with implementing the Sieve of Eratosthenes in Vyxal. I'd like to know how to make this code more readable and idiomatic, and, if there are issues with time or memory, more efficient.

Please note that I am not looking for tips on golfing it. If there's a way to make it clearer by making it shorter, that's fine, but making it terser is not the goal here, just making it more readable.

3$ṡ→sieve ⟨2⟩→primes 2→x {←sieve L0> | ←sieve'←x%;: h:→x ←primes$J→primes 1ȯ→sieve} ←primes

Try it Online!

An integer (> 2) is given as input. An inclusive range from 3 to that integer is made and stored in the variable sieve. Then, the variable primes, which will be returned at the end, is initialized as the list [2], and the current prime number to filter out composite numbers with, x, is set to 2.

While sieve is non-empty, a list of numbers in sieve that aren't divisible by x is constructed. Then, the head of that list is assigned to x and appended to primes, and the rest is assigned to sieve. I'm unsatisfied with h:→x ←primes$J→primes because should've worked to split the list in two but is buggy, and I can't find a nicer alternative. Also ←primes$J→primes is like saying primes = primes + [x] instead of simply saying primes.append(x) (in Python), but I can't find an alternative to that either.

Might I also be overusing variables?

Thanks for your feedback.

\$\endgroup\$
1
8
\$\begingroup\$

It is probably more efficient to work with a boolean array (which is the idea behind the sieve anyway - a boolean mask that you build up to filter out all of the non-primes in the range). Instead of a sieve and a primes variable, we just have a single isprime array which we modify as we go along. There are two advantages to this. Firstly, it is easier to understand. Secondly, it is actually more memory-efficient because we only need to alter one list and can actually keep it on the stack, meaning we don't need to assign it to a variable, and so we can modify the list in-place.

We can initialize the array like so: ⟨0 | 0⟩ 1 ←input ‹ ẋ f J (prepend [0, 0] to a list of input - 1 1s), which initially just says that \$0\$ and \$1\$ are not prime. So far so good.

Then, we want to start our loop at \$2\$ since that's the lowest prime, and we want to end it at the square root of the input, since that's the maximum value you need to scan when doing sieve. If you insert a :, after the ←sieve in the body of your while loop, you'll notice that you don't stop here, so you waste \$O(n)\$ steps just looping through the remaining primes and dequeueing the list repeatedly.

To do this, we can just do ←input √ ⌈ 2$ ṡ (x| - square root the input, ceiling (although I think floor works too? using ceiling just to be safe), and produce a range from 2. Note that you could also just do the for loop directly since 0 and 1 will be skipped by the following condition anyway. We then do a for loop, saving our current value as x.

We first want to duplicate the current top-of-stack, which is the prime array, because we will be popping it to check if x is prime. So, we do : followed by ←x i [ - get isprime[x] and if it's prime, run the next block.

Then, we just want to mark 2x, 3x, 4x, ... as composite. So, we floor divide the input by x, take the exclusive range, increment it (to get 2, 3, ..., input/x), and then multiply each one by x: ←input ←x ḭ ɽ › ←x *. Finally, we set isprime[n] to 0 for each one: (n 0 Ȧ).

At the end, this will produce a boolean array, so we simply use the "truthy indices" element to get the list of prime numbers: T.

Here is the final program, which should be approximately optimal time complexity, but may still have some constant optimizations possible:

→input
⟨0 | 0⟩ 1 ←input ‹ ẋ f J
←input √ ⌈ 2$ ṡ (x|
    : ←x i [
        ←input ←x ḭ ɽ › ←x * (n 0 Ȧ)
    ]
)
T

This is (mostly) equivalent pseudocode:

save input to `input`
[0, 0] -join- flatten(1 repeated (`input` - 1) times)
for each `x` in 2..ceil(sqrt(`input`))
    dup
    if `isprime`[`x`]
        for n in x * 2..floor(`input` ÷ `x`)
            `isprime`[n] = false
get truthy indices of `isprime`
\$\endgroup\$
4
  • \$\begingroup\$ Thanks! I'll need some time to process this, because Vyxal is very much a read-only language for me (don't tell lyxal I said that :P). I don't know if flooring the square root would for 3, since that'd give a range from 1 to 2, and 3's divisible by 1. \$\endgroup\$
    – user
    Aug 6 at 21:47
  • \$\begingroup\$ @user but since 1 is not a prime (and the isprime list is initialized as such) it would get skipped \$\endgroup\$ Aug 6 at 21:53
  • \$\begingroup\$ @user I've added some roughly equivalent pseudocode - hopefully this is a bit more digestable \$\endgroup\$ Aug 6 at 21:57
  • 3
    \$\begingroup\$ Ah, thanks! Vyxal is already pretty easy to digest, what with it being gluten free, but this tree nut-free code is even better :P \$\endgroup\$
    – user
    Aug 6 at 21:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.