The best way to save space is to use a Bloom Filter.
If we capture all the even numbers, that would sadly only give us "Definitely not Even" or "Maybe Even".
But for just the cost of doubling our space, we can use two Bloom filters!
So we can construct one bloom filter capturing even numbers, and another bloom filter capturing odd numbers.
Now we have "Definitely not Even" and "Maybe Even" but also "Definitely not Odd" and "Maybe Odd".
In this manner, we can use the "evens" filter to find the odd numbers and the "odds" filter to find the even numbers.
Having done this, we'll be left with just a handful of unlucky numbers that are recorded as both "Maybe even" and "Maybe odd". These will surely be few enough in number that we can special case these in our if/else block.
The filters as a first-pass will save gigabytes of memory!
We can optimize the hash function to make it more space efficient.
Instead of using remainders to locate filter positions, we can use a mersenne prime number mask (like say 31), but in this case I have a feeling the best hash function to use would be to mask with (2^1)-1.
https://gist.github.com/alexjurkiewicz/1abf05f16fd98aabf380c...
It's a joke post with some interesting bits and details.
It is hard to imagine better efficiency than O(1)!
Indeed we could improve it further by performing all evaluations even when we find the answer earlier, ensuring it is a true Constant Time algorithm, safe for use in cryptography.
And with a little extra work you can shrink the whole table's size in memory by a factor of eight, but I'll leave that as an exercise for the interested reader.
Optimization efforts included increasing the internal buffer size of the StreamWriter used to create the source code: this reduced the runtime to around 6 minutes, as well as running a non-debug build, as it was observed that the poor Visual Studio metrics gathering process was contributing significantly to disk activity as well, but that ultimately didn't matter much. So, ehhm, yes, good job on that I guess?
And if you then make the ranges tree-shaped you get logarithmic complexity, which massively cuts down the O(n) of the rather naive chained `if` statements.
I haven't found any authoritative source, but I strongly suspect that the .NET bytecode format has 32-bit limits all over the place. Maaaybe you could break up the code into functions less than 1 GB in size and then chain them together.
[1]: https://aphyr.com/posts/342-typing-the-technical-interview
[2]: https://www.richard-towers.com/2023/03/11/typescripting-the-...
> “Can I use any language?” > > “Sure.” > > Move quickly, before he realizes his mistake.
So if you're concerned with privacy issues, you can run the assembly version proposed in the article locally and be well within the same order of performance.
Let's thank the author of the article for providing a decent alternative to Google.
ah, but the license is not that good we can't reproduce his code.
I think I just experienced a segfault
Did you want to test the LLM's grammatical comprehension?
Wow he really lucked out... On his way to perfecting a fully functioning and performant Even/Odd Detector, he stumbled upon a fully functioning and performant Coin Flip Simulator!
I started designing my modules, a ROM, a register with a ROM pointer, etc, etc, writing the Verilog and working out the clock sync between modules. Then I got 'lazy' and wrote a trie tree like implementation in Java, and have it spit out the whole tree in Verilog. It worked and just one clock cycle after the last letter my number would output. Fastest in the class! Also the most number of gates in the class. Surprised I got a 90 grade given I didn't use any of the advanced ASIC design the class taught. The TA didn't know what the hell they were looking at.
It's a common pitfall for those learning hardware description languages like Verilog, when they think about them like programming languages. If you go "if (calc) res <= a * b;" If res is 32 bits wide then you have instantiated a 32 bit fast multiplier circuit dedicated just to that one operation. This is often not what was intended.
Despite how leaning on the analogy too closely can mislead in that way, the analogy between hardware and software is not a shallow one. A combinatorial circuit is akin to the pure function of functional programming. Anything that can be described as a pure function working on fixed integers or floating point or other discrete data types, can be transformed into a combinatorial circuit. And there are algorithms to do so automatically and often with reasonable efficiency.
Free software synthesis has come a long way in recent years, by the way. There's even several hobbyist projects that can take VHDL or Verilog and produce layouts using TTL chips or even discrete transistor logic with automatic circuit board layout. You can now compile your code directly to circuit board copper masks and a part list.
Or even simpler: If it's 0, return "even". If not, do a recursive call to n-1, if that equals "even", return "odd", otherwise return "even".
But the best way is probably to just use a library. Yes, 500MB of additional dependencies, but then it's a one-liner.
for i in range(2*8):
if i % 2 == 0:
for i in range(0, 2**8, 2):
print(" if (number == "+str(i)+")")
print(" printf(\"even\\n\");")
print(" if (number == "+str(i + 1)+")")
print(" printf(\"odd\\n\");")
for i in range(0, 2**8, 2):
print(f""" if (number == {i})
puts("even");
if (number == {i + 1})
puts("odd");""") even, odd = "even", "odd"
for i in range(2\*32):
print(f' if (number == {i}) puts("{even}");')
even, odd = odd, even
// Check whether a number is odd or even.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
static bool is_odd_or_even(unsigned long num) {
return true;
}
int main(int argc, char **argv) {
const unsigned long num = strtoul(argv[1], NULL, 10);
printf("%lu is %s odd or even\n",
num,
is_odd_or_even(num) ? "is" : "is not");
}I was gonna comment “this is what I really like to see on HN”. Then I saw the date and was sad that we’re having to dip into the history box to find fun/interesting articles more often of late it seems.
Anyone else interested in a temporary moratorium on all things LLM? We could have GPT-free-Wednesday, or something like that :)
I would be interested in a permanent moratorium, personally. There's no interesting content to be had in the various LLM articles that litter HN these days. Or failing a topic ban, at least give a way to filter it for those of us who are sick of hearing about AI hype.
We don’t _have_ to. You could start a blog and display the indomitable human spirit.
return odd_or_evenness[n];
const odd_or_evenness = comptime blk: {
var buf: [16]bool = undefined;
var is_even = false;
for (&buf) |*b| {
b.* = is_even;
is_even = !is_even;
}
break :blk buf;
};
/* Copyright 2023. All unauthorized distribution of this source code
will be persecuted to the fullest extent of the law*/
#include <stdio.h>
#include <stdint.h>
#include <string.h>
int main(int argc, char* argv[])
{
uint8_t number = argc>1 ? argv[1][strlen(argv[1])-1]-'0' : printf("Usage: odd-or-even number\n");
if (number == 0)
printf("even\n");
if (number == 1)
printf("odd\n");
if (number == 2)
printf("even\n");
if (number == 3)
printf("odd\n");
if (number == 4)
printf("even\n");
if (number == 5)
printf("odd\n");
if (number == 6)
printf("even\n");
if (number == 7)
printf("odd\n");
if (number == 8)
printf("even\n");
if (number == 9)
printf("odd\n");
if (number == 10)
printf("even\n");
}
Or is the performance considered worse because it becomes O(n) (where n < MAX_UINT) vs. constant time ( O(MAX_UINT) )
switch (v) {
case: 0,2,4,8,…:
return EVEN;
case: 1,3,5,7,…:
return ODD;
default:
return IDK;
}
processing the whole number is absurd
You know, to save the performance cost of processing the input as a string, and chomping off all but the last character.
All you need is the final binary digit, which incidentally is the most optimal codegen, `v & 1`.
https://news.ycombinator.com/item?id=38790597
4B If Statements (469 comments)
Thanks for making me doubt myself & googling who that guy who made python was again, because surely "van der Gussom" isn't a normal Dutch name. Well played.
Amazing!
Save space.
def even_flip_flop(number):
even = True
for _ in range(number):
even = not even
return even
def even_recursive(number):
return True if number == 0 else not even_recursive(number - 1)
table = [True, False] * 1000 # adjust to your needs
def even_lookup(number):
return table[number]isEven is a performant, hand-compiled evenness checker for any 32 bit integer. A single file import that does one job and one job only!
"Is it odd or Even?"
"YES"
There was a function to detect a key press which would return a number identifying the pressed key.
I needed to map that number to the letter printed on the key to print it on the screen. I don't remember whether there was no hashmap data structure or I just didn't know about it, but I implemented it with a serie of if.
The problem with that solution is that while mapping A was fast, Z was very slow because it was at the end of the list. That is how I discovered divide and conquer/ dichotomy with if branches.
I tracked it down to a folder with thousands of C++ files called things like uint_to_int.cc and inch_to_cm.cc and cm_to_m.cc. Basically the developer in charge of writing the conversion library took our typed units library and autogenerated a C++ file for every possible conversion the application might need to make.
Every time we added a new typed unit it would create another couple of dozen files to be compiled.
> Lets compile the code, disabling optimizations with /Od to make sure that the pesky compiler doesn’t interfere with our algorithm
I'm in too deep now, so I'll let it run while I'm at work.
And that weird flag is because it's a windows compiler: cl.exe, not gcc.
File.write("check.rb", (["if i == 0\n puts :even"] + (1..1_000_000).map { |i| "elsif i == #{i}\n puts :#{i % 2 == 0 ? "even" : "odd"}" } + ["end\n"]).join("\n"))
i = ARGV.first.to_i
fish: Job 1, 'ruby check.rb 0' terminated by signal SIGILL (Illegal instruction)Am I lost? Aren't the compiler/linker responsible for fast code, not the language itself?
Most of the difference in speed is the optimizer/linker. Assuming a fair competition the difference between Ada, C, C++, D, Fortran, Rust, Zig (and many others I can't think of) is very rarely even 1% in any real world situation. Of course it isn't hard add pessimization to make any language lose, sometimes accidentally, so fair competitions are very hard to find/make.
Then again, the article was clearly sarcastic.
given the article, it's fair to assume the author was joking around
that being said, the way the language is used and its ecosystem do contribute to the executable's efficiency. yet, given C's frugality, or the proximity between its instructions and the executed ones, it's not unfair to say that "C is fast"
If anyone knows what’s actually going on, please do tell.
The numbers match quite nicely. 40gb program size minus 32gb RAM is 8gb, divided by 800mb/s makes 10 seconds.
https://github.com/toji/gl-matrix/blob/master/dist/gl-matrix...
Ok but if you do want to play with writing binary code manually I recommend Casey Muratori's performance course
The technique actually has a lot of practical applications, so it's useful to have a C++ library that helps you with generating amd64 machine code.
Moreover, interviewers will be smitten by the hand-optimized assembly code.
printf("%d is %s\n", n, last_binary_bit(n) == 0 ? "even" : "odd");
int last_binary_bit(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
if (n == 2) return 0;
...
}
int last_binary_bit(int n) {
// Handle the easy cases.
if (n == 0) return 0;
if (n == 1) return 1;
// Number may be large. Divide and conquer. It doesn't matter where we split it,
// so use a randomized algorithm because those are fast.
for (;;) {
int r = random();
if (r < n) {
// Smaller numbers are easier.
int smaller1 = r;
int smaller2 = n - 4;
int bit1 = last_binary_bit(smaller1);
int bit2 = last_binary_bit(smaller2);
// Fancy math: even + even is even, even + odd is odd, etc.
if (bit1 == 0 && bit2 == 0) return 0;
if (bit1 == 0 && bit2 == 1) return 1;
if (bit1 == 1 && bit2 == 0) return 1;
if (bit1 == 1 && bit2 == 1) return 0;
}
}
} not eax
and eax, 1Lol
Many gigabytes saved!
/s
else
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
if (argc < 2) {
fprintf(stderr, "Usage: %s <string>\n", argv[0]);
return 1;
}
char *s = argv[1];
int i;
/* find the end of the string */
for (i = 0; s[i] != '\0'; ++i)
;
/* make sure the string wasn't empty */
if (i == 0) {
fprintf(stderr, "Error: empty string\n");
return 1;
}
/* last character is at s[i - 1] */
char d = s[i - 1];
if (d == '0')
printf("even\n");
if (d == '1')
printf("odd\n");
if (d == '2')
printf("even\n");
if (d == '3')
printf("odd\n");
if (d == '4')
printf("even\n");
if (d == '5')
printf("odd\n");
if (d == '6')
printf("even\n");
if (d == '7')
printf("odd\n");
if (d == '8')
printf("even\n");
if (d == '9')
printf("odd\n");
return 0;
}
./check_digit 999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
if (d & 1)
printf("odd\n");
else
printf("even\n") #define _(e) { e;};
#define r(e) _(return e)
#define I(b, e) _(if (b) r(e));
#define W(e) _(while (1) _(e));
int main(int c, char **v) {
_(I(c != 2, -1) _(c = 0) W(I(!v[1][c++], v[1][c - 2] & 1)))
} number="$1"
if [[ "$number" =~ "^(2|4|6|8|10|12|14|16|18|20)$" ]]; then
echo even
elif [[ "$number" =~ "^(1|3|5|7|9|11|13|15|17|19)$" ]]; then
echo odd
else
echo Nan
fi