Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

4 billion if statements (2023)

andreasjhkarlsson.github.io

Post reply on HN
Print view View original

171–180 of 183 posts

Re: 4 billion if statements (2023)

#171

Post by sfink »

Sulf1re wrote: post #166

I don't get it. why not just look look at the last binary bit?

Hm, good thought. You could just do

    printf("%d is %s\n", n, last_binary_bit(n) == 0 ? "even" : "odd");
and the rest is trivial:

    int last_binary_bit(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        if (n == 2) return 0;
        ...
    }
Come to think of it, with a little fancy math you could divide and conquer:

    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

Re: 4 billion if statements (2023)

#173

Post by LegionMammal978 »

billforsternz wrote: post #167
pcthrowaway wrote: post #165

Earlier quoted context omitted.

Wouldn't using elif for all comparisons after the first improve performance? Or is the performance considered worse because it becomes O(n) (where n < MAX_UINT) vs. constant time ( O(MAX_UINT) )

It certainly would be normal to use else if (or switch) if you wanted to be picky but really such changes are inconsequential here. And I was trying to change just one line. Sadly I also had to quietly change stdlib.h to string.h as well.

If you wanted to avoid , you could use the poor man's strlen(), snprintf(0,0,"%s",argv[1]). For full input validation without adding any more statements, the best I can get (in ISO C) is

      uint8_t number = (argc
Though with either function you may run into issues if the OS allows arguments longer than INT_MAX. To be defensive, you could use "%32767s" or "%*32767[0123456789]%n" instead, at the cost of failing inputs longer than 32KiB.

Re: 4 billion if statements (2023)

#174

Post by teo_zero »

tetris11 wrote: post #26
imtringued wrote: post #14

Earlier quoted context omitted.

You can do it even faster with the if statements: #include #include int main(int argc, char *argv[]) { if (argc \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…

probably easier in bash: 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 A bit limited, but you can scale it up

Scaled up:

  case "$1" in
    *0|*2|*4|*6|*8) echo even;;
    *) echo odd;;
  esac
If $1 had a trailing non-digit, or was empty, that would indeed be an odd situation!

Re: 4 billion if statements (2023)

#176

Post by thih9 »

waisbrot wrote: post #105
thih9 wrote: post #82

Earlier quoted context omitted.

I expected some job interview meme[1][2] but I did not know this one and it looks like a real story too! Thanks for sharing, that was a fun read. [1]: https://aphyr.com/posts/342-typing-the-technical-interview [2]: https://www.richard-towers.com/2023/03/11/typescripting-the-...

I love the Aphyr posts. > “Can I use any language?” > > “Sure.” > > Move quickly, before he realizes his mistake.

Works both in job interviews and real projects!

I’m almost serious, the only time I saw haskell in production was after a similar scenario.

Re: 4 billion if statements (2023)

#177

Post by bmacho »

hellzbellz123 wrote: post #37
philippta wrote: post #24

> I saw from the SSD was around 800 MB/s (which doesn’t really make sense as that should give execution speeds at 40+ seconds, but computers are magical so who knows what is going on). If anyone knows what’s actually going on, please do tell.

I'm not entirely sure but could it be predictive branching?

No, it needs to read the entire executable in order to be correct, it can't skip anything. Therefore the time for the IO must be a lower bound, predictive branching can't help that.

Re: 4 billion if statements (2023)

#178

Post by [deleted] »

bobbylarrybobby wrote: post #137
majkinetor wrote: post #72

Earlier quoted context omitted.

But then, even numbers will have the worst possible performance.

You brought up an important opportunity for optimization. If you know the distribution of your data, it may make more sense to implement it in terms of the odd numbers and leave even numbers as the fallback. It's important to profile with a realistic distribution of data to make sure you're targeting the correct parity of numbers.

[deleted]

Re: 4 billion if statements (2023)

#179

Post by blauditore »

IncreasePosts wrote: post #96
majkinetor wrote: post #72

Earlier quoted context omitted.

But then, even numbers will have the worst possible performance.

Good point. Have two programs - one checking every even number and returning odd of not even. And then have a program checking every odd number and returning even if not. Then, a simple program to dispatch to either program randomly, so you end up in the long term with good performance for each.

That sounds kinda stupid, it would completely destroy the original space savings. Unless the sharding makes it fit within compiler limits.

Re: 4 billion if statements (2023)

#180

Post by __david__ »

mandarax8 wrote: post #149
uplifter wrote: post #127

Earlier quoted context omitted.

You're absolutely right. The obvious solution would have been to create a boolean table containing all the pre-computed answers, and then simply use the integer you are testing as the index of the correct answer in memory. Now your isEven code is just a simple array lookup! Such an obvious improvement, I can't believe the OP didn't see it. And with a little extra work you can shrink the whole table's size in memory b…

Maybe we can even find some correlation in the bit pattern of the input and the Boolean table!

Perhaps, but I fear you’re veering way too much into “clever” territory. Remember, this code has to be understandable to the junior members of the team! If you’re not careful you’ll end up with arcane operators, strange magic numbers, and a general unreadable mess.
Post reply on HN