Zero-dependency Algebra Calculator

I made the cursor work with offsets (mostly)

As it turns out, great things can happen when you sit down for five hours with a good playlist.
I made all of the characters with a bitmap 8x8 font. It'll be fine for this, especially since I think I've already picked the screen resolution I'll be using.
I made the logic for displaying the current expression using that font, and I also made the cursor work properly. It's all I wanted to accomplish and more.
Tomorrow, I'll make subscripts work and maybe some of the solving buttons if I get to it. I'll be nearly done the project then.

Today, I worked on the boilerplate for letters and made the digit 0 (might be improved later). Tomorrow, I'll throw on some good tunes and bang out all of the letters.

Today, I finished nearly all the buttons and made the click stuff happen for the easy ones.

Alright, got the display working. I'm using Raylib for the buttons and window management, though the actual display part will be zero-dependency. I got some button code working too. They don't do anything, but they have click detection.

Yun's theorem works now and is integrated into my root-finding! I'm very nearly done the algebra part; I just need to get rid of denominators before solving and add some conditions to my validity checker. After that, I can finally get on to the display code.

So I just spent some time fixing bugs with my GCD, division, and expansion code. I also wrote maybe 75% of an implementation of Yun's algorithm. though I've run out of time. Below attached is my progress in the size of the project; it's easily my largest yet.

So polynomial GCF was a little more involved than I thought it would be. I've got it mostly working, here's an example. Tomorrow I'll finish it up an hopefully finally make Yun's algorithm.

I had planned to implement Yun's algorithm today, but that took longer than I thought it would. It needs polynomial GCF, which needs polynomial division. As I was implementing polynomial division, I unearthed a bunch of bugs with my old expansion code which was a lot of fun to fix. GCF should hopefully be easy now that I have a functional division function (should be very similar to integer), and Yun's algorithm should be easy if I have that. I already wrote a function to get the derivative of a polynomial, so I don't have to worry about that.

It works! Well, mostly. It can't deal at all with multiplicity, but I can deal with that probably tomorrow. The bisection method was surprisingly easy to implement, but Yun's theorem still scares me.

Using Bundan's theorem, I made some code that can roughly pinpoint the location of a root. I think I'll work on an implementation of the bisection method tomorrow. While painfully slow, it will always work and I think the performance is good enough for my purposes. If I were calculating something hundreds of times per second, I might reconsider.

I'm back! I didn't have much coding time last week, but I did get an implementation of Bundan's theorem working. I hope to get a real root isolation function working in the next couple hours. Also, I've decided to put a pause on hardware. I'm going to finish this, throw it onto the web with Emscripten, and ship it. I think with hardware it's going to take me beyond the length that Summer of Code runs, though I definitely still plan to make hardware for this.

Alrighty then, a couple things.
First, I got rearrangement working. The function takes in an expression and a target, and rearranges to have that target on the left.
Second, I got an implementation of the power rule working. I'm planning on doing real-root isolation with Bundan's theorem, so I need to be able to calculate the derivative of a polynomial for that.
Third, I'm going to be busier this next week. I plan on aiming for at least a half hour per day, but progress will slow until next weekend.
Last, I was thinking about what I want the final product to be. First, I'm going to finish the math stuff. Then, I think I'll design and order a PCB for a physical calculator. While that's shipping, I'll work on the display code in the medium of a web version through WASM. That way, I have a demo at the end of this that is easily shared. Things can change, of course, but that's my plan as of right now.
If you're reading this last part, thanks! See ya later.

I've spent some time working on the rearrangement, but most of the time is debugging my expansion code. It doesn't help that the Zed debugger doesn't have a feature to easily expand an array completely, which makes this much more tedious.

After spending a bunch of time working on term separation, I realized that the expansion code I already had was enough to start working on root-finding. I quickly implemented a version of Cauchy's bound, which is a way to find the maximum and minimum bounds of all roots of a polynomial.

I've just been fixing bugs that I'm finding in my polynomial expansion. There was an issue with multivariate polynomials, and another with zero coefficients that I had to fix. I think it's nearly correct now, though. I've also been working on some code to check the validity of expressions.

I've made the expansion of polynomials much faster, and it can support much higher degrees without segfaulting too. I've also crossed both the 50 hour mark and the 2500 LOC mark.

Bunch of small bugfixes, I'm very happy with the results.

The biggest things I've done are make it so excess parentheses don't affect the final answer and make it so things multiplied after a block are multiplied into it. Both are demonstrated below. The code that makes the things after multiply in should be able to be trivially used to support polynomial multiplication, but I'm leaving that to tomorrow in order to be able to jump right into something.

Alright, I just spent an hour looking for this single line of code. It shouldn't be i - 1, it should just be i, and it was causing everything to fail in weird ways. On the bright side, multivariate expressions work now!

The last 10 hours have been completely spent on trying to get polynomial expansion working. I've almost got monomial by polynomial working, it's able to expand and reduce within terms, I've just got to finish up term combination. I've got an idea for how to handle polynomial by polynomial, so I'll do that next.

The constant expression solving is working! I was debugging it today, but I've fixed the main bug and hopefully there aren't more. It can take in a set of constant and a bunch of variables and their values and solve the equation. It supports all of the operations I've implemented so far, and the \ notation is various functions like roots, logs, and trigonometric functions. I think I have enough now to use this library for a scientific calculator, but I really want to add some solving ability to this. I'm going to read up about the root-finding algorithms I've decided to use and hopefully manage to get something working soon. After that, I think it's on to hardware!

Today, I got maybe 85% of the way done on my constant expression solving. It's able to solve anything following the order of operations to a T. I made a mistake when writing the lexer. For some reason, I assumed the index of radicals and bases of logarithms would always be a constant decimal, which is obviously not the case. I'll fix that tomorrow and provide a proper update on it then.
The code shown below is my new decimal power function. My old one would convert the decimal to a fraction, then solve based on that. This function would be very prone to overflowing if the decimal was large; providing wrong solutions. This new one is an iterative method that computes the partial part of the power by guessing and checking with my new logarithm function, then multiplying it by the whole part. I've tested it; it's not only faster but it also correctly got the solution to a stupidly large exponent to 13 decimal places, which is well beyond the rough precision goals I've been following for this project.

Alright, so I don't have that much coding time on this one. I spent some time setting up some structs and unions for parsing expressions, then realized I had no idea how to make an algebra algorithm. Of course, I have some ideas. But I wasn't sure how to deal with equations that are impossible or very difficult to solve algebraically. I then spent the next couple hours reading about root-finding algorithms, and I still haven't found one I like. I think I'll work on this function to evaluate expressions rather than solve for a variable. I'll also keep reading about these root-finding algorithms, maybe there's something that will work. Maybe I'll have to pivot this to a scientific calculator project, we'll see.

The last couple devlogs have been slow, but all of the trying and failing there has compounded in the last hour and a half. I've gotten both the lexer and logarithms working.
First, the lexer. Turns out that beyond some precision problems in my number recognition, it was mostly bug-free. I'm sure something will come up later, but it's working well enough now for me to continue.
Next, logarithms. I spent a little while learning about how they actually work; much less superficially than I thought I knew them before. My implementation uses a series to calculate natural logarithms. I then use this to calculate log base 2, which takes advantage of the fact that IEEE-754 floating point is basically just scientific notation to make it ridiculously fast. Finally, I can trivially calculate logs of any base using the identity log base a (x) = log base b (x) / log base b (a). My implementation is not only precise, but it's more than fast enough for my needs.

The code is there, but it doesn't necessarily, uh, work. I thought I'd just put everything down at once, and then I'd go through debugging. Much debugging.

I've been working on the lexing step of reading equations. The code is still coming along (a fair amount of dev time was missed by Hackatime), though here's the plan for the pseudo-FSM that I'll be using.

Since I've been struggling to get logarithm working but still want to post something, here's a portion of my makefile where I've got some functions working. There are more lines than shown, but this will let me update flags and such for all compiled targets at once.

Here is my first attempt at logarithm. It's only able to get 5 or 6 correct digits before the fraction blows up. Time for some more reading to find a better method!

I've been working on some code to convert decimal to either mixed or improper fractions. Got most of it working last night, though made some tweaks this morning to assure more precision and deal with negative numbers.

I've been working on a bunch of little things, fractions, fractional exponents, some other helper functions. None of it is super interesting, though. One thing I caught in my root implementation is the line of code in the attached screenshot. I'm familiar with C, but I do still miss the little things such as this. I thought the caret meant exponent as it does in many other languages, but it actually means XOR, which definitely isn't what I wanted.

Alright, fixed some of the edge cases, the attached screenshot is one of them. The fun thing about doing everything from scratch is that if you have a subtle bug somewhere, it's a lot of fun to track down. The errors seemed to be mostly from my nth root function freaking out on large values. I've been thinking recently about when I want this project to include, so I think I'll throw that all down into a text file next.

I thought inverse trigonometric functions would be easy. I was wrong.
I've got it ALMOST working. It works great in 99% of cases, though there are a couple where my functions are off by a few hundredths. My brain is exhausted from doing trig all day (there was much time not spent in my editor and thus not counted); I'll tackle it again tomorrow.

My implementation of tangent using lookup tables ended up being not quite precise enough, so I spent much of the day researching an algorithm called CORDIC. My implementation of it is able to get all of the trig ratios well into the double digit sig figs, so more than good enough for my purposes. Next is inverse trig ratios, I'll update when those are working. I'm pretty sure it'll be very similar to my current code for going forwards.

Got the range of tangent values between 0 and PI/2 in a lookup table. I've also now got a function to use this to estimate values of tangent in between data points, and it seems to be working now to six sig figs. Tomorrow, planning on making this work for all values of tangent, then working on the other trig ratios if that goes well.

Got nth roots working!
I'm using a method that I've seen called Newton's method, Heron's method, and the Babylonian method. Give it a try; calculating roots to arbitrarily high accuracies is always fun.