4 billion if statements (2023) • Hacker News Board

Re: 4 billion if statements (2023)

#151

Post by Ensorceled » Fri, Dec 12, 2025, 9:07 PM UTC

I just had flash backs to a previous job where I was brought in to optimize another teams builds since they were now taking minutes instead of seconds.

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.

Re: 4 billion if statements (2023)

#152

Post by _kst_ » Fri, Dec 12, 2025, 9:07 PM UTC

The author missed an opportunity for a much shorter solution for the given problem statement.

    // Check whether a number is odd or even.

    #include 
    #include 
    #include 

    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");
    }

Re: 4 billion if statements (2023)

#153

Post by encom » Fri, Dec 12, 2025, 9:10 PM UTC

KeplerBoy wrote: post #143

encom wrote: post #81

Earlier quoted context omitted.

Well I created the 16 bit .c file, because I'm not that curious. gcc -O0 completed immediately and made a 1,5MB executable. -O1 took about 10 minutes for a 1,8 MB executable. -O2 has been running for 1h15m so far... i7-14700K I'm in too deep now, so I'll let it run while I'm at work.

Keep us updated.

GCC -O2 made a 1,8 MB executable after a bit over four hours. I'm not trying -O3 :D

I don't know enough about compilers to answer why this doesn't get optimised down to something tiny, or why it took so long. I'm not sure what we've learned tonight, but there you go.

Re: 4 billion if statements (2023)

#154

Post by sedatk » Fri, Dec 12, 2025, 9:22 PM UTC

dorianmariecom wrote: post #146

i tried in ruby up to 1 million (1 billion was taking too long) 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")) and added at the top i = ARGV.first.to_i but i'm getting SIGILL fish: Job 1, 'ruby check.rb 0' terminated by signal SIGILL (Illegal instruction)

Ooh a new bug.

Re: 4 billion if statements (2023)

#155

Post by jiggawatts » Fri, Dec 12, 2025, 9:27 PM UTC

uplifter wrote: post #127

nixpulvis wrote: post #98

Earlier quoted context omitted.

How is this time efficient at all? It takes upwards of 40 seconds to compute on large 32bit values. It's a joke post with some interesting bits and details.

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…

If the "exercise" is to strictly rely on if-else statements, then the obvious speedup is to perform a binary search instead of a linear one. The result would still be horrifically space inefficient, but the speed would be roughly the time it takes to load 32x 4KB pages randomly from disk (the article memory-mapped the file). On a modern SSD a random read is 20 microseconds, so that's less than a millisecond for an even/odd check!

"That's good enough, ship it to production. We'll optimise it later."

Re: 4 billion if statements (2023)

#156

Post by jiggawatts » Fri, Dec 12, 2025, 9:30 PM UTC

ZeroConcerns wrote: post #15

Ah, yes, exactly the pointless diversion I needed for my lunch break. For science: generating a C# switch statement for similar purposes took 7 minutes on similar-ish hardware, but the resulting 99.2GB file could not be opened or compiled ('Stream is too long'), which was slightly disappointing. Optimization efforts included increasing the internal buffer size of the StreamWriter used to create the source code: this…

To match the article, you'd want to directly emit the Intermediate Language (IL) tokens with something like this: https://learn.microsoft.com/en-us/dotnet/api/system.reflecti...

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.

Re: 4 billion if statements (2023)

#157

Post by niccl » Fri, Dec 12, 2025, 9:37 PM UTC

_kst_ wrote: post #152

The author missed an opportunity for a much shorter solution for the given problem statement. // Check whether a number is odd or even. #include #include #include 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"); }

Brilliant! Mr Boole would love this

Re: 4 billion if statements (2023)

#158

Post by nrhrjrjrjtntbt » Fri, Dec 12, 2025, 9:41 PM UTC

nixpulvis wrote: post #98

xnorswap wrote: post #91

This is time efficient* but rather wasteful of space. 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…

How is this time efficient at all? It takes upwards of 40 seconds to compute on large 32bit values. It's a joke post with some interesting bits and details.

r/whoosh

Re: 4 billion if statements (2023)

#159

Post by hybridtupel » Fri, Dec 12, 2025, 10:11 PM UTC

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.

Why not run both and use the result retrieved the fastest.

Re: 4 billion if statements (2023)

#160

Post by billforsternz » Fri, Dec 12, 2025, 10:19 PM UTC

I know it's silly, but I just want to fix his first version with the minimum possible changes;

  /* Copyright 2023. All unauthorized distribution of this source code
     will be persecuted to the fullest extent of the law*/
  #include 
  #include 
  #include 
  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");
  }

This way it basically works. It's a shame that it doesn't call out a non numeric argument but that's about the only problem. It relies on a trick, printf() returns the number of characters printed, so the error message string needs to be longer than 10.