Problem 7 - GLSL

By this point, I have worked in a lot of programming languages. And, for obvious reasons, just about any programming language that I have used in my life for something, I have used in this blog to solve a Project Euler problem. However, this has not been the case for quite all languages. As I do work in the graphics lab at Williams College, naturally I have worked with GLSL, a shader language. Now, as GLSL is intended for shaders and running on the GPU, there are some issues using it for a Project Euler problem.

Perhaps the largest and most obvious issue is how to output an answer in GLSL. Shaders produce images, so clearly in order to output the answer from GLSL, I had to create an image. There are these things called 7-segment displays that display numbers pretty well, without much complicated logic, so I wrote up some GLSL to make a 7-segment display, or, to be more specific, some webGL. webGL is less featured than GLSL, including some annoying features like how in wbGL for loops must have constant bounds. The 7-segment display can be seen on shadertoy: https://www.shadertoy.com/view/4ssSz2.

Further frustrations with webGL include lack of much support for integer arithmetic (almost all of graphics is done with floating point numbers). See the hand-written modulus function and hand power-of-10 calculations for more info on this particular issue...

Then, when I had my code almost all running, I ran an issue with webGL. Remember how I said that for loops must have constant bounds? Well, the reason why is because the loops must get unfolded in the compiler. Now, unfolding a loop 150000 times...that is not the best, indeed, attempting to compile my shader crashed webGL on the machine I was using. So, because that didn't work, I may yet return to webGL to try to solve a problem, keeping in mind all the additional issues.

GLSL has smart loop bounds and doesn't need to do crazy stuff like unfold loops, so my solution below ran and gave the answer. Now, another interesting thing about using GLSL. This code is a pixel shader. What that means is that it is run once per pixel, using information about where that pixel is on screen. So though GPUs are known for being very good at parallelizing things, this problem used parallelism in the dumbest way possible, which is having every pixel compute the answer by itself, and then check if the pixel should be green or black in order to display it in a 7-segment display. Even though about 1000x more work was done than necessary, this runs in a reasonable time (maybe a couple seconds? I didn't set up anything to time it) on my machine. And here is the output, in all of its glory:

#define NUMBER_TO_PRINT esol
#define DISTANCE_BETWEEN_DIGITS 0.05
#define LINE_WIDTH 0.05
#define ON_COLOR  vec4(0.0, 1.0, 0.0, 1.0);
#define OFF_COLOR vec4(0.0, 0.0, 0.0, 1.0);

float digits(float x) {
    if (x < 2.0) { return 1.0; }
    return ceil(log(x) / log(10.0));
}

int imod(int x, int y) {
    return x - y*(x/y);
}

int euler7() {

    int numprimes = 1;
    int ans = 0;
    for (int i = 3; i < 150000; i += 2) {
        bool isprime = (imod(i, 2) != 0);
        for (int j = 3; j*j <= i; j += 2) {
            isprime = isprime && (imod(i, j) > 0);
        }
        numprimes  = numprimes + int(isprime);
        ans       += (int(numprimes == 10001) * i);
        numprimes += int(numprimes == 10001);
    }
    return ans;
}

uniform vec3 iResolution;

void main(void) {

    int esol = euler7();
    vec2 uv = gl_FragCoord.xy / iResolution.xy;
    //Below line switches between glsl and webgl coordinaes
    //uv.y = 1.0 - uv.y;

    float N = digits(float(NUMBER_TO_PRINT));
    float width = (1.0 - (N-1.0)*DISTANCE_BETWEEN_DIGITS) / N;
    float digit = floor(uv.x / (width + DISTANCE_BETWEEN_DIGITS));

    //coordinates within box
    float digitStartx = (width+DISTANCE_BETWEEN_DIGITS)*digit;
    float digitEndx   = digitStartx + width;
    vec2 sub_uv = vec2((uv.x - digitStartx) * 1.0/(digitEndx - digitStartx), (uv.y - .2) * (1.0/.6));
    //Computing a power of 10 was made harder because webgl
    //Could do something less silly in actual glsl
    int p = 1;
    for (int i = 0; i < 10; ++i) {
        p *= (1 + int(i < int(N) - int(digit)) * 9);
    }
    int currentDigit = imod(NUMBER_TO_PRINT, p) / (p/10);

    //Determining the position
    bool tiptop   = sub_uv.y < LINE_WIDTH && sub_uv.y > 0.0;
    bool top      = sub_uv.y < 0.5 - LINE_WIDTH/2.0&& sub_uv.y > 0.0;
    bool left     = sub_uv.x > 0.0                 && sub_uv.x < LINE_WIDTH;
    bool middle_x = sub_uv.x > LINE_WIDTH          && sub_uv.x < 1.0 - LINE_WIDTH;
    bool middle_y = sub_uv.y > 0.5 - LINE_WIDTH/2.0&& sub_uv.y < 0.5 + LINE_WIDTH/2.0;
    bool right    = sub_uv.x > (1.0 - LINE_WIDTH)  && sub_uv.x < 1.0;
    bool bottom   = sub_uv.y > 0.5 + LINE_WIDTH/2.0&& sub_uv.y < 1.0;
    bool botbot   = sub_uv.y > 1.0 - LINE_WIDTH    && sub_uv.y < 1.0;
    

    //shorthand

    int c = currentDigit;
    bool bit =(top && left  && (c != 1 && c != 2 && c != 3 && c != 7)) ||
              (top && right && (c != 5 && c != 6))                     ||
              (tiptop && middle_x && (c != 1 && c != 4))               ||
              (middle_x && middle_y && (c > 1 && c != 7))              ||
              (bottom && left && (c/2*2 == c) && c != 4)               ||
              (bottom && right && (c != 2))                            ||
              (botbot && middle_x && (c != 1 && c != 4 && c != 7));
    gl_FragColor = float(bit && true) * ON_COLOR + float(!(bit && true)) * OFF_COLOR;
}