Computing primes with CSS | Hacker News Reader

Computing primes with CSS

nedbatchelder.com

111 pointsingve60 comments

This is way cooler: http://silon.slaks.net

is it, though?

https://github.com/SLaks/Silon#implementation-details

"Silon is implemented using LESS to generate CSS selectors for every combination of inputs that will turn each gate on. In effect, I created a LESS-based DSL that expresses (almost-)arbitrary boolean expressions."

Yes, I know a preprocessor is involved, much like many single-element/background-image hacks and CSS-only glitch effects which translate to fifty-keyframe animations.

It's still cooler than the OP.

it's definitely shinier than the OP, but I personally think encoding a sieve of Eratosthenes in a CSS selector is cooler than encoding truth tables in a CSS selector

I was always more interested in the philosophy of mathematics than prime numbers.

Actually, I'm interested in philosophy in general, especially early Wittgenstein & Gödel.

So I'm biased.

Yes, it is. Almost-arbitrary boolean expressions vs. completely straightforward and obvious use of a CSS selector.

That's not just cool, that's crazy!

wait, what?!

"Your scientists were so preoccupied with whether they could that they didn't stop to think if they should."

--Dr. Ian Malcolm (Jurassic Park)

We have clearly passed the point where we should stop, but let's keep going and see what happens.

-- Scientist from Jurassic Park

He already knows very well that he "shouldn't have". The point is he did it anyway.

Nature finds a way.

You can do the same thing with pure HTML, just write `2,3,5,7,11,13...`. I am disappointed by the article, was expecting something with CSS `calc()`.

That's not similar, at all. This is actually removing multiples, as in the sieve of erastosthenes.

It's missing a loop, and the primes are hardcoded into the source code (see the similarity?). You might be mislead by the fact that you also find 'span:nth-child(4n+8)' or 'span:nth-child(6n+12)' (which aren't primes) but those are redundant, and an efficient sieve would skip non primes.

Yes, they are redundant, but there's still no special knowledge of the primes in the file.

The primes are hardcoded into the source the same way that the primes are hardcoded into the sequence of natural numbers. They're there, but the important bit is finding them.

The point is that the file has nothing about the primes in it. 6 and 7 are treated equally, but 7 is displayed and 6 is not.

The file has the first sqrt(1000) primes hardcoded in it.

If you wanted to find the first 100.000 prime numbers, you'd need to add all the prime numbers up to 313 in the css file.

You should look more closely: it doesn't. The CSS selectors are for 2, 3, 4, 5, 6, 7, 8, 9, ..., 32. The most you can say is that it has sqrt(1000) == 32 hardcoded into it, but there are no primes.

Ok, I get it. However, you still need to modify the source code to accomodate for larger inputs.

True dat.

I made a slightly improved version using <ol> and <li> elements to not have to manually output the numbers within the <span> element: https://jsfiddle.net/r8c2Lsz7/

Nice! :)

How does the size of the code increase with the number of primes shown?

Imho, the code should not grow. So in my view, the article is cheating.

Code size increases in Θ(n^(0.5))

I agree that the title is somewhat misleading - it is (to me) as much a 'computation of prime numbers' as a lookup table would be.

FWIW, this[1] is closer to how a "real" sieve of Eratosthenes program might look like, with three optimizations: 1) omitting even numbers from the sieve, 2) sieving starting at n^2, 3) precomputing primes up to sqrt(n) if you want to sieve up to n. The code size then is Θ(sqrt(pi(n)).

[1] https://jsfiddle.net/L8mxuag5/1/

Well it's closer to O((n/log(n))^0.5), although that doesn't make much of a difference until n becomes rather large.

Good catch - I didn't differentiation between n as 'upper limit for primes' and n as 'input length'. The former is more intuitive, which makes your solution more accurate. (Also, I should have played it safe and use O instead of Θ...)

Wouldn't a bit of js to create them on the fly stop that? It would still be a kind of lookup table though.

I think using JavaScript would move the concept even further away from "computing primes with CSS".

It would just do some things on the fly that the author did with python.

I don't understand why the commenters in this thread are being so negative towards this project. This is a fun experiment to see what the author could do with the minimal tools CSS provides. Sure there's no use for this kind of project. Not everything has to have a use. Some things can be for pure fun. The negativity in this thread isn't even productive or helpful.

I don't feel really negatively towards this project, but after reading the title and looking at the code it felt a bit disappointing. When I read "computing primes" I didn't expect so much pre-computation cooked into the code.

It's what you might call a "halfway algorithm" -- yes it needs some major fudging baked in (because from what I understand you can't do things iteratively in CSS). But it does, intrinsically, compute the primes. And the point is it demonstrates a kind of computation one normally wouldn't think was even possible with CSS (that is: not that you'd rule it out as beyond the computational reach of CSS; but it's definitely the sort of computation you normally wouldn't think to do with CSS).

So I'd say it's definitely a valid hack.

I don't disagree, because I have a similar feeling. But I recognize that it comes from a bit of a 'No True Scotsman' in regard to computation.

By which I mean that looking up values in a table is actually a part of computation. That's pretty much how anything with a trigonometric function works [we've just replaced books with integrated circuits]. Back in the days of using a slide rule, there was a looking it up in a table element as well, it's just that the table was in a flexible form.

Practically, speaking if the easiest way to calculate the first fifty million primes might be: https://primes.utm.edu/lists/small/millions/

Philosophically, I don't have the same feeling querying for some nth prime at https://primes.utm.edu/nthprime/index.php but it's probably doing all its calculations for mundane things like network packets and none of it sieving natural numbers.

I see your point, and I think we share a point of view.

But when using lookup tables, I consider the computation of the lookup table a part of the algorithm - after all, a lookup table is essentially an optimization: You extract a sub-computation and store it, paying with space for better time complexity.

Philosophically, I don't think that feeling intellectually satisfying is a marker of correct understanding. I mean I don't think there's anything out in independent reality that makes an procedure that implements the sieve of Eratosthenes better than a procedure that uses lookup tables.

1. The only thing that matters about a function 'nth-prime' is that it maps 1->2, 2->3, 3->5 etc.

2. To be useful in practical applications, a function `is-prime` is unlikely to use the sieve of Eratosthenes and more likely to use something like Fermat's Primality Test [1] and hence will be mistaken over Carmichael Numbers and so hard coding the first few into the function via looking might be a good way to do what people expect...though at some point:

Numbers that fool the Fermat test are called Carmichael numbers, and little is known about them other than that they are extremely rare. There are 255 Carmichael numbers below 100,000,000. The smallest few are 561, 1105, 1729, 2465, 2821, and 6601. In testing primality of very large numbers chosen at random, the chance of stumbling upon a value that fools the Fermat test is less than the chance that cosmic radiation will cause the computer to make an error in carrying out a “correct” algorithm. Considering an algorithm to be inadequate for the first reason but not for the second illustrates the difference between mathematics and engineering. Abelson, Sussman, Sussman https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.htm...

[1]: https://en.wikipedia.org/wiki/Fermat_primality_test

What pre-computation do you see there? There are the numbers 1-999, and the numbers 2-32.

I see an iteration of every possible factor for the numbers given. Continuing from 999 further on to 1400, the code doesn't work anymore (It claims 1369 to be prime).

So, to be precise, the code does not compute 'primes', the code lists every number that is not devisable by any number from 2 to 32.

There is a precomputation that 32 is the (rough) square root of 1000. There is no precomputation of primes. It is true that the code will not work beyond 1000, unless you also add more selectors.

I can't speak for the others but I'm very wary of "too powerful" languages and language features. They lead naturally to technical debt and security vulnerabilities.

This sort of explains how I feel: http://lukeplant.me.uk/blog/posts/less-powerful-languages/

That's why my reactionary instinct to "neat hacks" like this is usually one of revulsion (at the language for making it possible).

But it’s a completely straightforward use of :nth-child, so not really that fun or deep of an experiment (yes, just an opinion). I was hoping for something at least as interesting as prime-testing backreferences /^(..+)\1+$/.

The negativity probably comes from the fact that people expect to find high quality content on the HN front page. Pet projects like these are not impressive enough to be featured.

Says you.

I once saw an interesting way of computing primes using LaTeX [0].

The link also mentions a way of doing the same in plain TeX that is taken from Donald Knuth's "The TeXbook".

[0] http://tex.stackexchange.com/questions/134305/how-to-produce...

Well, TeX is supposed to be able to do that, which makes it less cool.

That's because CSS is turing complete. The rule 110 cellular automaton has been implemented in CSS, and because the rule 110 is turing complete, that means CSS is turing complete.

What’s “because” CSS is Turing complete? Anyway, this implementation could be done using a DFA (because it’s not actually computing primes with CSS).

You could replace the "+4" in "2n+4" with "+0" to remove the amount of custom text you have to insert into each line.

No, the point is to display the primes (2, 3, 5, 7...).

but then 2 would be hidden, and 2 is prime.

You can remove all non primes in the selector, like below

span:nth-child(2n+4), span:nth-child(3n+6), span:nth-child(5n+10), span:nth-child(7n+14), span:nth-child(11n+22), span:nth-child(13n+26), span:nth-child(17n+34), span:nth-child(19n+38), span:nth-child(23n+46), span:nth-child(29n+58), span:nth-child(31n+62),

But that'd be cheating. How do you know what the primes are before you've computed them?

Unrelated to the main story, those damnable f-strings are awful. For goodness' sake, don't put code into your format strings, you maniacs!

But don't take my word for it: http://www.stringtemplate.org/about.html

Anything can be overused. Do you find my use of them "awful"? It will mean we don't need code like: "...".format(a=a, b=b, c=c, d=d)

No, I will admit your usage here seems perfectly cromulent. ;-)

(Don't pay too much attention to me: I still haven't adopted the .format() method! Heh.)

Very nice project sir!

Your use there is exactly what it was designed for. I've enjoyed your work over the years, so I'm quite happy you found it useful.

But would that be... as stylish?

     #####
    #### _\_  ________
    ##=-[.].]| \      \
    #(    _\ |  |------|
     #   __| |  ||||||||
      \  _/  |  ||||||||
   .--'--'-. |  | ____ |
  / __      `|__|[o__o]|

_(____nm_______ /____\____

We detached this comment from https://news.ycombinator.com/item?id=12611579 and marked it off-topic.

Reply on news.ycombinator.com