One thing that my grad advisor used to emphasize is “failing fast”. That is, for every problem of the form “Is it possible to do X?”, there is a dual problem of “Can you prove it’s not possible to do X?”
Before spending far too much time on the first question, it’s worth it to spend a little bit of time on the second: what’s the quickest way to show that this can’t possibly work? Often this takes the form of looking for statements such as “If X worked, then Y would work too”, and then you go test Y. Just because Y holds, doesn’t mean X does… but if it doesn’t, you know X doesn’t.
It can feel like a bit of a diversion in the moment (“why am I wasting my time with Y, when I really care about X?”) but it has saved me months, possibly years of going down rabbit holes in my career. Likewise, it definitely helps with that anxiety you mention, because it means I at least have some motivation that my idea isn’t completely crazy.
Love this comment because it translates so well to any mentally taxing endeavor. Writing a long-running program? Set a few assertions up front so that it fails immediately before wasting your time. Think about those "failure" condition assertions up front and save your time on practically any experiment. Even chess players do this by surrendering early when they know a game has reached a conclusion.
+1...but this may be better advice when you don't have any anxieties/paralysis about the problem than when you do. Turned-out-that-it-was-overconfident approaches to problems have probably wasted far more time than anxieties/paralysis has.
Peripheral to this, some of my best refactors have come from trying to document why we can’t do X, explaining that we can’t do X because of Y, and realizing that Y does not need to exist.
There comes a point where explaining why we can’t have something is more painful than just fixing it.
This is also a useful technique to validate a new product before committing too many resources building it. Imagine that you have built it technically flawlessly but it's not selling copies. Why might that be? Draw up a list of reasons and test each of those as hypotheses before you build the product itself.
Something similar we do at work is write a quick document on why something isn't possible.
A bug can't be reproduced? Take a video of it working fine, and show the logical path for how the bug couldn't happen.
Can't build X in 3 months? What's the minimum for X? What's the missing component that takes 2 months? We can't have a partnership with A, but why wouldn't it be possible to have a partnership with A's competitor?
A risk to this approach: if you (or someone working for you, who is trying to tackle a problem) starts to externalize the motivation to solve the problem, optimization may start to favor 'failing fast' rather than pursuing best approaches (e.g. there's only one chance to try something per day, and you/they develop a pattern of pursuing the simplest possibility because it takes the least research and thus makes for the easiest increment of work day.)
This is possibly a risk, but it's not one I've ever seen play out. I don't think most people favor failing fast. It's something you do because it's good practice, while crossing your fingers that it doesn't fail. I think this is because in order to prove that something doesn't work, you first have to come up with that something -- deciding on a problem and thinking of a potential solution. While some people might find it fun to disprove other people's ideas, I don't think most really find it satisfying to disprove their own.
I think the bigger risk to this approach is that it can be disheartening and demotivating to see your ideas that you already got attached to and were looking forward to pursuing shut down. But it's still less demotivating than spending a year on it before watching it fail.
I had a group working under me who were troubleshooting an intermittent fault in some control circruitry for a nuclear reactor, and they started phoning it in just like this when they realized that there was only enough appetite to describe and propose weird problems to the boss once each day. After about a week, the goal became achievement of the daily failure with a minimum of preparation. It was a highly solvable problem, but they were all avoiding the necessary step of serious research.
That's reasonable. I think being in the academic world, I don't see it as often because daily achievement isn't really rewarded -- it's all about individual output in the longer term (manuscripts, grants, etc. ), and every "failure" feels like a step away from having a completed manuscript, even when it's necessary. If anything, it's why a lot of academics tend to avoid the "fail fast" techniques, because at a daily level, it feels more productive to be working towards a solution (even if it is a waste of time) than shooting down potential solution after solution.
I had a function that performed a 256-bit division. I thought there was a good chance it could be optimized, because the dividend was fixed: the function computed 2^256 / d. Surely, if the dividend was always the same (and such a nice, power-of-2 number!), there should be a way to exploit that, right?
I poked at it for a few hours before it occurred to me that I could ask someone else who knew a lot about division. So I cold-emailed Daniel Lemire. He replied with the following argument:
Suppose you had an algorithm that could compute 2^k / d much more efficiently than the typical algorithm. You could then use this algorithm to speed up any division n / d, by rewriting the expression as (n - 2^k)/d + 2^k/d. This works because both dividends will now be less than 2^k, and division algorithms get faster as the dividend gets smaller.
In other words: it's not impossible that there's an efficient algorithm for 2^k / d, but if it does exist, then all the people who have dedicated their time to optimizing integer division over the years have missed some enormous low-hanging fruit.
That was compelling enough for me, and I gave up trying to optimize my function. :)
Appeal to authority is only a fallacy when the person is an authority in an unrelated area. Appealing to an actual authority of the subject in question isn't a fallacy—it's the whole point of having authorities.
"90% of dentists agree you should own a motorbike" is an appeal to authority fallacy.
An appeal to authority is any logical argument that relies significantly upon the authority of the person making that argument as support for that argument. It then becomes circular and flawed.
If you were to replace the person who is actually speaking with anyone else, and look at the same argument and its support, and it doesn't hold up, that's an appeal to authority.
It doesn't matter who the authority is. Just that there was an authority used to support a significantly unsupported argument
> An argument from authority (argumentum ab auctoritate), also called an appeal to authority, or argumentum ad verecundiam, is a form of argument in which a claim made by an authority on some topic is used as evidence to support one's own claim.
Further down:
> Historically, opinion on the appeal to authority has been divided: some hold that it can be a valid or at least defeasible.
You seem to be arguing for appeals to authority as defeasible.
Incorrectly understanding the authority you are quoting shows how problematic it is to make pure appeals to authority.
Lol. But seriously appeal to authority fallacy need not be only when the authority is outside their domain. For instance when authority makes a bad argument.
The dividing line here is that it's fallacious to argue that something is true simply based on authority. That doesn't hold where there are external cogent reasons for following that authority (eg. in this example: it's a difficult problem that's well studied by many, and the body of work has not yet yeileded an answer such that it's unlikely that a more casual hunch will do so).
I'm not saying that this type of proof was applied perfectly here, however, the notion of proving that solving problem X must be hard because solving it would solve problem Y, which is (at least for now) known to be hard is a fundamental methodology in the field of computational complexity theory. There is a strong academic basis in these types of lines of reasoning, specifically in computing and optimization.
I'm not a trained computer scientist but didn't Daniel Lemire (purportedly) answer a different question from what OP asked? In OPs question k is fixed, wouldn't that open up avenues to implementation different from when k is not?
I can see why you puzzled over this. I’m not sure I agree with the guys argument — seems more like that there isn’t asymptotically better algorithm. It’s not convincing to me that there isn’t one division algorithm that’s a constant factor better.
IIRC you are correct, there are one or two spots in the Knuth division algorithm where having a power-of-2 dividend lets you eliminate a shift or an addition or something -- but nothing (nothing obvious, at least!) that yields a significant speedup.
One thing I like to ask myself is how did things get to be the way they are?
>all the people who have dedicated their time to optimizing . . . over the years have missed some enormous low-hanging fruit.
When I was a teenager one of my most worthwhile early chemical breakthroughs as an undergraduate was a typical lesson (these are dubbed "experiments") where students produced a product from raw materials and were evaluated on their final yield of acceptable recovered product, compared to the theoretical amount that could be obtained if perfection were to be achieved across all steps in the reaction and subsequent processing & handling.
This was a reaction that was known not to go very far to completion when equilibrium was reached to begin with, so most emphasis was placed on technique for subsequent separation and purification of the desired product recovered afterward. Good yield was considered 25%, poor at 10% or less, the historical high score was 27%. It was also accepted that the final product was not considered very stable, subject to degradation from exposure to things like heat, air and moisture, and there were some literature references this was based on.
Basically an overall view of the combined laboratory techniques applied across the study, compared to how the other students were doing. The product was not actually a commercially useful material but it had proven worthwhile in this regard.
The university had been doing this same challenging competition for decades, designed back then by a still-active professor, and it was considered a good comparison of how each year's students were performing on the same real-world problems over the decades. Same old same old.
I went through it one time and it came out pretty good, but before refining my technique I dived a bit deeper into the physical properties of all chemicals involved, in my case looking for a way to drive the equilibrium further to begin with.
One of the well-known ways to drive reversible reactions to completion is to remove product as you go along, not always easy but also quite essential in many industrial processes.
Seemed to me distillation would be most feasible except the product was a solid and one of the raw materials was a liquid having a known boiling point, much lower than the expected boiling point of the dissolved solid raw material product in the reaction flask, and the solvent much lower in boiling point than that.
Ended up vacuum distilling from the incompleted reaction flask where the water of reaction was removed along with the solvent, "excessive" heat actually helped complete the reaction before the remaining lower-boiling raw material was vaporized, and the desired solid product had a lower boiling point under vacuum while melted than the remaining "heavy solid" raw material, and the good stuff was recovered in over 50% yield as an oil in it's own dedicated receiver, which crystallized wonderfully by itself with no further purification needed. Earned me my first A+ and encouraged me to continue going further than average ever since.
Turns out all the original professors were wrong about heat instability, and also had never fully considered as many physical properties of the exact chemicals being worked with, only similar materials for which there was much more common knowledge and published references.
The final lesson was that sometimes the most respected elements of "common sense" amount to more or less "common lack of sense".
Also, I've said this before, when all recommended solutions have been attempted and failed to deliver, the actual solution will be something that is not recommended.
I often approach this from a “upper bound” and “lower bound” scenario perspective. So suppose I am trying to extract a signal from data that is noisy and sparse. Often the most time consuming part of solving the problem is figuring out how to deal with all of the noise, and I don’t want to waste time doing that just to come up with nothing in the end.
A “upper bound” approach would be to simulate some data that is perfectly clean and meets all my model assumptions, and test my basic method on it. If it doesn’t work on the clean data, it won’t work on the noisy data.
The “lower bound” approach would be to try the simplest and dumbest thing I can think of to deal with the noise in the real data. If I can pick up some amount of signal even with the dumb approach, it makes me much more confident that if I spend time making a sophisticated noise model, it will be worth it.
Probably not quite what you wanted, but P=NP. When you look at what does that imply then it's hard to think that it holds.
Scott Aaronson has a checklist on how to quicky reject a P?=NP paper, and one of the best methods is to check whether the paper proves something weaker first.
Back off the envelope calculations can usually quickly tell you if something is possible or not.
For physical problems. Newtons law of conservation of energy is an obvious first sanity check. Given some objects mass and the desired travel, you can get the required energy and from there the required power. Before you even start designing a prototype.
In formal logic, it is known as "modus tollens"... if 'if x then y' is true, then 'if not y then not x' is also true. The inverse is not necessarily true, however: 'if x then y' does not mean 'if y then x'.
In the case of a an X that is hard to figure out on its own, and it is easy to figure out Y, then it might be worth testing Y first, even if you will only get useful information if Y is false.
Let's say you're trying to figure out whether you left your coat at work. You could drive to the office and look for it there, and that will definitely tell you the answer. But if you look in your closet at home, then you know that the coat is definitely not at work, so you're done.
If you don't find the coat in your closet, you will don't know whether you left it at work. It could be in your car or maybe you left it on the train. But it's still worth checking your closet first because that gives you an early possible solution.
In logic, that's: If coat is at work, then closet is empty.
X = "Coat is at work".
Y = "Closet is empty".
Modus tollens tells us that "If X, then Y" implies "If not Y, then not X." So: If closet is not empty, then coat is not at work.
Well, assume you have a very, very efficient algorithm to check if normal boolean expressions have a solution. It checks some constant number of things for each variable, and then outputs a solution and it works for a large number of things.
Using the same logic as the parent comment, I would be very suspicious of the general applicability of this algorithm. Because, if this algorithm was correct, P would be equal to NP based off of this algorithm, because you'd have a polynomial solution to SAT. This, in turn, would invalidate pretty much all practical cryptography, most likely turn bitcoin on its head, and cause a significant number of other disruptions.
That is this line of thinking. The formal name is Modus Tollens, but it basically says: If your assumption is right, I can propose a much more preposterous assumption that would also be right. Or I could propose something enabled or validated by your assumption which is much easier to invalidate.
I constantly use this in stupid security discussions as well. There are so many people asking about silly threat scenarios, but the specific threat scenarios generally imply that an attacker already has control of critical infrastructure anyway, and all of these nitpicky things they wonder about are just not relevant. Like, if you assume this action to be possible, they have control of the secret management solution, and then we are doomed already.
An example of how you could fill this in: identify a small subset of the problem that is relatively quick and easy to test. If the entirety of the problem can be solved, then for sure this small subset has to be solvable too. If you can't solve this small sub-problem, then you know there's not much point diving into the larger rabbit hole yet. However if you do solve the sub-problem, then that might show you the potential that exists, it may allow you to already look at adjacent problems using the results of this early test, and also important: it will give you additional motivation to keep going.
Contrapositive (if ~Y, then ~X) is logically equivalent to the original implication (if X, then Y). Instead of proving the latter, you can prove the former contrapositive.
Before spending far too much time on the first question, it’s worth it to spend a little bit of time on the second: what’s the quickest way to show that this can’t possibly work? Often this takes the form of looking for statements such as “If X worked, then Y would work too”, and then you go test Y. Just because Y holds, doesn’t mean X does… but if it doesn’t, you know X doesn’t.
It can feel like a bit of a diversion in the moment (“why am I wasting my time with Y, when I really care about X?”) but it has saved me months, possibly years of going down rabbit holes in my career. Likewise, it definitely helps with that anxiety you mention, because it means I at least have some motivation that my idea isn’t completely crazy.