zig

Zig unable to evaluate comptime expression


I'm trying to learn Zig using the website https://exercism.org/. I was solving this exercise, which requires us to find the nth prime number.

My idea was to generate all of them during comptime and return as required; this is my current my code:

const std = @import("std");
const mem = std.mem;

const buffer_size = 100000;

fn sieve(comptime buffer: []usize, comptime limit: usize) []usize {
    if (limit < 2)
        return buffer[0..0];
    const sqrt_limit = std.math.sqrt(limit);
    var bitset = std.StaticBitSet(limit + 1).initFull();
    var n: usize = 3;
    var i: usize = 1;
    
    
    buffer[0] = 2;
    while(n <= sqrt_limit): (n += 2) {
        if (!bitset.isSet(n))
            continue;

        buffer[i] = n;
        i += 1;
        var j = 2 * n;
        while (j <= limit): (j += i) {
            bitset.unset(j);
        }
    }
    while (n <= limit) : (n += 2) {
        if (!bitset.isSet(i))
            continue;

        buffer[i] = n;
        i += 1;
    }
    return buffer[0..i];
}


var primes_buffer: [buffer_size]usize = undefined;
const primes = sieve(&primes_buffer, buffer_size);

pub fn prime(allocator: mem.Allocator, number: usize) !usize {
    _ = allocator;
    return primes[number-1];
}

But when I try to compile this, I'm getting the following error:

nth_prime.zig:15:15: error: unable to evaluate comptime expression
nth_prime.zig:15:11: note: operation is runtime due to this operand
nth_prime.zig:39:21: note: called from here

Why am I not able to populate my array at comptime, and why is this line problematic?

buffer[0] = 2;

Solution

  • I think its because the buffer primes_buffer is actually a runtime value, so you can't get it to work in that way. One way to write it would be like:

    const primes = blk: {
        const buffer_size = 1000;
        @setEvalBranchQuota(buffer_size * buffer_size);
        var primes_buffer: [buffer_size]usize = undefined;
        const len = sieve(&primes_buffer, buffer_size);
        break :blk .{ primes_buffer, len };
    };
    
    fn sieve(comptime buffer: []usize, comptime limit: usize) usize {
        if (limit < 2)
            return buffer[0..0];
        const sqrt_limit = std.math.sqrt(limit);
        var bitset = std.StaticBitSet(limit + 1).initFull();
        var n: usize = 3;
        var i: usize = 1;
    
        buffer[0] = 2;
        while (n <= sqrt_limit) : (n += 2) {
            if (!bitset.isSet(n))
                continue;
    
            buffer[i] = n;
            i += 1;
            var j = 2 * n;
            while (j <= limit) : (j += n) { // should increment j by n
                bitset.unset(j);
            }
        }
        while (n <= limit) : (n += 2) {
            if (!bitset.isSet(i))
                continue;
    
            buffer[i] = n;
            i += 1;
        }
        return i;
    }
    
    pub fn prime(allocator: mem.Allocator, number: usize) !usize {
        _ = allocator;
        if (number >= primes[1]) {
            @panic("no"); // or return an error
        }
        return primes[0][number];
    }
    

    This way, the scope we defined as blk will run and evaluate in comptime.