I wish I still had one of the earliest programs I wrote. It would have been 1996, I was 16, and I had a linear algebra book which had an appendix entry on computer graphics. I had taken a programming class the prior quarter.<p>I got hooked writing a program to draw rotating wireframes of a few different shapes. I almost failed the class because I was so distracted by this.<p>I didn't know about arrays yet. Every vertex was its own variable with a hardcoded default. Every entry in the rotation matrices was its own variable. The code to do matrix multiplication therefore didn't have loops, just a long list of calculations. Which had to be duplicated and adapted to every vertex.<p>I did know about pointers, I had to draw to the screen after all, which was done by writing to memory starting at a known address. So at least I had loops rasterizing the lines between vertices.<p>Which means I definitely had the concept of arrays and indexing into them, I just didn't know enough to make my own.
It seems over-engineered to me. Why go through all the hustle of code generation? It can be solved with a simple “for loop”:<p><pre><code> func isOdd(n int) bool {
var odd bool
for i := 0; i < n; i++ {
odd = !odd
}
return odd
}
</code></pre>
Playground link: <a href="https://go.dev/play/p/8TIfzGrdWDF" rel="nofollow">https://go.dev/play/p/8TIfzGrdWDF</a><p>I did not profile this one yet. But my intuition, and my industry experience, tell me that this is fast.
This approach is perfect for the is-even npm package[1], with 196,023 weekly downloads, or the is-odd npm package[2], with 285,501 weekly downloads. Wouldn't it be cool if you type `npm install` and it starts downloading a 40GB is-even and a 40GB is-odd?<p>[1] <a href="https://www.npmjs.com/package/is-even" rel="nofollow">https://www.npmjs.com/package/is-even</a><p>[2] <a href="https://www.npmjs.com/package/is-odd" rel="nofollow">https://www.npmjs.com/package/is-odd</a>
why though? this is exactly what databases have been invented for! One could simply store a mapping of numbers to their classifications as 'even' or 'odd' in an SQLite database. This approach has the added benefit of not requiring program updates whenever a number's classification changes from odd to even.
The joke is completely lost on me. I don't even mean the person who did this — why not, after all. 1198 upvotes ATM is what confuses me.<p>Lookup tables for computable values are not novel, nor are they a joke. This actually is a solutions for the time/memory tradeoff, as author well knows. The problem at hand is absurd, but quite primitive, so there was absolutely no doubt this can be done. No real measurements were performed, apart from the observations that it took about 10 seconds to chew through 40GB program on his computer. So what did we learn? That exe files cannot be more than 4GB? That a program with 2^32 ifs is about 300 GB? Why 1198 people found this interesting?<p>Maybe I'm spoiled, but unlike "Hexing the technical interview" or some SIGBOVIK stuff, this doesn't seem crazy, just pointless.
This is amazing technology. You should sell it to AWS so they can offer an Enterprise-ready AWS EvenOrOdd API for everyone who does not know how to host the 40GB executable properly. With the power of the cloud this programme would be unstoppable
I'm surprised no one has chimed in on how the program is "processing" 40GB of instructions with only 800 MB/s * 10s of disk read.<p>If I had to hazard a guess, there's some kind of smart caching going on at the OS level, but that would entail the benchmark of "n close to 2^32" not being run correctly.<p>...Or that the CPU is smart enough to jump millions of instructions ahead.
I feel like the whole article is an allegory of LLM development (as a critic would write it: devoting a stupendous amount of resources and 'training data' to 'memorize' the solution). I wonder if this was the author's intent?
I’m pleasantly surprised that nobody started the discussion on whether zero is odd or even ;-)
<a href="https://en.wikipedia.org/wiki/Parity_of_zero" rel="nofollow">https://en.wikipedia.org/wiki/Parity_of_zero</a>
Jokes aside, lookup tables are a common technique to avoid costly operations. I was recently implementing one to avoid integer division. In my case I knew that the nominator and denominator were 8 bit unsigned integers, so I've replaced the division with 2 table lookups and 6 shifts and arithmetic operations [1]. The well known `libdivide` [2] does that for arbitrary 16, 32, and 64 bit integers, and it has precomputed magic numbers and lookup tables for all 16-bit integers in the same repo.<p>[1]: <a href="https://github.com/ashvardanian/StringZilla/blob/9f6ca3c6d3cbc2b9fa090bedb6fbf0d04b788279/include/stringzilla/stringzilla.h#L1679">https://github.com/ashvardanian/StringZilla/blob/9f6ca3c6d3c...</a>
[2]: <a href="https://github.com/ridiculousfish/libdivide">https://github.com/ridiculousfish/libdivide</a>
Clearly they should have optimized using binary search. Use nested if-else statements 31 deep. This would require using a more sophisticated comparison like < less than instead of equals. You'd get a similar amount of code, but it would execute on O(logN) instead of O(N). That would surely be the mark of an expert. ;-)
I'd like to see a fully distributed version. All you need is 4B hosts (IPV6 FTW) named N.domain.com (where N varies from 0 to 4B-1). The driver app sends N to the first host (0.domain.com). Each host compares the incoming N with their N.domain.com name; if they match, return the host's true/false value. If they don't match, forward the request to (N+1).domain.com and return the result.
It's kind of ironic that the python generator script uses modulo. The author could have pushed it to the point of not using one.<p>I'm tempted to write a followup doing even crazier things...
Surely any solution that claims to be performant would use a binary search, rather than looping through every number. Would be a little trickier to generate the code though.<p>Edit: /s of course
This metaprogramming reminds me of the post where they serialized data to ruby code to get around a slow XML parser: <a href="https://news.ycombinator.com/item?id=36311924">https://news.ycombinator.com/item?id=36311924</a><p>I’m curious if anyone has found a serious application for metaprogramming large amounts of data in a high level language like this?<p>So far the only application I have thought of was meta programming a series of api calls before executing them so the entire transaction can be replayed as a script.
That reminds me of my first program ever as an 11 year old. Not only did I not know about modulus, I didn't know about less than or greater than. The program picked bingo numbers. So there were 5 lines that looked something like `10 IF n=1 OR n=2 OR n=3 OR n=4 OR n=5 OR n=6 OR n=7 OR n=8 OR n=9 OR n=10 OR n=11 OR n=12 OR n=13 OR n=14 OR n=15 THEN l="B"`
At 9, I tried to make a game that combined SimCity 2000 and Transport Tycoon Deluxe - my favs at the time. I used MFC(Windows) because my parents got me a big black book about it. My game was a simple train simulator with four trains. Each train moved turn by turn to its destination from its origin. Each train had to finish its move before the next train had a chance to move.<p>I wrote it in C++ but didn't know much about managing the game's state or objects. But there was some fancy acceleration code in there.<p>You "played" the game by modifying the hardcoded x,y coordinates in the code and admiring how the trains moved on screen.<p>I thought real games used multi-threading to move each train at the same time. When I tried it, the game broke, probably because of UI updates from other threads.<p>So I never quite built my game. But this project, with all its problems, got me into software development years later.
If your programming language of choice has no arrays (like most of the languages implemented in one of the many, many, many "How to write your own interpreter/simple compiler" tutorials out there) but supports variables, then you can use this technique to kinda implement them anyway, Okasaki-style:<p><pre><code> var arr0, arr1, arr2, arr3, arr4, ..., arr65535 : int;
func get_arr(index: int): int {
if index < 0 or index > 65535 { exit(); }
if index < 32768 {
if index < 16384 {
if index < 8192 {
...
if index < 2 {
if index < 1 {
return arr0;
} else {
return arr1;
}
} else {
if index < 3 {
return arr2;
} else {
return arr3;
}
}
...
}
else {
...
}
} else {
...
}
} else {
...
}
}
proc set_arr(index: int, value: int) {
if index < 0 or index > 65535 { exit(); }
if index < 32768 {
if index < 16384 {
if index < 8192 {
...
if index < 2 {
if index < 1 {
arr0 = value;
} else {
arr1 = value;
}
} else {
if index < 3 {
arr2 = value;
} else {
arr3 = value;
}
}
...
}
else {
...
}
} else {
...
}
} else {
...
}
}
</code></pre>
It even has O(log n) access time which is actually the same complexity as accessing a RAM by a pointer anyway! Just replicate this code for any array variable you need to simulate and pre-allocate enough of the memory, it's totally free with that .bss trick anyhow.<p>So technically, languages without arrays are about as Turing-complete as those with limited-size pointers/array indices (funnily enough Brainfuck — where the pointer is invisible to the progammer — <i>actually</i> is Turing-complete).
When I was in college, I had to take an assembly language course. It was on MIPS: 32 registers.<p>One assignment said, roughly:<p>- Read ten numbers into an array.<p>- Sort the numbers into the array.<p>Nothing said I needed to read the array, so I read in the numbers, both to the array and registers, hardcoded a bubble sort on the registers, and wrote the result to the array. End of program.<p>I was being cute. I got full marks with a note to stop being cute.
That work is amazing!<p>Now before you laugh at the original meme and the use of AI chosing the wrong algorithm, read this:<p><a href="https://fosstodon.org/@gabrielesvelto/110592904713090347" rel="nofollow">https://fosstodon.org/@gabrielesvelto/110592904713090347</a><p>There is no proof AI was used, but:<p>> Google's code was allocating 20000 variables in a single frame.
Weirdest bit is this, I think.<p>> After all, IPv4 is still standing stronger than ever, 60 years after it was deemed deprecated due to so called “address exhaustion”.<p>IPv4: deprecated in 1963, 19 years before it was introduced.
> for the large number close to the 2^32 limit the result is still returned in around 10 seconds.<p>This could be improved by arranging the if/else statements in a binary tree.
From the article:<p>“Now, in a world where AI is replacing programmers by the minute, taking their jobs and revolutionizing the way we think about code, maybe we should…”<p>Excuse me ?!?<p>I get that job loss due to AI is a common fear. But is there any hard evidence that the job market is losing “a software engineering job a minute” to AI? That’s 525600 jobs annually…
I'm mildly surprised that the compiler seems to compile the code so literally so that the binary blows up like that with a linear runtime as well. I would've guessed that for such a straight-line execution on one of the simplest mathematical operations to yield a boolean, a modern highly-optimizing compiler would've done <i>something</i> with it.<p>What would it take to make the compiler optimize this code meaningfully?
First program I ever wrote was to bypass an anti-afk program in a game: it needed to click on a button which was x vs y pixels, and would appear on random positions on the screen every time. I manually inserted one line for each viable position using x-1 and y-1. In v2 I implemented a for loop which made the script go from tens of pages to not even a single full one - computer magic! (EasyUO language)
That looks like a program developed with TDD that has gone on too long without refactoring.<p>The author probably has a billion individual tests that will all lose their value if it were to be simplified, since they would no longer correspond to special cases in the code.
As a kid I heard that circuits like adders were made from boolean algebra AND, OR and NOT gates.<p>I played around on a big paper pad, and finally got a 4 bit adder implementation.<p>But since my unit circuit was [A,B]->[S], instead of the canonical [A,B,carry-in]->[S,carry-out], I had to add a second layer of units to propagate the first carry onward. And a third layer of units in case that also generated a carry. Etc.<p>So my circuit had gate of order N^2/2 and depth order of 2*N instead of gate and depth orders of N.
I was hoping that this would be about someone finally building an LLM out of a decision tree or decision tree derived technique (which ultimately boils down to nested if statements). Not sure why no one has tried it yet.
> In fact, the above code is a perfect example of a time-memory tradeoff<p>Not as much since the program will take increasingly more time to run as the input number gets higher. Checking if a 'small' number is even or odd will be pretty fast. Checking a 'large' number will be slow since it will go through all 'IFs' until it reaches the result.<p>It's like O(M/2) average time complexity where 'M' is a constant, the program memory size (number of 'IFs' stored).
Not to compete with your brilliant code on optimization, bu I have also written a swap routine that excels especially on numbers close to each other. I know sign function result can be put into a variable, but computers nowadays are so fast...<p>Anyone feel free to use it.<p>static void swap(ref int a, ref int b)
{
int c = (b - a) ;
while (c != 0)
{
a += Math.Sign(c);
b -= Math.Sign(c);
c -= Math.Sign(c);
}
}
The whole article looks like a misunderstanding to me. The author writes about a trade-off between memory and processor, although in his example both memory (on disk and in RAM) and processor are wasted (executing all IF instructions in turn).<p>It is also strange that the author is trying to generate code in assembly language, which he does not know very well, because there is a DIV/IDIV instruction.
I gave similar a shot in rust, using build.rs to dynamically create the file, inspired by the blog post. I'd been meaning to look at build.rs for a while.<p>It seems to hit a pretty pathological compilation situation. Done as ifs, rust ran out of stack. Done as "match" it has been compiling for about 24 hours.
Interesting. How would this compare to making a while loop or recursive function, I wonder?<p>And, what about switch statements? In theory it is said they should be faster, but I am not sure that's necessarily the case.<p>Another option would be to keep a database with the numbers indexed, and then compare with performing a database query.
When I was young I tried to make my own alarm clock.<p>My masterplan was to print the time to the display (starting from 8 AM), wait a second and print the next value. All manually, obviously.<p>I remember eventually giving up because it was getting too boring. I think I discovered about loops a year after the event.<p>Great times :)
In the blog post "Branch predictor: How many "if"s are too many?", I started with the same premise, but focused on branch predictor :P<p><a href="https://blog.cloudflare.com/branch-predictor" rel="nofollow">https://blog.cloudflare.com/branch-predictor</a>
"Since I'm a great believer in performant code I decided to implement this in the C programming language as it's by far the fastest language on the planet to this day (thanks to the visionary genius Dennis Richie)."<p>Fastest portable language. Assembler is faster.
So I honestly thought that this was going to be another LLM article, but using the venerable ReLU activation function instead of the usual. A ReLU is exactly an if statement when rendered in a decision tree (if less than 0, emit 0; otherwise, emit the input). Given the relative popularity of the 4B parameter models (any transformer is dominated by the number of parameters in good old fully-connected feedforward layers), you can perhaps describe such models as 4B if statements. I was disappointed that the author didn’t go there as a means of parody.
I'm afraid I take issue with the phrase "amazingly performant". I would struggle to come up with another way of determining whether a number near 2^32 is even that takes anything like 10 seconds
What was really hurting me was all the literal strings "even" and "odd." I would have made them into constants. I guess then the next step would be to use constants for all the numbers.
Reminds me of that guy who scrolled to the end of Excel: <a href="https://youtu.be/sF8k3zl70os" rel="nofollow">https://youtu.be/sF8k3zl70os</a>
> we need more if statements!<p>Waiting for the Will Ferrel skit of this. Though this article was funny enough on its own. The Python program to generate the C code was hilarious.
Come on, we live in 2023 and we can achieve better performance. It should be parallelized with checks evenly distributed between GPU cores. Unless you think that efforts by NVIDIA and AMD should be wasted.
Seems like a poorly chosen example, since you could simply "lookup" the last bit of the integer to see if it is even or odd, which should be instant for any integer?
Although not quite as spectacular as that, here is some funny codegen in POSIX shell I wrote; `sh` doesn't have a `repeat` command, so I wrote a script to implement it without forcing any loops at all. Along the way I uncovered some interesting segfaults for most sh implementations (including, sadly, dash), which is the reason for the somewhat convoluted code. Have fun!<p><pre><code> #!/bin/sh
#
# Usage: repeat TIMES COMMAND
# Repeat COMMAND a given number of TIMES.
eval_full_quotes='
s/\\/\\\\/g ; s/\"/\\\"/g ; s/</\\</g ; s/>/\\>/g ;
s/\$/\\\$/g ; s/\[/\\\[/g ; s/*/\\*/g ; s/?/\\?/g ;
s/|/\\|/g ; s/&/\\&/g ; s/~/\\~/g ; s/=/\\=/g ;
s/;/\\;/g ; s/ /\\ /g ; s/%/\\%/g ; s/`/\\`/g ;
s/(/\\(/g ; s/)/\\)/g ; s/{/\\{/g ; s/}/\\}/g ;
s/#/\\#/g ; s/'"'"'/\\'"'"'/g'
errorx() { printf 'Error: %s\n' "${*:-"unknown error."}" >&2; exit 1; }
_rep() {
rep_times="$((2 * $1))"
rep_string="$2"
output=""
while [ 0 -lt "${rep_times}" ]; do
test 1 -eq "$(((rep_times /= 2) % 2))" && output="${output}${rep_string}"
rep_string="${rep_string}${rep_string}"
done
printf '%s' "${output}"
}
{
times="$1"
shift
test 0 -lt "${times}" || errorx "First argument must be a positive integer."
test 0 -lt "$#" || errorx "No command given to repeat."
repeat_command="$*"
command_length="${#repeat_command}"
max_arg="${ARG_MAX:-"$(getconf ARG_MAX)"}"
if [ "${max_arg}" -le "$((times * (command_length + 2)))" ]; then
: "$(( block_size = max_arg / (20 * (command_length + 2)) ))"
: "$(( blocks = times / block_size + 1 ))"
: "$(( remainder = (block_size + (times % block_size)) % block_size ))"
eval_string="$(_rep "${block_size}" "${repeat_command}; " | sed -e "${eval_full_quotes}")"
while [ 0 -lt "$((blocks -= 1))" ]; do
eval eval "${eval_string}"
done
eval_string="$(_rep "${remainder}" "${repeat_command}; " | sed -e "${eval_full_quotes}")"
eval eval "${eval_string}"
else
eval_string="$(_rep "${times}" "${repeat_command}; " | sed -e "${eval_full_quotes}")"
eval eval "${eval_string}"
fi
}
exit</code></pre>
> Now, in a world where AI is replacing programmers by the minute, taking their jobs and revolutionizing the way we think about code<p>I’m dumb. This is a joke right? At most I can say AI has revolutionized how I interface with documentation.
> Running this gives us a nice 40 GB file which contains all 4.2 billion comparisons needed to determine if any 32 bit number is even or odd!<p>For some reason I am thinking of npm now ...
Why do people always got skill issue and can't learn to use proper modulo arithmetic? It seems like those "TikTok idiots" always get the limelight over this kind of silly thing
Here is a version with 0 if statements<p><pre><code> #include <stdio.h>
#include <stdlib.h>
int main(int argc, char** argv) {
return printf(atoi(argv[1]) & 1 ? "odd" : "even") < 0;
}</code></pre>
> Considering the computer has to read 40 GB of data from disk, map it to physical memory and then let the CPU has a rip of it<p>No it doesn't? Maybe it needs to set up page tables for 40GB, but it doesn't need to read the parts you're not using into memory, that's part of the point of memory-mapping like this - it sets up a page fault handler to load the page into memory when accessed, rather than needing to do it all up-front.