Geek Squad

Gregory Smith21 said:You’re mistaken—and honestly, a little harsh. I know my stuff—everything from tackling n-th order differential equations to coding in Assembly, but hey, that's beside the point.

Can you actually write an Assembly program that solves a basic first-order differential equation? You know, where the input f(x, y) is continuous and the output is the set of all solutions for something like u' = f(x, u).

That was refreshing ☕

bluebadger112 said:Do you know how to write an Assembly program that solves a standard first-order differential equation? You know, where the input f(t, u) is continuous, and the output is the set of all solutions in t, such that u' = f(t, u).

That sounds quite interesting ☕

Yes, I suppose that is certainly possible. In any programming language, you are provided with basic mathematical operations, and by combining those fundamental functions, one could theoretically solve complex functions, including differential equations. Since there aren't built-in operators specifically for integration or differentiation, I guess you would have to combine those core arithmetic functions—like add, sub, div, and Mul eax—to eventually reach that goal.

I believe the critical part is ensuring the program includes a conditional function where you define which functions to differentiate via a lookup table, or perhaps just through standard comparisons using cmp.

Most people would probably choose to do this in a higher-level programming language because it seems much simpler. To solve an equation like that, you might end up writing countless lines of code in Assembly, whereas in something like Java, you would likely need significantly fewer. Still, I suppose it is really just a matter of time and effort.

One could even attempt to build it directly in a hex editor, provided they truly know what they are doing and happen to be a bit of a masochist. 😬

Personally, I feel that Assembly is more suited for writing drivers and kernel development, which is where my own interests primarily lie.

Gregory Smith21 said:Yeah, totally—every programming language has those core math operations built in. You can basically stitch those basic functions together to tackle complex stuff like differential equations. Since you don't have dedicated operators for integrating or deriving, you just have to combine the basics—like add, sub, div, and Mul eax—to get where you need to go.

All that matters is that the program includes a conditional function—you just define whether you're deriving functions via a lookup table or the standard way—and then let the cmp handle the comparison.

Most people just stick to high-level languages because they're way easier—I mean, solving an equation like that takes dozens of lines in Assembly, whereas in something like Java, it’s much more concise. It really just comes down to how much time you have to spare.

You could always whip it up in a hex editor—assuming you actually know what you're doing and have a serious masochism streak. 😬

Assembly is really more for writing drivers and kernel development—which happens to be exactly where my interests lie.

I'm not sure we were quite on the same page there—I wasn't actually talking about an algorithm that derives or integrates functions. I meant one that returns functions where the derivatives possess a specific property—in this case, $u' = f(u)$ for a given input function $f$. Such an algorithm doesn't need to perform any differentiation or integration, nor does it need to check if the result satisfies the required property (since the algorithm's own correctness proof handles that part). Of course, in practice, an algorithm like this won't return the exact solution—there's just too much data involved, and you run into the classic issue of trying to evaluate a function at infinite points on a computer, which is impossible. But, if you set a specific tolerance, it will find a function that stays within that distance from the true solution (uniformly). If you want to dive deeper, look into the derivation of Peano's theorem; understanding that is pretty much a prerequisite for implementing and proving the correctness of an algorithm like this. Otherwise, there are numerical algorithms out there that can solve practically any partial differential equation, provided you're okay with a tiny bit of error.

bluebadger112 said:Hmm, I suppose we might not have been fully on the same page here. I wasn't actually referring to an algorithm that performs differentiation or integration of functions, but rather one that returns functions whose derivatives possess a specific property—in this case, $u' = f(u)$ for a given input function $f$. Such an algorithm doesn't necessarily need to differentiate, integrate, or even verify if $u$ meets the required criteria, provided that the correctness of the algorithm itself guarantees that result. Of course, in a practical sense, such an algorithm generally won't return the exact solution due to the inherent limitations of finite data, which leads to a significant number of hurdles (most notably the impossibility of evaluating a function at an infinite number of points via computer), but for any pre-defined distance, it will find a function that stays within that margin of the true solution (uniformly). If this subject interests you, perhaps looking into the derivation of Peano's theorem might be helpful, as understanding that concept is probably a minimum requirement for implementing and proving the correctness of such an algorithm. Beyond that, there are numerical algorithms capable of solving practically any partial differential equation, albeit with a small degree of error.

It seems to me that finding an exact solution through computer computation is often impossible for certain things, so approximation becomes the necessary route. Even simpler concepts than differential equations require approximation, such as calculating the square root of 2, for instance.

Through programming, one can calculate these types of differential equations, though they remain bounded within a specified interval. For example, using the Euler method, you define your variables and increase them by increments, which should ultimately yield an approximate solution.

For most practical applications, I guess an approximation is more than sufficient.

Everything in a computer is just an approximation—unless we're talking about symbolic repositories, of course. At the end of the day, representing a real number on a machine is really just storing its approximate value.

Proving that Euler polygons actually converge uniformly toward the solution—which is basically the heart of the Peano theorem proof—is no small feat. That said, Euler polygons aren't exactly the best tool for approximating over wide intervals; the error margin depends heavily on the interval width, and apparently, some other methods get bogged down by that issue too, though I don't know much about them.

bluebadger112 said:Everything is essentially an approximation within a computer, unless one is working with certain symbolic repositories. I suppose the way a real number is represented in a computer system is actually just its approximate value.

The proof showing that Euler polygons truly converge uniformly toward the solution—which happens to be the core component of the Peano theorem proof—is quite non-trivial, I believe. On the other hand, Euler polygons might not be the most practical choice for approximations over broad intervals, since the proximity estimate to the exact solution seems to depend on the width of the interval itself; I think there are other methods that handle this better, though I am likely not familiar enough with them to say for sure.

As we input numbers with more decimal places into the function, up to a certain point, the graph becomes more clearly defined and the results become more precise.

In this regard, the computer is absolutely indispensable. One could manually calculate a specific interval, such as [1,5], provided we use a step size of, say, 0.2, but for a significantly more accurate result, it would probably be best to calculate that same interval using a step size of perhaps 1*10^-6. If we were attempting to do that by hand, it would likely take an incredibly long time. With a computer, however, you can resolve this in an instant and obtain a much more well-defined graph.

Gregory Smith21 said:If you plug in numbers with more decimal places—up to a certain point—you get a much sharper graph and way more precise results.

Computers are honestly indispensable here. Sure, we could manually calculate an interval like [1,5] by using a step size of, say, 0.2—but if you actually want precision, you’d need that same interval with a step size closer to 1*10^-6. Doing that by hand would take forever. With a computer, you knock it out in a second and end up with a much sharper graph.

The more points you use to evaluate a function, the smoother that graph looks—pretty much a given.
You can only evaluate it using a finite number of points, really. The accuracy of how close the Euler polygon gets to the actual solution depends entirely on the length of the interval. Specifically, if $l$ is the interval length, $f$ is locally Lipschitz in the second variable, $v$ is the Euler polygon, and $u$ is the true solution—you get a uniform estimate $|u - v| < cM(l)$, where $M$ is some strictly increasing function, $c > 0$, and $v$ depends on $c$. Basically, that means choosing the Euler polygon depends on picking a specific positive constant upfront. So, the larger the interval, the worse the estimate gets—meaning you have less of a guarantee that the Euler polygon stays close to the real deal. Sure, you could just pick a tiny enough $c$, but then the sub-intervals needed to define $v = v(c)$ might end up being way too many for a computer to handle.

bluebadger112 said:I suppose you're right that evaluating a function at more points results in a denser representation of its graph. That seems to be the case.
However, one can only evaluate it at a finite number of points. The accuracy of how closely an Euler polygon approximates the actual solution depends heavily on the length of the interval. Specifically, if $l$ represents the interval length, $f$ is locally Lipschitz with respect to the second variable, $v$ is the Euler polygon, and $u$ is the solution to the initial value problem, then we have a uniform estimate $|u - v| < cM(l)$, where $M$ is a known strictly increasing function, $c > 0$, and $v$ depends on $c$—meaning the selection of the Euler polygon is contingent upon a pre-established positive constant. Consequently, as the interval grows larger, the estimate becomes less reliable; the guarantee of proximity between the Euler polygon and the true solution diminishes. Now, while one could theoretically choose a sufficiently small $c$, doing so might result in an interval distribution for defining $v = v(c)$ that contains far too many segments for a computer to handle efficiently.

It might indeed involve too much data for a computer, though I guess it really just depends on how the program is structured and what kind of processor is being used.

Whether we are dealing with a 32-bit or 64-bit architecture makes a significant difference. Individual mathematical operations are limited by the register capacity of a specific processor. Even during a very basic addition, we encounter these constraints. With 32-bit systems, a single register holds a maximum of 32 bits, which essentially means a maximum input of 4 ASCII characters per register. For 64-bit, it would be 8 ASCII characters.

With 32-bit, the maximum arithmetic processing you can perform involves a four-digit number per operation.

For example,

mov eax, [num1]
sub eax, '0'

mov ebx, [num2]
sub ebx, '0'

In this scenario, the maximum values for num1 and num2 would be 9999. Anything beyond that leads to a buffer overflow, causing the program to crash.

I imagine this issue could be resolved by "splitting" any number larger than four digits and processing them individually.

The situation regarding division and Mul eax is quite similar.

Mul eax, num1

Where the product is split into two segments: Edx serves as the 32-bit high-order segment and eax acts as the 32-bit low-order segment. If the maximum for each register is 9999, exceeding that will trigger a buffer overflow.

If we were to use a constant $c$ that is, say, 0.000000000000000001, we wouldn't calculate it directly as 0...1; rather, we might treat it as 1 and then format it as 0...1 when printing. Such a process requires additional functions because we cannot compute it all at once in a single step due to the massive discrepancy between the number of ASCII characters and the capacity of the processor registers.

In any mathematical software—whether it's something like GeoGebra or WolframAlpha—the underlying processes remain the same. For every complex operation, variables are segmented into smaller parts, which are then processed either serially or in parallel, segment by segment, until the final product is reached.

Gregory Smith21 said:It could be too much data for the machine—it really just comes down to how you write the code and what kind of processor you're running.

Yeah, that’s definitely true—but you can always pick a constant so small that the computer can't even handle it, meaning it just sees it as zero. Honestly, you could fill the entire universe with the fastest parallel processors and memory imaginable, and still choose a constant that's just too tiny. 😁

What I find interesting, though, is the idea of optimal algorithms. Take a meaningful problem that belongs to a non-empty class of algorithms designed to solve it—there's always going to be an algorithm in that group with the best complexity, basically the one that's asymptotically the fastest. For instance, when sorting $n$ items, we know the best complexity for that class is $O(n \log n)$; researchers actually built several algorithms with that complexity and mathematically proved nothing can be "faster."

Then you have these algorithmically solvable problems where finding an optimal algorithm is questionable—maybe even theoretically impossible—even though we know one must exist! And for some problems, we don't even know what the best possible complexity would be, which is its own kind of headache.

When we actually know what the optimal complexity is, the goal shifts to shrinking that constant inside the Big O notation—and people spend a ton of energy trying to do exactly that and publishing their results.
It’s also pretty wild that there are problems solved by non-optimal algorithms that actually turn out to be faster on average in real-world practice than the "optimal" ones. Sorting is one of those cases.

The core question will always be: Can we do better?

EDIT: I used the word trivial earlier, but now I'm wondering if every meaningful problem actually has an optimal algorithmic solution. 🤔 Sure, for a given input, it does, but that doesn't feel like a complete answer to me. 🤔 Man, you really dug deep into this one. ☕

bluebadger112 said:Yes, that is an undeniable truth, though one could always select a value for c so infinitesimally small that a computer simply cannot handle it... essentially, it would perceive it as nothing more than zero. You could fill the entire universe with the fastest parallel processors, massive amounts of memory, and whatever else you can conjure, yet still choose a c so minuscule that it renders everything moot. 😁

What I find truly compelling, specifically regarding optimal algorithms, is this... suppose you have a meaningful problem with a non-empty class of algorithms designed to solve it. In such a case, there trivially exists an algorithm within that class possessing the best complexity, which is to say, it is asymptotically the fastest possible. For instance, in the problem of sorting n pieces of data, the best complexity for the class of all solving algorithms is known to be O(n*log(n)); several algorithms of this complexity have been constructed, and it has been mathematically proven that nothing "faster" can exist.

However, there are algorithmically solvable problems where the actual constructibility of an optimal algorithm is questionable at best, and quite likely theoretically impossible—even though we know without a shadow of a doubt that such an algorithm does exist! For certain problems, we don't even know what the best complexity of an optimal algorithm might be, which is a different kind of frustration entirely.

When dealing with problems where the optimal complexity is already known to us, the remaining task becomes reducing that constant factor involved in the O-notation, and people actually spend quite a bit of time using various clever tricks to do just that and then publish their findings.
It is also quite fascinating that there are problems solved by sub-optimal algorithms which, in practical applications, have turned out to be faster on average than the supposedly "optimal" algorithms for that specific problem. The aforementioned sorting problem is one such example.

The central question will always remain: Can we do better?

The sorting problem is rather intriguing... once, purely out of boredom, I found myself programming various algorithms and sketching out how they function just to help clarify things for my students. Within the realm of OOP, there isn't really much need for that, as I believe the sort class in C# utilizes Quick sort... or perhaps it doesn't, I am not entirely certain.
Here is a clever visualization of how various sorting algorithms operate: 😁
https://www.toptal.com/developers/sorting-algorithms

Programming is actually secondary to me; I view it as a supplementary skill, something I possess in case I need to upgrade or modify something... since my primary work involves various data processing algorithms, well...
There is always room for improvement, naturally, but the real question is merely when a marginal shift becomes interesting enough to justify the effort... 😁

Well, there isn't any, which is why "soft" methods and approximate solutions exist, as they are often more than sufficient.

northernviper4 said:? XD

🤣 That wasn't really your fault 😁 Yep, QS is actually an algorithm where the asymptotic complexity is worse than the optimal one—but in practice, it's faster. If I recall correctly, its worst-case complexity is O(n^2), which isn't great. But the expected complexity is n*ln(n).

bluebadger112 said:🤣 That wasn't really aimed at you... 😁 Yep, QS is actually an algorithm where the asymptotic complexity is technically worse than the optimal version, yet in practical applications, it often outperforms them. If my memory serves me correctly, its worst-case complexity is O(n^2), which is significantly worse... though the expected complexity remains n*ln(n).

Actually, no, bluebadger112, why don't you just start a new thread? An extreme geek debate, or maybe even your own dedicated corner... we could hang out there once in a while so we aren't exhausting everyone else with these empty, trivial discussions...☕

bluebadger112 said:Yes, I suppose that is quite true, though one could always select a value for c that is sufficiently small such that the computer simply cannot handle it, effectively recognizing it only as zero. It seems to me that even if you were to fill the entire universe with the fastest parallel processors and massive amounts of memory, you could still choose a c small enough to cause this issue.😁

That is precisely why a value like 0.0...x is treated as a natural number initially, only to be printed later as 0.0...x; it happens because the system might otherwise just perceive it as zero.

For instance, if you enter the number 12345678, a 32-bit processor would temporarily store it in a buffer.

A number of this magnitude would occupy two memory blocks.

0x00000004: 8765

0x00000008: 4321

Afterward, the values are retrieved from the buffer using a LIFO—or last in, first out—system.

Depending on whether the processor is 32-bit or 64-bit, an input like 0.0...x would result in the number being stored in memory blocks containing 4 or 8 digits respectively.

The intention when dealing with a very small c is to segment the memory blocks by increments of one rather than 4 or 8, which allows us to monitor the state of every single segment.

For example.

Let us look at the previous example.

0x00000004: 8765

0x0000008: 4321

If we were to segment these memory addresses at the smallest possible increment—that is, an offset of 1—we could track the status of the addresses, which is more useful for subsequent operations.

0x00000004: 8765

0x00000005: 7654

0x00000006: 6543

0x00000007: 5432

0x00000008: 4321

With every increase in the memory address, the input shifts one ASCII character to the left until the end of the input is reached.

In the case of a tiny c, we deal with 0.0...x. The first thing the program needs to do regarding 0.0...x is determine the "0," which is accomplished by using a cmp instruction to compare 2c (the hex value for the decimal point) with 2c; once we get zero, we execute a conditional jump to a subroutine.

Within that subroutine, we compare the values following the decimal point until we reach x.

Take 0.00000005, for example.

Once the 0 has been isolated via the cmp and the comparison of 2c, we begin analyzing the remaining 0...5.

The goal is to isolate either the final digit or the start of the first natural number at a specific decimal place, continuing all the way to the end to derive a natural number. Arithmetic operations are then performed on that number as if it were a standard natural number, and it is subsequently printed as 0.0...x.

This approach is taken specifically to prevent a situation where a computer might recognize a number with too many decimal places as being zero.

This is just one method to circumvent that particular problem. However, I suppose even then, the resulting value would be nothing more than an approximation, albeit perhaps a slightly more precise one.

bluebadger112 said:Well, I don't know... if someone doesn't want to read, they can just squint... ☕ Unless Wolf shows us he's actually handsome, or things change quickly and our little Geek Squad posts start becoming interesting to the masses. Fine, it's his bar, we'll just follow his lead... ☕

You’re saying there’s a problem where an optimal algorithm simply doesn't exist, or perhaps it can't be proven to exist, or maybe it just can't be constructed at all... That really caught my attention today. Do you have any literature you could recommend so I might look into it further?

Vuče 👋

Are we discussing: 1) algorithms for optimization problems, 2) regarding optimal solutions for specific problems, 3) optimality itself—meaning the performance of algorithms when applied to certain tasks—or 4) all of the above combined?

Existing algorithms for optimization problems will exhibit various levels of performance depending entirely on the nature of the problem at hand. The sheer scale of Big Data has reached a point where classical optimization algorithms become practically useless unless they are heavily modified and adapted for parallel or distributed computing environments, and currently, the cutting edge has moved toward optimizations supported by quantum computing.

As far as actual optimal solutions are concerned—if a problem is defined and a sequence of appropriate algorithms is selected, the resulting solutions often aren't different enough to matter in a practical application. In the real world, true optimality is almost never achieved. Take optimal manufacturing, for instance...
When we discuss algorithmic performance regarding a specific problem, specifically concerning time complexity and computational resource requirements, it frequently turns out that one algorithm is more efficient for one particular problem, while a completely different algorithm excels at another.
The most trivial examples are state-space search algorithms—finding the optimal path. An algorithm's efficiency depends most heavily on the parameters set for the problem itself, which means that often, the simplest algorithms are actually more efficient... such as Breadth-First Search with uniform cost compared to its more complex, improved version, the A* search.

In short, among existing algorithms, there is always one that is currently considered optimal or most efficient for a specific problem, yet the possibility that a better one exists is certain; it is merely a question of economic feasibility and whether such minute improvements are truly necessary. Furthermore, as storage and processing technologies evolve, the potential for improving algorithmic performance continues to expand...

Regarding literature, tell me specifically what interests you and I might find something... You can also send me a private message if you'd prefer I didn't post here.
Of everything discussed, the most tragic part is how no one seems to see the opportunity to learn something new or even ask a question when they absolutely don't understand something. It makes one wonder if people actually care about upgrading their knowledge at all. But then again, those are the same people who feel mathematics and its related fields are irrelevant because they think, "Oh, well, if no one ever asks me about this, it isn't used anywhere"... failing to realize they are actually daily victims of such algorithms... 😬

2) 😁 More specifically—using the notation I pulled here—is it true that for any solvable "problem," there's an algorithmic O(f) solution where every possible solution to that problem is also at least Ω(f) (per Knuth’s Ω)? For instance, sorting $n$ objects has an $f(n) = n \log n$ solution, while summing the first $n$ integers is just $f(n) = 1$...

bluebadger112 said:2) 😁 It would be more precise if we utilized the notation that was adopted... Right here...Does every algorithmic "problem" that possesses an $O(f)$ solution also inherently require at least an $\Omega(f)$ solution... essentially implying that the complexity class is tightly bound by $f$ according to Knuth’s $\Omega$ notation? For instance, we know sorting $n$ objects yields such a result where $f(n) = n \log n$, and calculating the sum of the first $n$ natural numbers settles at $f(n) = 1$... or perhaps I am oversimplifying the nature of the lower bound...

Well, it appears we have finally arrived at the green frontier... 🙂
The persistent tension between mathematical terminology and computer science nomenclature continues to be a subject that warrants a much more rigorous examination than most modern academics seem willing to provide... It is a divide that feels increasingly wide, almost cavernous, as we drift further into an era where the two disciplines are forced into a marriage of convenience, yet they speak entirely different languages... One finds themselves navigating a landscape where a term used by a pure mathematician might carry a completely different weight—or perhaps no weight at all—when uttered within the halls of a software engineering firm or a high-frequency trading desk in Chicago... There is this fundamental friction, this constant tug-of-war between the abstract elegance of a proof and the gritty, practical necessity of implementation... A mathematician seeks the absolute truth of a structure, while the programmer is often just trying to ensure the system doesn't crash when the input hits a certain threshold... It leads to these peculiar moments of confusion during an extreme geek debate, where one party is discussing the intrinsic properties of a set, and the other is merely concerned with how many bytes that set will occupy in memory... It’s quite frankly exhausting to witness such a lack of linguistic synchronization... One would hope that as the fields converge, we might see some semblance of a unified lexicon, but I fear we are merely layering complexity upon complexity without ever truly reconciling the underlying concepts... 😁
That is certainly an intriguing question, one that I have quite honestly never encountered before... It makes one wonder, though, what exactly serves as the common thread among all those issues that typically plague such a solution? 🤔 Perhaps there might be some academic papers out there regarding this matter... I wonder if you have direct access to the various scientific databases and scholarly repositories used by major research institutions...

Sent from my BLN-L21 via Tapatalk

josuha said:I’m asking the two most charming ladies on this forum to weigh in—I have a few things on my mind. 🍿

chic fight? 🍿
I've always had an affinity for math and CS—even if I haven't touched algorithm complexity analysis in quite some time.
What was your experience like working with 2D pathfinders?
https://www.geeksforgeeks.org/count-...ht-nxm-matrix/
Some tech firms in the States actually use this kind of thing as a standard job assessment. 🍿

The optimization of moving from point A to point B. 😁

Anthony Nguyen81 said:chic fight? 🍿

I have always had a certain fondness for mathematics and computer science, though I must admit it has been quite some time since I last found myself deeply immersed in analyzing algorithmic complexity...

What kind of work were you doing with 2D pathfinders?

https://www.geeksforgeeks.org/count-...ht-nxm-matrix/

Certain tech firms in the States actually utilize this sort of thing as a standard job assessment... 🍿

The optimization of navigating from point A to point B... 😁

These are quintessential problems, really; I frequently walk my first-year university students through them using various different algorithms... 😁

During my very first job interview, I recall being presented with a problem that I eventually resolved using a decision tree based on probabilities to calculate the net present value of several different options. It was almost exactly like the exercises we used to run through in class... so, I suppose I don't mind seeing these types of questions pop up during interviews... 😁

northernviper4 said:These are classic hurdles—I actually work through these exact scenarios with my freshmen when we dive into various algorithms. 😁

During my first job interview, I was thrown a curveball—a problem-solving task that required using decision trees paired with probabilities to calculate the net present value of several different options. It felt strangely familiar, almost like those textbook exercises you grind through in school—xD. Honestly, if they want to use those kinds of scenarios during interviews, I'm all for it. 😁

A colleague of mine went down to some federal agency to check things out—and ended up getting completely screwed over. 😁
It’s an intriguing puzzle—finding a path from one word to another by changing only a single letter at a time, ensuring every intermediate step remains a valid entry within a predefined dictionary.

Decision trees integrated with probabilities—that really is the only way forward. Period. 😬
He cobbled something together—but his initial solution failed to deliver any real-time results. 😬

Anthony Nguyen81 said:Well, a colleague of mine actually went in for an interview with some major federal agency, and they ended up dumping this 😁
on him...
It is a rather intriguing problem, really... finding a way to transition from one word to another by changing only a single letter at a time, while ensuring every step remains within a predefined dictionary.

A decision tree incorporating probabilities seems to be the only viable path if you want to 😬

He managed to cobble something together, though his initial attempt failed to provide results in anything resembling real-time... 😬

Honestly, that decision tree thing has nothing to do with the core issue... I only brought it up because it was an example of a task I encountered during a job interview myself... 🙂
What he’s actually looking at is state-space searching, and there are quite a few different algorithms available for that specific purpose.