123

In a recent interview, I was asked a really strange question. The interviewer asked me how can I compute 1+2+3+...+1000 just using compiler features. This means that I am not allowed to write a program and execute it, but I should just write a program that could drive the compiler to compute this sum while compilation and print the result when compilation completes. As a hint, he told me that I may use generics and pre-processor features of the compiler. It is possible to use C++, C# or Java compiler. Any ideas???

This question is not related to computing the sum without any loops asked here. In addition, It should be noted that the sum SHOULD be calculated during compilation. Printing just the result using C++ compiler directives is not acceptable.


Reading more about the posted answers, I found that solving problems during compilation using C++ templates is called metaprogramming. This is a technique that was discovered accidentally by Dr. Erwin Unruh, during the process of standardizing the C++ language. You may read more about this topic on wiki page of meta-programming. It seems that it is possible to write the program in Java using java annotations. You may take a look at maress's answer below.

A nice book about meta-programming in C++ is this one. Worth to take a look if interested.

A useful C++ meta-programming library is Boost's MPL this link.

TonySalimi
  • 8,257
  • 4
  • 33
  • 62
  • 17
    #error "500500" Does a compilation error count as "completing"? – Mysticial Jan 06 '12 at 19:43
  • 4
    The hint essentially means for you to use C++ templates. Obviously not the same but this one is for printing 1 to a 1000, I am sure you can modify it to add to a thousand... http://stackoverflow.com/questions/4568645/printing-1-to-1000-without-loop-or-conditionals – Joe Jan 06 '12 at 19:43
  • 8
    `const int value = 1 + 2 + 3.... + 1000; Console.WriteLine(value);` ;P – George Duckett Jan 06 '12 at 19:44
  • C++ templates can do it. – lapk Jan 06 '12 at 19:44
  • 2
    See the top answer here: http://stackoverflow.com/questions/4568645/printing-1-to-1000-without-loop-or-conditionals – alan Jan 06 '12 at 19:45
  • @Mysticial: The sum should be computing during compilation. – TonySalimi Jan 06 '12 at 19:45
  • Is there reason to believe that this is actually possible in Java? I cannot think of a Java solution and am curious if there is one. – Trevor Freeman Jan 06 '12 at 19:55
  • @increment1: I am not sure about Java, but taking a look at the answers, it seems that it may be possible in C++. – TonySalimi Jan 06 '12 at 19:57
  • 9
    Sometimes I think that some interview questions are asked merely to prove the interviewer's intellectual superiority over the interviewee. – Chris Jan 06 '12 at 22:26
  • 1
    @AndrewBarber, maybe they ask these questions to see how easily you get confused :-) – Tomas Jan 07 '12 at 00:34
  • @Tomas LOL... yeah, could be it! (and see Chris' comment right above yours, too!) – Andrew Barber Jan 07 '12 at 03:21
  • 1
    Are you allowed to say `const int sum = n * (n + 1) / 2;`? – Kerrek SB Jan 09 '12 at 16:38
  • 2
    I also experienced the same kind of interviewer and I refuse to accept the job because I don't want him to be my coworker. – LEMUEL ADANE Jan 10 '12 at 01:24
  • 1
    @Kerrek; No, as you see, your solution is executed on runtime not compile time. – TonySalimi Jan 10 '12 at 05:43
  • 2
    @hsalimi: Not necessarily.... in C++11, say `constexpr int n = 1000; constexpr int sum = n*(n+1)/2;`, and it'll be a compile-time constant expression. But this is essentially already true in C++03. – Kerrek SB Jan 10 '12 at 13:51
  • 4
    Did you ask for a **lot of money** before you were asked this question? – Salman A Jun 23 '12 at 09:26
  • Just one line works in many languages: `const int x = 500500`. Compile time! _if we are allowed to use mathematics formula then we can use a calculator too_ – masoud Sep 07 '13 at 15:50
  • @MM. As mentioned, the sum should be COMPUTED during compilation. – TonySalimi Sep 09 '13 at 12:06

13 Answers13

119

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
      ]
Xeo
  • 129,499
  • 52
  • 291
  • 397
  • @hsalimi: I edited the answer to actually show some code that gets the job done. :) – Xeo Jan 06 '12 at 20:06
  • Wow, you really impressed me :-) – TonySalimi Jan 06 '12 at 20:09
  • @hsalimi: It was Dr. Erwin Unruh who invented this technique at the 1997 C++ Standardization meeting in Stockholm. He computed a series of prime numbers. – Dietmar Kühl Jan 06 '12 at 20:46
  • To make it work without recursion you could use the formula of N*(N+1)/2 to compute the sum. – Adam Gritt Jan 06 '12 at 21:11
  • @Adam: Yes, but I wanted to truly "calculate" it without shortcuts / formulas. FredOverflow's answer is basically what you suggested here. – Xeo Jan 06 '12 at 21:14
  • @DietmarKühl : Woww ... would you please provide me more info about Dr. Erwin and this fantastic materials? Be glad to provide any link for his prime numbers solution. – TonySalimi Jan 09 '12 at 11:41
  • @hsalini: it is well-know C++ lore, easy to Google! This would finde e.g. [unruh.cpp](http://www.informit.com/articles/article.aspx?p=30667&seqNum=8). Seems I got the meeting it was invented at wrong, though. – Dietmar Kühl Jan 09 '12 at 11:49
  • 2
    @hsalimi In case you want to see a lot more fantastic examples of template metaprogramming in C++, I suggest [Modern C++ Design](http://www.amazon.com/Modern-Design-Generic-Programming-Patterns/dp/0201704315) by Andrei Alexandrescu. – AVH Jan 12 '12 at 09:57
90

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' 
Marlon
  • 19,924
  • 12
  • 70
  • 101
  • 4
    @ildjarn Well there's a difference between the c++ template answers and this one: This here only works because of constant folding while the template allows for arbitrary (?) code. Still a good idea to assign it to a char ! – Voo Jan 06 '12 at 20:44
  • @Voo Yes, but to be fair C# just doesn't compare with C++ for this kind of programming. – Marlon Jan 06 '12 at 21:14
  • 3
    @Marion And I really don't consider that a mistake in the language design ;) template meta programming may be all powerful, but other languages can still do most of the things with other solutions that don't have all those pitfalls. I've had to work on a project that took hours to compile (not completely true - it was unbelievably fast if we didn't increasing the recursive instantiation limit.. it failed in seconds) and was horrible to maintain. Probably a reason why I'm not much a fan of it.. – Voo Jan 06 '12 at 22:16
  • @Voo : FredOverflow's approach relies on constant folding as well. As far as slow compilation, blame your compiler, not the language (hint -- Clang compiles C++ **fast**). – ildjarn Jan 06 '12 at 23:25
  • @ildjarn Clang compiles extremely complicated, really deeply nested and horribly complex templates fast? I assume everything's possible and I can't test it anymore (thank god) but I can't imagine it. Also I'm talking about Xeo's approach not Fred's here. – Voo Jan 07 '12 at 00:30
  • @Voo : Yes, that's correct -- Clang compiles extremely complicated, really deeply nested and horribly complex templates with linear complexity while GCC compiles them with quadric complexity (or _used to_ -- I heard this was addressed relatively recently, maybe in 4.5+?) and VC++ compiles them with even worse than that. – ildjarn Jan 07 '12 at 00:35
51

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.

Community
  • 1
  • 1
fredoverflow
  • 256,549
  • 94
  • 388
  • 662
31

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.

Daniel Fischer
  • 181,706
  • 17
  • 308
  • 431
20

Life will be a lot easier with C++11 which adds constexpr functions for compile time calculation, although they're only currently support by gcc 4.6 or later.

constexpr unsigned sum(unsigned start, unsigned end) {
    return start == end ? start :
        sum(start, (start + end) / 2) +
        sum((start + end) / 2 + 1, end);
}

template <int> struct equals;
equals<sum(1,1000)> x;

The standard only requires the compiler to support a recursion depth of 512, so it still needs to avoid linear recursion depth. Here's the output:

$ g++-mp-4.6 --std=c++0x test.cpp -c
test.cpp:8:25: error: aggregate 'equals<500500> x' has incomplete type and cannot be defined

Of course you can just use the formula:

constexpr unsigned sum(unsigned start, unsigned end) {
    return (start + end) * (end - start + 1) / 2;
}

// static_assert is a C++11 assert, which checks
// at compile time.
static_assert(sum(0,1000) == 500500, "Sum failed for 0 to 1000");
Daniel James
  • 3,899
  • 22
  • 30
  • 1
    +1, totally forgot about `constexpr` for a moment. Maybe I just love templates too much. :( – Xeo Jan 07 '12 at 08:30
  • This is a nice use of constexpr to address the question (see the Adder implementation): http://kaizer.se/wiki/log/post/C++_constexpr_foldr/ – Matt Jan 11 '12 at 17:53
  • That formula can overflow; the last step is `/ 2` so to handle the full range of possible `unsigned` results, the value you're right-shifting would have to be n+1 bits wide, but it isn't. It's possible to rearrange the formula to avoid that, like clang does for runtime-variable ranges: https://godbolt.org/z/dUGXqg shows that clang knows the closed-form formula and uses it to optimize `total += i` loops. – Peter Cordes Mar 01 '20 at 20:01
14

In java, i thought about using annotation processing. The apt tool scans the source file before actually parsing the source file to the javac command.

During compilation of the source files, the output will be printed out:

@Documented
@Retention(RetentionPolicy.RUNTIME)
@Target({ElementType.TYPE, ElementType.METHOD})
public @interface MyInterface {

    int offset() default 0;

    int last() default 100;
}

The processor factory:

public class MyInterfaceAnnotationProcessorFactory implements AnnotationProcessorFactory {

    public Collection<String> supportedOptions() {
        System.err.println("Called supportedOptions.............................");
        return Collections.EMPTY_LIST;
    }

    public Collection<String> supportedAnnotationTypes() {
        System.err.println("Called supportedAnnotationTypes...........................");
        return Collections.singletonList("practiceproject.MyInterface");
    }

    public AnnotationProcessor getProcessorFor(Set<AnnotationTypeDeclaration> set, AnnotationProcessorEnvironment ape) {
        System.err.println("Called getProcessorFor................");
        if (set.isEmpty()) {
            return AnnotationProcessors.NO_OP;
        }
        return new MyInterfaceAnnotationProcessor(ape);
    }
}

The actual annotation processor:

public class MyInterfaceAnnotationProcessor implements AnnotationProcessor {

    private AnnotationProcessorEnvironment ape;
    private AnnotationTypeDeclaration atd;

    public MyInterfaceAnnotationProcessor(AnnotationProcessorEnvironment ape) {
        this.ape = ape;
        atd = (AnnotationTypeDeclaration) ape.getTypeDeclaration("practiceproject.MyInterface");
    }

    public void process() {
        Collection<Declaration> decls = ape.getDeclarationsAnnotatedWith(atd);
        for (Declaration dec : decls) {
            processDeclaration(dec);
        }
    }

    private void processDeclaration(Declaration d) {
        Collection<AnnotationMirror> ams = d.getAnnotationMirrors();
        for (AnnotationMirror am : ams) {
            if (am.getAnnotationType().getDeclaration().equals(atd)) {
                Map<AnnotationTypeElementDeclaration, AnnotationValue> values = am.getElementValues();
                int offset = 0;
                int last = 100;
                for (Map.Entry<AnnotationTypeElementDeclaration, AnnotationValue> entry : values.entrySet()) {
                    AnnotationTypeElementDeclaration ated = entry.getKey();
                    AnnotationValue v = entry.getValue();
                    String name = ated.getSimpleName();
                    if (name.equals("offset")) {
                        offset = ((Integer) v.getValue()).intValue();
                    } else if (name.equals("last")) {
                        last = ((Integer) v.getValue()).intValue();
                    }
                }
                //find the sum
                System.err.println("Sum: " + ((last + 1 - offset) / 2) * (2 * offset + (last - offset)));
            }
        }
    }
}

Then we create a source file. simple class that uses MyInterface annotation:

 @MyInterface(offset = 1, last = 1000)
public class Main {

    @MyInterface
    void doNothing() {
        System.out.println("Doing nothing");
    }

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        Main m = new Main();
        m.doNothing();
        MyInterface my = (MyInterface) m.getClass().getAnnotation(MyInterface.class);
        System.out.println("offset: " + my.offset());
        System.out.println("Last: " + my.last());
    }
}

The annotation processor is compiled into a jar file, then the apt tool is used to compile the source file as:

apt -cp "D:\Variance project\PracticeProject\dist\practiceproject.jar" -factory practiceproject.annotprocess.MyInterfaceAnnotationProcessorFactory "D:\Variance project\PracticeProject2\src\practiceproject2\Main.java"

The output of the project:

Called supportedAnnotationTypes...........................
Called getProcessorFor................
Sum: 5000
Sum: 500500
maress
  • 3,533
  • 1
  • 19
  • 37
9

I feel obligated to give this C code, since nobody else has yet:

#include <stdio.h>
int main() {
   int x = 1+2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17+18+19+20+
           21+22+23+24+25+26+27+28+29+30+31+32+33+34+35+36+37+38+39+40+
           41+42+43+44+45+46+47+48+49+50+51+52+53+54+55+56+57+58+59+60+
           61+62+63+64+65+66+67+68+69+70+71+72+73+74+75+76+77+78+79+80+
           81+82+83+84+85+86+87+88+89+90+91+92+93+94+95+96+97+98+99+100+     
           101+102+103+104+105+106+107+108+109+110+111+112+113+114+115+116+117+118+119+120+
           121+122+123+124+125+126+127+128+129+130+131+132+133+134+135+136+137+138+139+140+
           141+142+143+144+145+146+147+148+149+150+151+152+153+154+155+156+157+158+159+160+
           161+162+163+164+165+166+167+168+169+170+171+172+173+174+175+176+177+178+179+180+
           181+182+183+184+185+186+187+188+189+190+191+192+193+194+195+196+197+198+199+200+
           201+202+203+204+205+206+207+208+209+210+211+212+213+214+215+216+217+218+219+220+
           221+222+223+224+225+226+227+228+229+230+231+232+233+234+235+236+237+238+239+240+
           241+242+243+244+245+246+247+248+249+250+251+252+253+254+255+256+257+258+259+260+
           261+262+263+264+265+266+267+268+269+270+271+272+273+274+275+276+277+278+279+280+
           281+282+283+284+285+286+287+288+289+290+291+292+293+294+295+296+297+298+299+300+
           301+302+303+304+305+306+307+308+309+310+311+312+313+314+315+316+317+318+319+320+
           321+322+323+324+325+326+327+328+329+330+331+332+333+334+335+336+337+338+339+340+
           341+342+343+344+345+346+347+348+349+350+351+352+353+354+355+356+357+358+359+360+
           361+362+363+364+365+366+367+368+369+370+371+372+373+374+375+376+377+378+379+380+
           381+382+383+384+385+386+387+388+389+390+391+392+393+394+395+396+397+398+399+400+
           401+402+403+404+405+406+407+408+409+410+411+412+413+414+415+416+417+418+419+420+
           421+422+423+424+425+426+427+428+429+430+431+432+433+434+435+436+437+438+439+440+
           441+442+443+444+445+446+447+448+449+450+451+452+453+454+455+456+457+458+459+460+
           461+462+463+464+465+466+467+468+469+470+471+472+473+474+475+476+477+478+479+480+
           481+482+483+484+485+486+487+488+489+490+491+492+493+494+495+496+497+498+499+500+
           501+502+503+504+505+506+507+508+509+510+511+512+513+514+515+516+517+518+519+520+
           521+522+523+524+525+526+527+528+529+530+531+532+533+534+535+536+537+538+539+540+
           541+542+543+544+545+546+547+548+549+550+551+552+553+554+555+556+557+558+559+560+
           561+562+563+564+565+566+567+568+569+570+571+572+573+574+575+576+577+578+579+580+
           581+582+583+584+585+586+587+588+589+590+591+592+593+594+595+596+597+598+599+600+
           601+602+603+604+605+606+607+608+609+610+611+612+613+614+615+616+617+618+619+620+
           621+622+623+624+625+626+627+628+629+630+631+632+633+634+635+636+637+638+639+640+
           641+642+643+644+645+646+647+648+649+650+651+652+653+654+655+656+657+658+659+660+
           661+662+663+664+665+666+667+668+669+670+671+672+673+674+675+676+677+678+679+680+
           681+682+683+684+685+686+687+688+689+690+691+692+693+694+695+696+697+698+699+700+
           701+702+703+704+705+706+707+708+709+710+711+712+713+714+715+716+717+718+719+720+
           721+722+723+724+725+726+727+728+729+730+731+732+733+734+735+736+737+738+739+740+
           741+742+743+744+745+746+747+748+749+750+751+752+753+754+755+756+757+758+759+760+
           761+762+763+764+765+766+767+768+769+770+771+772+773+774+775+776+777+778+779+780+
           781+782+783+784+785+786+787+788+789+790+791+792+793+794+795+796+797+798+799+800+
           801+802+803+804+805+806+807+808+809+810+811+812+813+814+815+816+817+818+819+820+
           821+822+823+824+825+826+827+828+829+830+831+832+833+834+835+836+837+838+839+840+
           841+842+843+844+845+846+847+848+849+850+851+852+853+854+855+856+857+858+859+860+
           861+862+863+864+865+866+867+868+869+870+871+872+873+874+875+876+877+878+879+880+
           881+882+883+884+885+886+887+888+889+890+891+892+893+894+895+896+897+898+899+900+
           901+902+903+904+905+906+907+908+909+910+911+912+913+914+915+916+917+918+919+920+
           921+922+923+924+925+926+927+928+929+930+931+932+933+934+935+936+937+938+939+940+
           941+942+943+944+945+946+947+948+949+950+951+952+953+954+955+956+957+958+959+960+
           961+962+963+964+965+966+967+968+969+970+971+972+973+974+975+976+977+978+979+980+
           981+982+983+984+985+986+987+988+989+990+991+992+993+994+995+996+997+998+999+1000;
  printf("%d\n", x);
}

And all I need to do is check the assembly to find my answer!

gcc -S compile_sum.c;
grep "\$[0-9]*, *-4" compile_sum.s

And I see:

movl    $500500, -4(%rbp)
Carl Walsh
  • 6,100
  • 2
  • 46
  • 50
  • Feature of a specific implementation, not the C language. – Puppy Jul 21 '12 at 01:46
  • 5
    How many **C compilers** do you know of that are not a "specific implementation" of C? – Carl Walsh Jul 21 '12 at 23:18
  • @Puppy: If `x` was global, the compiler would be (more or less) required to evaluate the expression at compile time. ISO C doesn't allow runtime-variable initializers for globals. Of course a specific implementation could emit a call to a constructor-like static-init function that computes it at runtime and stores. But ISO C does let you use compile time constants as array sizes (like `int y[x];` in a struct definition or as another global for example), so any hypothetical pessimizing implementation would still have to support that. – Peter Cordes Mar 01 '20 at 20:18
9

Here's an implementation that works under VC++ 2010. I had to break the calculations up into 3 stages since the compiler complained when the templates recursed 500+ times.

template<int t_startVal, int t_baseVal = 0, int t_result = 0>
struct SumT
{
    enum { result = SumT<t_startVal - 1, t_baseVal, t_baseVal + t_result +
        t_startVal>::result };
};

template<int t_baseVal, int t_result>
struct SumT<0, t_baseVal, t_result>
{
    enum { result = t_result };
};

template<int output_value>
struct Dump
{
    enum { value = output_value };
    int bad_array[0];
};

enum
{
    value1 = SumT<400>::result,                // [1,400]
    value2 = SumT<400, 400, value1>::result,   // [401, 800]
    value3 = SumT<200, 800, value2>::result    // [801, 1000]
};

Dump<value3> dump;

When you compile this, you should see this output from the compiler something like this:

1>warning C4200: nonstandard extension used : zero-sized array in struct/union
1>          Cannot generate copy-ctor or copy-assignment operator when UDT contains a 
zero-sized array
1>          templatedrivensum.cpp(33) : see reference to class template 
instantiation 'Dump<output_value>' being compiled
1>          with
1>          [
1>              output_value=500500
1>          ]
hypercode
  • 488
  • 2
  • 10
  • Very nice idea with breaking it down, I think I'm gonna incorporate that into my answer somehow. +1 :) – Xeo Jan 07 '12 at 01:09
7

Extended from Carl Walsh's answer to actually print the result during compilation:

#define VALUE (1+2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17+18+19+20+\
21+22+23+24+25+26+27+28+29+30+31+32+33+34+35+36+37+38+39+40+\
41+42+43+44+45+46+47+48+49+50+51+52+53+54+55+56+57+58+59+60+\
61+62+63+64+65+66+67+68+69+70+71+72+73+74+75+76+77+78+79+80+\
81+82+83+84+85+86+87+88+89+90+91+92+93+94+95+96+97+98+99+100+\
101+102+103+104+105+106+107+108+109+110+111+112+113+114+115+116+117+118+119+120+\
121+122+123+124+125+126+127+128+129+130+131+132+133+134+135+136+137+138+139+140+\
141+142+143+144+145+146+147+148+149+150+151+152+153+154+155+156+157+158+159+160+\
161+162+163+164+165+166+167+168+169+170+171+172+173+174+175+176+177+178+179+180+\
181+182+183+184+185+186+187+188+189+190+191+192+193+194+195+196+197+198+199+200+\
201+202+203+204+205+206+207+208+209+210+211+212+213+214+215+216+217+218+219+220+\
221+222+223+224+225+226+227+228+229+230+231+232+233+234+235+236+237+238+239+240+\
241+242+243+244+245+246+247+248+249+250+251+252+253+254+255+256+257+258+259+260+\
261+262+263+264+265+266+267+268+269+270+271+272+273+274+275+276+277+278+279+280+\
281+282+283+284+285+286+287+288+289+290+291+292+293+294+295+296+297+298+299+300+\
301+302+303+304+305+306+307+308+309+310+311+312+313+314+315+316+317+318+319+320+\
321+322+323+324+325+326+327+328+329+330+331+332+333+334+335+336+337+338+339+340+\
341+342+343+344+345+346+347+348+349+350+351+352+353+354+355+356+357+358+359+360+\
361+362+363+364+365+366+367+368+369+370+371+372+373+374+375+376+377+378+379+380+\
381+382+383+384+385+386+387+388+389+390+391+392+393+394+395+396+397+398+399+400+\
401+402+403+404+405+406+407+408+409+410+411+412+413+414+415+416+417+418+419+420+\
421+422+423+424+425+426+427+428+429+430+431+432+433+434+435+436+437+438+439+440+\
441+442+443+444+445+446+447+448+449+450+451+452+453+454+455+456+457+458+459+460+\
461+462+463+464+465+466+467+468+469+470+471+472+473+474+475+476+477+478+479+480+\
481+482+483+484+485+486+487+488+489+490+491+492+493+494+495+496+497+498+499+500+\
501+502+503+504+505+506+507+508+509+510+511+512+513+514+515+516+517+518+519+520+\
521+522+523+524+525+526+527+528+529+530+531+532+533+534+535+536+537+538+539+540+\
541+542+543+544+545+546+547+548+549+550+551+552+553+554+555+556+557+558+559+560+\
561+562+563+564+565+566+567+568+569+570+571+572+573+574+575+576+577+578+579+580+\
581+582+583+584+585+586+587+588+589+590+591+592+593+594+595+596+597+598+599+600+\
601+602+603+604+605+606+607+608+609+610+611+612+613+614+615+616+617+618+619+620+\
621+622+623+624+625+626+627+628+629+630+631+632+633+634+635+636+637+638+639+640+\
641+642+643+644+645+646+647+648+649+650+651+652+653+654+655+656+657+658+659+660+\
661+662+663+664+665+666+667+668+669+670+671+672+673+674+675+676+677+678+679+680+\
681+682+683+684+685+686+687+688+689+690+691+692+693+694+695+696+697+698+699+700+\
701+702+703+704+705+706+707+708+709+710+711+712+713+714+715+716+717+718+719+720+\
721+722+723+724+725+726+727+728+729+730+731+732+733+734+735+736+737+738+739+740+\
741+742+743+744+745+746+747+748+749+750+751+752+753+754+755+756+757+758+759+760+\
761+762+763+764+765+766+767+768+769+770+771+772+773+774+775+776+777+778+779+780+\
781+782+783+784+785+786+787+788+789+790+791+792+793+794+795+796+797+798+799+800+\
801+802+803+804+805+806+807+808+809+810+811+812+813+814+815+816+817+818+819+820+\
821+822+823+824+825+826+827+828+829+830+831+832+833+834+835+836+837+838+839+840+\
841+842+843+844+845+846+847+848+849+850+851+852+853+854+855+856+857+858+859+860+\
861+862+863+864+865+866+867+868+869+870+871+872+873+874+875+876+877+878+879+880+\
881+882+883+884+885+886+887+888+889+890+891+892+893+894+895+896+897+898+899+900+\
901+902+903+904+905+906+907+908+909+910+911+912+913+914+915+916+917+918+919+920+\
921+922+923+924+925+926+927+928+929+930+931+932+933+934+935+936+937+938+939+940+\
941+942+943+944+945+946+947+948+949+950+951+952+953+954+955+956+957+958+959+960+\
961+962+963+964+965+966+967+968+969+970+971+972+973+974+975+976+977+978+979+980+\
981+982+983+984+985+986+987+988+989+990+991+992+993+994+995+996+997+998+999+1000)

char tab[VALUE];

int main()
{
    tab = 5;
}

gcc outputs:

test.c: In function 'main':
test.c:56:9: error: incompatible types when assigning to type 'char[500500]' fro
m type 'int'
milleniumbug
  • 15,379
  • 3
  • 47
  • 71
2

You can use (and mostly abuse) C++ macros/templates to do metaprogramming. AFAIK, Java doesn't allow the same kind of thing.

ptyx
  • 4,074
  • 1
  • 19
  • 21
  • 2
    Not really an answer to the question. – Ikke Jan 07 '12 at 14:33
  • I think you are right. In java you can't use the same template recursion trick, since a generic class parameter can't be a value - it must be a class. – Eyal Schneider Jan 07 '12 at 22:17
  • The generics feature of the C# compiler allows you to do some compile-time calculations. See [Eric Lippert's post](http://blogs.msdn.com/b/ericlippert/archive/2007/03/28/lambda-expressions-vs-anonymous-methods-part-five.aspx) about this. – Allon Guralnek Jan 10 '12 at 18:55
1

Using java you can do a similar thing to the C# answer:

public class Cheat {
    public static final int x = (1000 *1001/2);
}

javac -Xprint Cheat.java

public class Cheat {

  public Cheat();
  public static final int x = 500500;
}

you can do this in scala using peano numbers because you can force the compiler to do recursion but i don't think you can do the same thing in c#/java

another solution not using -Xprint but even more dodgy

public class Cheat {
  public static final int x = 5/(1000 *1001/2 - 500500);
}

javac -Xlint:all Cheat.java

Cheat.java:2: warning: [divzero] division by zero
  public static final int x = 5/(1000 *1001/2 - 500500);
                            ^
1 warning

without using any compiler flags. since you can check for an arbitrary number of constants (not just 500500) this solution should be acceptable.

public class Cheat {
  public static final short max = (Short.MAX_VALUE - 500500) + 1001*1000/2;
  public static final short overflow = (Short.MAX_VALUE - 500500 + 1) + 1001*1000/2;

}

Cheat.java:3: error: possible loss of precision
  public static final short overflow = (Short.MAX_VALUE - 500500 + 1) + 1001*1000/2;
                                                                  ^
  required: short
  found:    int
1 error
benmmurphy
  • 2,503
  • 1
  • 20
  • 30
  • You didn't drive the compiler to *compute* `500500`, sorry. – Xeo Aug 12 '12 at 17:38
  • 1
    is this in reference to all three solutions? in solution 1 i took some java code and compiled it and the compiler printed out 500500. that looks a lot like the compiler computing 500500. how is this not the compiler computing 500500? – benmmurphy Aug 12 '12 at 17:49
  • Yeah, true enough, I was talking about solution 2 and 3. I read this answer already on an earlier update and came back on the newest one and somehow seem to have forgotten the first solution. – Xeo Aug 12 '12 at 17:51
  • i would say solution 2&3 are computing it as well. you can add an arbitrary number of checks so you are basically doing `for (i = 0; i < 100000; ++i) {if (i == 1000*1000/2) print i}`. i have a 160mb java file that does this and it works :) – benmmurphy Aug 16 '12 at 00:11
1

Though this actually works with small numbers, clang++ returns me a compiler error if I am using sum_first where N > 400.

#include <iostream>

using namespace std;


template <int N>
struct sum_first
{
   static const int value = N + sum_first<N - 1>::value;
};

template <>
struct sum_first<0>
{
    static const int value = 0;
};

int main()
{
    cout << sum_first<1000>::value << endl;
}
ebasconp
  • 1,608
  • 2
  • 17
  • 27
1

In theory, you can use this:

#include <iostream>

template<int N>
struct Triangle{
  static int getVal()
  {
    return N + Triangle<N-1>::getVal();
  }
};

template<>
struct Triangle<1>{
  static int getVal()
  {
    return 1;
  }
};

int main(){
   std::cout << Triangle<1000>::getVal() << std::endl;
   return 0;
}

(based on the code that Xeo posted). But GCC gives me this error:

triangle.c++:7: error: template instantiation depth exceeds maximum of 500 (use -ftemplate-depth-NN to increase the maximum) instantiating struct Triangle<500>

plus an enormous pseudo-stacktrace.

ruakh
  • 175,680
  • 26
  • 273
  • 307
  • Gotta use the flag: -ftemplate-depth-1000 – Jetti Jan 06 '12 at 19:57
  • @hsalimi: Yes. It also works for 1000, once you add the flag. But it doesn't print *at compile-time*, and Xeo has changed his/her answer to actually answer this specific problem, so I think my answer is obsolete. :-) – ruakh Jan 06 '12 at 20:23