2

It's mostly all in the title. How do you report the runtime of a C++ program that has intensive calculations at compile-time?

If I have a program that, when I use the bash time command on it, appears to run in .5 seconds, but the COMPILE TIME CALCULATIONS take over 10 minutes, can I honestly say my program runs in .5 seconds?

8
  • 1
    wow i posted this 5 seconds ago and there's already a downvote
    – HiddenToad
    Feb 9 at 18:02
  • 5
    Then I'd suggest the architecture of your code is sub-optimal and you are addressing the wrong issue. And why do you think "run time" is anything other than the time required to run the program?
    – Peter M
    Feb 9 at 18:09
  • 1
    If you are compiling as a precursor step, then you create a shell script and use the time command on that. Feb 9 at 19:30
  • 1
    Stepping back a bit here: why do you care what people might think is the runtime of your convoluted prime finder? Feb 9 at 23:17
  • 2
    "can i honestly say my program runs in .5 seconds?" Are the people using your program compiling it? Will they care how long it takes to execute? Feb 10 at 7:44

2 Answers 2

8

You don't. Run-time is not compile-time, and nobody except the developer cares in the least how long compilation took.

(But also what Peter said: if your system really works like this, then something is very wrong to begin with.)

5

The Sieve of Eratosthenes calculates all prime numbers up to any given limit. If you're calculating primes at compile time you're simply shifting what would have been a run time speed cost to a space cost. Yes your program runs faster when ran for primes "under a certain limit" but the bigger that limit the bigger your program.

It's called the space time tradeoff. It's why algorithms aren't only rated in big O for speed but also space.

In terms of speed the Sieve is O(n log log n). Space is O(n).

Your pre-calculated Sieve has speed at O(1) and space is the same. Except the pre-calculation invents a new big O category to consider: distribution size. Where the classic Sieve algorithm's distribution size is O(1) your pre-calculated Sieve distribution size is O(n).

Congrats. It's a different way to tradeoff. One that requires maintaining and distributing n binaries. Enjoy.

3
  • I would be surprised if running a sieve at compile time is as fast as running the same sieve at runtime. For this specific problem, you should be able to run a sieve that can examine several hundred million integers per second. How long does it take to load these integers from the compiled file?
    – gnasher729
    Feb 9 at 23:42
  • @gnasher729 it takes O(n) to load if you insist on loading the whole thing. You don’t have to. Also, the rate of examined numbers isn’t what we’re competing with. It’s the rate of discovered primes. Feb 10 at 1:19
  • Rate of discovered primes = number of primes examined / log n. Practically linear.
    – gnasher729
    Feb 11 at 16:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.