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!
30
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
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
3
2
2
2
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
Aug 16 '19
[deleted]
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
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
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
0
Aug 16 '19
[deleted]
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!
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.”