How to drive C#, C++ or Java compiler to compute 1+2+3+...+1000 at compile time?
C#JavaC++Compiler ConstructionMetaprogrammingC# Problem Overview
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.
C# Solutions
Solution 1 - C#
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>’
Output for MSVC10:
error C2514: 'sum_from<Start>::to<Goal>::equals<Result>' : class has no constructors
with
[
Start=1,
Goal=1000,
Result=500500
]
Solution 2 - C#
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'
Solution 3 - C#
> 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.
Solution 4 - C#
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.
Solution 5 - C#
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");
Solution 6 - C#
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
Solution 7 - C#
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> ]
Solution 8 - C#
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)
Solution 9 - C#
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'
Solution 10 - C#
You can use (and mostly abuse) C++ macros/templates to do metaprogramming. AFAIK, Java doesn't allow the same kind of thing.
Solution 11 - C#
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.
Solution 12 - C#
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
Solution 13 - C#
Though this actually works with small numbers, clang++ returns me a compiler error if I am using sum_first
#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;
}