Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to drive C#, C++ or Java compiler to compute 1+2+3+...+1000 at compile time?

People also ask

How do you get to your C: drive?

In later Windows version, the C: drive is labeled as Primary Drive or Local Disk, and can be accessed by default by opening the “My Computer” folder.

Is it okay for drive C to be full?

Well, what instantly jumps to mind is that having a "completely full" drive may cause some of the following problems: May cause problems for any program that need to generate temporary files or use the disk to cache (for example installers (even to other drives), downloading, compression, etc).


Updated Now with improved recursion depth! Works on MSVC10 and GCC without increased depth. :)


Simple compile-time recursion + addition:

template<unsigned Cur, unsigned Goal>
struct adder{
  static unsigned const sub_goal = (Cur + Goal) / 2;
  static unsigned const tmp = adder<Cur, sub_goal>::value;
  static unsigned const value = tmp + adder<sub_goal+1, Goal>::value;
};

template<unsigned Goal>
struct adder<Goal, Goal>{
  static unsigned const value = Goal;
};

Testcode:

template<unsigned Start>
struct sum_from{
  template<unsigned Goal>
  struct to{
    template<unsigned N>
    struct equals;

    typedef equals<adder<Start, Goal>::value> result;
  };
};

int main(){
  sum_from<1>::to<1000>::result();
}

Output for GCC:

error: declaration of ‘struct sum_from<1u>::to<1000u>::equals<500500u>’

Live example on Ideone.

Output for MSVC10:

error C2514: 'sum_from<Start>::to<Goal>::equals<Result>' : class has no constructors
      with
      [
          Start=1,
          Goal=1000,
          Result=500500
      ]

C# example to error at compile time.

class Foo
{
    const char Sum = (1000 + 1) * 1000 / 2;
}

Produces the following compilation error:

Constant value '500500' cannot be converted to a 'char' 

I should just write a program that could drive the compiler to compute this sum while compilation and print the result when compilation completes.

A popular trick to print a number during compilation is trying to access a non-existent member of a template instantiated with the number you want to print:

template<int> struct print_n {};

print_n<1000 * 1001 / 2>::foobar go;

The compiler then says:

error: 'foobar' in 'struct print_n<500500>' does not name a type

For a more interesting example of this technique, see Solve the eight queens problem at compile-time.


Since neither compiler nor language were specified in the interview question, I dare submit a solution in Haskell using GHC:

{-# LANGUAGE TemplateHaskell #-}
{-# OPTIONS_GHC -ddump-splices #-}
module Main where

main :: IO ()
main = print $(let x = sum [1 :: Int .. 1000] in [| x |])

Compile it:

$ ghc compsum.hs
[1 of 1] Compiling Main             ( compsum.hs, compsum.o )
Loading package ghc-prim ... linking ... done.
<snip more "Loading package ..." messages>
Loading package template-haskell ... linking ... done.
compsum.hs:6:16-56: Splicing expression
    let x = sum [1 :: Int .. 1000] in [| x |] ======> 500500
Linking compsum ...

And we got a working programme also.