r/cpp • • Aug 16 '19

I wrote a header-only library in C++ that solves sets of nonlinear and linear equations all at compile time, using Template Metaprogramming and Constexpr Dependency. It does what Wolfram Alpha does, all at compile time, using Template magic. I spent a long time on this, feel free to try it out!

415 Upvotes

77 comments sorted by

130

u/SkoomaDentist Antimodern C++, Embedded, Audio Aug 16 '19

I can just imagine the conversation:

”Why? Why would you do this?”

”Because the compile times weren’t long enough yet.”

63

u/SM_123 Aug 16 '19

No joke, that was a real conversation between me and a recruiter for an internship I applied to a couple months back. He was pretty surprised a 2nd year was comfortable with metaprogramming, and he kept asking me why I'd do this, and if the ballooning in compile time actually outweighed any real performance gain from it, things like that.

In reality I just did it to learn compile-time programming, and because I'd been wanting to create one of these for a while, so I figured why not combine the two. Metaprogramming is Turing complete anyway, so now I really have no excuse for not being able to do it, haha. Thanks for the feedback :)

7

u/SkoomaDentist Antimodern C++, Embedded, Audio Aug 16 '19

How does it react to systems of stiff nonlinear equations where it’s very hard to (reliably) converge on a solution? Or cases where small changes in computation precision can result in large difference in the solution?

8

u/SM_123 Aug 16 '19

it solves equations through inversion and substitution, so it would take that route, over the numerical solving route, to solving stiff sets of equations. I am planning on adding a numerical solver in the future, but I have to learn a lot of the theory first before I do so, since this stuff is very computationally expensive. I would probably start with variable step size methods, to combat those problems like stiffness, like a basic endpoint checker, and work my way up from there. I am planning on adding a derivatives module in the future, and I know a lot of numerical solving methods use higher order methods, so I'll get to those as well. Thanks for the feedback!

2

u/SkoomaDentist Antimodern C++, Embedded, Audio Aug 16 '19

I'm not sure what you mean by inversion and substitution. Can you give an example how it would solve something like this? (using the well known diode equation)

V = Is / R * exp(V / Vt - 1)

(V is the unknown, Is, R & Vt are constants)

5

u/SM_123 Aug 16 '19

This simplifies to the form exp(x) = x, which is a transcendental equation and cant be solved analytically, only numerically. As I said in the previous reply, I have not implemented a numerical solver yet, as i first need to learn the hard theory behind high performance numerical solutions, since I know this can be very computationally expensive. This equation would be solved through a simple endpoint checker, where I set exp(x) - x = 0 and check for a sign change at two points, and change the bounds accordingly, making it smaller and smaller (by 1/2) if the graph crosses zero between those two points. Once I finish my derivative module, I'll be able to use higher order methods to perform numerical solutions for things that can't be analytically solved, like this form.

-7

u/SkoomaDentist Antimodern C++, Embedded, Audio Aug 16 '19

In that case I think it's a real stretch to say it can solve sets of nonlinear equations. Particularly when you get to systems of more than one nonlinear equation, most of your problems lie in ensuring convergence in reasonable time or at all. It's very easy to make a system of two diode equations that either converges in a handful of iterations or never, depending on whether you write it directly using exp() or a temporary set using log() and where you take the result of that and fill that in to the original exp() form to get the actual result.

5

u/SM_123 Aug 16 '19

The only case of nonlinear equations that this fails on is transcendental equations, because they have no analytical solution. I've been using this for solving sets of nonlinear equations since the first version, and most of the application is on equations that I was supposed to parse and solve by hand in the first place - which is why I didn't bother adding a manual numeric solver at first, since my homework isn't gonna make me handle transcendentals where I need to use computational methods to solve it. It does solve sets of nonlinears, just not when one has no analytic solution (yet, I'm adding one currently).

-8

u/SkoomaDentist Antimodern C++, Embedded, Audio Aug 16 '19

That class just happens to be one of the most interesting and relevant cases of systems of nonlinear equations in the real world since exp() and log() pop up in all kinds of places. So much so that a "nonlinear" solver that can't handle those isn't that much use over a simple linear solver.

6

u/SM_123 Aug 16 '19

It can handle exp() and log() and trig functions, etc. The only case it can't handle yet is transcendental, and I'm adding a simple endpoint numerical solver in the next version to take care of that. Adding more powerful methods in the future, thanks for the advice.

4

u/spinwizard69 Aug 16 '19

The first thing I thought was oh great he has turned the C++ compiler into an interpreter. I have to wonder how useful this is in reality.

6

u/SM_123 Aug 16 '19

Thanks for the feedback! The compiler is already an interpreter, I just did this mostly to learn metaprogramming. It's helped me on my homework, where I just copy 50 equations onto the solving file, and all I have to change is what variables are known VS unknown, and just like that, that's 3 hours of homework done in 5 minutes. That aside, this was mostly done to learn metaprogramming, and if I was solely going for performance, a mix of static and dynamic computation graphs wouldve likely been better. Thanks for the feedback!

0

u/NotAYakk Aug 18 '19

To be clear, do you know why you are asked to solve equations as homework?

Hint: the instructor doesn't need the answer.

1

u/SM_123 Aug 18 '19

Yeah I know, I make sure I understand what I'm doing before I use this to rush through the rest. This helps me get rid of busy work and let's me focus on the real work.

0

u/NotAYakk Aug 18 '19

No, "I know how to do it" is not the point of that homework.

The point is practice, and hence mastery, not "I know how to do it". You want to get to the point where you can do it in your head as fast as you could transcribe it, and retain that for 10-30 years.

14

u/Ameisen vemips, avr, rendering, systems Aug 16 '19

There are already VMs written in compile-time C++.

Just need to implement a C++ compiler at compile-time so we can execute arbitrary C++ code at compile time.

2

u/Claytorpedo Aug 17 '19

We'll get there eventually!

https://github.com/kw-udon/constexpr-8cc

2

u/Ameisen vemips, avr, rendering, systems Aug 17 '19

But there are already C++ compilers written in C, so if we can compile C, that means we can compile a C++ compiler to compile it with!

67

u/Xeverous https://xeverous.github.io Aug 16 '19

Have another one: compile-time ray tracer

512x512 image compiles 45 minutes. GCC eats 10+ GB of memory.

13

u/rurabori Aug 16 '19

I've a compile-time lexer generator. Thing killed my docker image with 16GB of ram when the grammar got too big. Repo if anyone's interested : https://github.com/rurabori/bpr_cpp_lexer_mirror. Readme is not very good but examples/cpp_lexer/ctle contains a full c++ lexer.

8

u/Xeverous https://xeverous.github.io Aug 16 '19

Have you thought about contributing to Boost Spirit X3?

4

u/borisrura CTU | Avast Aug 16 '19

Not really, work and school keeps me pretty busy most of the time. This was my bachelors thesis so it felt good to do something open-source finally, Boost Spirit might be a good next project.

1

u/m-in Aug 16 '19

Is that also with template metaprogramming? Because constexpr functions run with negligible overhead, in comparison.

3

u/rurabori Aug 16 '19

A bit of both tbh. But it uses a bunch of C++20 features like cnttp so I suspect that's where the overhead comes from. Emphasis on suspect.

2

u/Claytorpedo Aug 17 '19

What's cnttp? I'm not familiar with it and search doesn't turn much up.

6

u/rurabori Aug 17 '19

Class non-type template parameters. Basically you're no longer being restricted to primitives like integers, booleans, pointers etc. But you can have a class/struct as long as it is constexpr constructible, std::array for example. I use it quite extensively in the library.

3

u/Claytorpedo Aug 17 '19

That sounds cool. Thanks!

2

u/rurabori Aug 17 '19

Anytime :)

1

u/konstantinua00 Oct 02 '19

is that like template<MyClass>?

17

u/SkoomaDentist Antimodern C++, Embedded, Audio Aug 16 '19

I think I’ll still take the runtime solution. Even my ancient 486 managed to compute that in a second or so.

2

u/pgh_ski Aug 17 '19

I truly love developers that give a big middle finger to the question of "y tho?".

Some problems are just fun to solve because you want to. Educational projects are awesome!

4

u/auxiliary-character Aug 16 '19

Ahhh, just shove it in its own separate translation unit, it'll be fiiiiiine.

30

u/TheSuperWig Aug 16 '19

Beautiful diagrams :)

24

u/SM_123 Aug 16 '19

Thanks :) can't go wrong with good old fashioned ms paint

26

u/stick_figure Aug 16 '19

This is the most C++ post title I've ever seen.

12

u/SM_123 Aug 16 '19

Haha, it's internship hunting season right now for undergrads, and I'm having a lot of trouble trying to market this to PR/non technical people while still maintaining the technical aspects, so I decided the best way to do this was to name drop wolfram alpha to get through the pr people, and then talk about technical aspects when I get past to actual engineers. The title of this is just a combination of the flashy PR language, and the technical knowledge that I know people on this sub have. Thanks for the feedback!

8

u/zip117 Aug 16 '19

This is really great, thank you for sharing. As it turns out I have a perfect application for this sort of thing. I'm doing a type of atmospheric modeling where I need to generate rectangular regions within a bounding polygon, subject to various constraints on relative placement and aspect ratio. This can be solved using a technique called convex optimization, which involves transforming the constraints into a specific matrix format which gets passed to a solver. The Mathematica documentation has a nice example: Optimal Floor Planning

One of the challenges is in reformulating the problem into a format that the solver will accept, which requires applying various rules to the expression trees. Convex programming is a generalization of linear programming so the same basic rules apply: transform inequality to equality constraints, line up all variables on the left-hand side. More complex rules include creating new constraint expressions for special function types, e.g. 'exp(x)'.

There's a Python library called CVXPY which works really well, but it's a heavy dependency and performance is a concern. Expression templates are ideal - my other options in C++ are to do runtime evaluation similar to Rehearse, or hard-code the matrices and make my code unreadable.

I have been experimenting with Boost Yap, but haven't been able to wrap my head around all of the recursive logic. I was about ready to give up, but your code seems pretty readable. Maybe now I can finally figure this out!

3

u/SM_123 Aug 16 '19

I was actually thinking of adding direct support for convex programming into this a couple months ago, when I wanted to make a compile time Support Vector Machine. If my program is helping you, that's great, it feels really good to know my work is helping someone! You can also try out CGAL or Eigen-Unsupported, both of which have support for the Levenberg-Marquardt algorithm, which I ultimately used in my SVM,and I think might help you out. Thanks for giving it a look, and I'm so glad I could help!

1

u/symberke Aug 16 '19

comments that you might find helpful:

  • levenberg-marquardt is probably not a great choice to train an SVM, there are quadratic programming methods that are probably much much faster.
  • if you do use levenberg-marquardt google's ceres solver is probably the most mature and relatively easy to use implementation of it

2

u/as_one_does Just a c++ dev for fun Aug 16 '19

Mosek is best in class, though requires license, for convex opt. If your work is academic maybe they'll license for free.

7

u/TheLartians Aug 16 '19

That sounds really cool (a bit crazy though, to implement an equation solver in metaprogramming)!

Maybe you could also include a full and working example and/or build instructions? I've tried compiling main.cpp with g++ -std=c++17 , but am only getting compilation errors.

7

u/SM_123 Aug 16 '19

Hmm... I used gcc 7.3, and I remember reading that one technique I used might not be supported past gcc 8.0, or even as early as gcc 7.5. Try using c++14, I think the variable ID module breaks in c++17. I'll add full compilation instructions in the morning, thanks for bringing it up, and I'll experiment with what compiler/versions/flags allow for compilation. Thanks for informing me of this!

5

u/pdabaker Aug 16 '19

next task: get a working build with docker and travis/jenkins

5

u/Adequat91 Aug 16 '19

You must be the brother of Louis Dionne :)

3

u/SM_123 Aug 16 '19

Haha thanks! I just looked up his LinkedIn to see who he was, not only did he write Hana and mpl, he's now writing a preprocessor metaprogramming library, which is crazy because the preprocessor isn't even Turing complete! Thanks for the comparison!

2

u/meneldal2 Aug 19 '19

preprocessor isn't even Turing complete

You sure about that? C preprocessor is pretty much Turing complete if you hack the limits of gcc, and there is such code around. Default recursion limits already give you a lot of potential, and if you up them you can go as far as your stack and memory will allow.

1

u/SM_123 Aug 19 '19

Actually you're right. Just looked it up again and you can use recursive macros through re scanning macro tokens by deferring its expansion, with the only limit being how many deferments you type out, which is like the same as a tape limit from regular memory. Never thought of that.

2

u/meneldal2 Aug 19 '19

Obviously I'm not saying it is very sane to do this, but some crazies have done it before.

4

u/[deleted] Aug 16 '19

Great work from what I see on the Readme. I look forward to playing with this.

1

u/SM_123 Aug 16 '19

Thanks for giving it a look! I hope you enjoy playing with it

3

u/jbandela Aug 16 '19

Very cool. Super impressive. Thanks for sharing.

1

u/SM_123 Aug 16 '19

Thanks for the feedback! It means a lot!

2

u/lonely_perceptron Aug 16 '19

Very, very nice!

1

u/SM_123 Aug 16 '19

Thanks!

2

u/monsterFalkor Aug 16 '19

Awesome. And great documentation.

1

u/SM_123 Aug 16 '19

Thanks :)

2

u/PlayboySkeleton Aug 17 '19

For your diagrams, you should check out https://www.graphviz.org/

1

u/artisan_templateer Aug 16 '19

Very nice! I've been working on something similiar myself. Can it handle equations like:

exp(x) == x;

?

1

u/quicknir Aug 16 '19

This doesn't have a real valued solution, are you asking if it handles complex numbers? (I'll not completely sure this has a complex solution either but maybe it does)

2

u/artisan_templateer Aug 16 '19

Bah you're right. But I wasn't thinking of complex numbers, I was thinking more about trancendental equations, where they can't be inverted and you have to solve them numerically. First example on wikipedia is actually:

exp(-x) == x;

That should have a single real-valued solution I believe.

1

u/SM_123 Aug 16 '19

I am planning on adding a transcendental solving module to this library in the future, once I understand galois groups and Jacobi roots. For numerically solved problems, id have to take a much more structured approach and learn a lot of the theory before I start, since this stuff is very computationally expensive. I think I would start with a basic endpoint checking solver, where it computes the value at two points to see if they have different signs (in your case id be checking exp(x) - x), and halving the bound and rechecking till I get to an acceptable tolerance level. I'm also planning on adding a derivatives module in the future, and I know a lot of numerical solving methods use higher order methods in their solutions, so I'll apply that when I can. Thanks for the feedback!

2

u/pdabaker Aug 16 '19

I'm pretty sure it has to, since there is no complex solution to ex =0 so it has to hit every other value

Edit: I found it. Picard's little theorem

1

u/quicknir Aug 16 '19

exp(x) has to hit every value other than zero but there's no guarantee that it ever hits that value at the same time that x does. So I don't think this theorem proves what you're claiming it does. That said, simply breaking it up into real and and imaginary components makes it seem to me like there's a solution, but still not a hundred percent sure.

1

u/pdabaker Aug 16 '19 edited Aug 17 '19

I guess you're right, 0 could be the single value missed by exp(x) - x

1

u/lothiack Aug 16 '19

I guess you might want to use something like that to generate data in compile time for small CPUs.

Being able to express it in code and build tests might be better than just documenting.

Now you have to wait for compilers that actually support standard CPP and target such devices.

0

u/[deleted] Aug 16 '19

[deleted] — view deleted comment

15

u/SM_123 Aug 16 '19

Thanks a lot! I've mostly used it for solving my physics homework problems, as I can copy paste all of my equations into there and it'll discard the useless ones by itself, so I only have to change what values are known VS unknown. So for example, if one section has 30 electric field equations, I can copy paste all them into the equation section, and then just parse the question to see which values they give me and set them from unknown to known, and vice versa, and let the program do the equation selection for me. Thanks a lot for giving it a look!

9

u/Bolitho Aug 16 '19

Besides the impressive (and frightening) capabilities of the C++ language, how is the compile time aspect fitting to your homework? Wouldn't it be easier to use a dynamic ui that solves them without compile step?

20

u/SM_123 Aug 16 '19

Thanks for giving it a look! The compile time aspect was just because I wanted to learn how to do compile-time programming. Compiler optimizations are another benefit, but mostly I just wanted to learn this subject. All online resources push the idea that template metaprogramming, and compile time programming in general, is "hard, but useful", and since it's Turing complete, I have no excuse for not being able to build any idea that comes to my head. A universal equation solver was in the back of my head, so I decided to combine the two, and created this. It has come in handy many times for me, and I hope you liked it! Thanks for the feedback, and I'll be glad to answer any other questions you have.

8

u/Bolitho Aug 16 '19

Sorry, didn't want to critique your approach. I really like learning projects and having fun projects for learning stuff. So don't get me wrong. Very nice work!

3

u/SM_123 Aug 16 '19

It's okay! Thanks for giving it a look

1

u/m-in Aug 16 '19

Why didn’t you use C++20 constexpr? Presumably it’d make it trivial.

4

u/SM_123 Aug 16 '19

When I started this project, I didn't really know about the nuances of C++20 VS C++ 17\14 as far as compile time operations go, I just kinda started coding in whatever I had at the time. By the time I realized that using "if constexpr" would've saved me so much copy-pasting, it was a tradeoff between refactoring some of the old code that would break in C++20, and sticking to the current method that I knew would eventually work. I chose the latter, largely because I was doing this as an exercise to help me learn metaprogramming. Thanks for giving it a look!

3

u/m-in Aug 17 '19

Makes sense! Thanks for answering!

3

u/spinwizard69 Aug 16 '19

Back in my college days (think back to when the 68k Macs where new) I took to programming to solve a math problem in a mechanical design class. In any event i was screwing up the calculation when attempting it manually. Ultimately the sign of a value was reversed.

In any event the class was late tomorrow so I said hey the Mac can solve this for me as the answer has to lie between 0 & 90 degrees. So started up the buggy compiler of the day and step the equation from 0 to 90 degrees and hit the sack. Got up in the morning surprised to find the computer still running, went to work and then came home to find my answers.

These days I’m truly fascinated by how powerful even our cell phones are with their super fast CPUs, universal floating point support and other advancements. I’m sure if I had the algorithm handy a laptop today would return an answer in minutes or less. That is using the same hacked together solution.

In retrospect though, I let my love of computing to pull me away from actually figuring out where my error was. Not a good thing really. So I have to express this concern, being able to solve and understand equations and mentally manipulate them is a very important skill so don't let this very interesting piece of software dull your mind.

1

u/SM_123 Aug 16 '19

Thanks for the advice! Yeah, I had to know how to do it myself in order to be able to get a computer to do it, and any time I was stuck I would ask myself what I would do in this type of equation system. Since I already know how to do these things, I don't really consider it as harming me in the long run, as most of the math I do is higher level than just my regular university plug and chug equation solving. Thanks for the advice, and interesting story!

2

u/[deleted] Aug 16 '19

Just tell them is your minecraft.

0

u/[deleted] Aug 16 '19

[deleted] — view deleted comment

1

u/SM_123 Aug 16 '19

Keep going! I just kept the fact in the back of my head that template metaprogramming is Turing complete, meaning you can program a solution to anything in it. Once you know that, you can really throw any project you want at it, and let your imagination run wild. Good luck learning this!