> using the appropriate unicode characters might make it easier to read
It's probably also a great way to introduce almost undetectable security vulnerabilities by using Unicode characters that look similar to each other but in fact are different.
This would cause your compilation to fail, unless you were deliberately declaring and using near identical symbols. Which would violate the whole "Code is meant to be easily read by humans" thing.
Recently I tried to reinstall an eSIM on my Android phone while overseas but was told by my carrier that the eSIM can only be activated while connected to antennas located in the carrier's country, i.e. it can't be activated overseas, despite my plan supporting call roaming and both countries being in the EU.
I don't know whether this is carrier-specific or the same for all carriers.
This worked for me, French carrier "Free", and install new eSIM while in Spain.
But now I have doubts, especially outside the EU: if it doesn't work, that would loose one of the advantages that I'd sort of expected eSIM to have: if your phone gets lost / stolen while abroad, you could just get a new eSIM from your carrier immediately, and set it up on your replacement phone.
In my case, my bank uses mandatory SMS 2FA for setting up their app on a new phone, thus making it impossible to make purchases with my card without having the being able to set up the app.
So I'd be back to the oldschool method of having a fried back at home set up the new eSIM, receive the 2FA code...
I think almost all carriers require this. I've seen mentions that the Google Fi eSIM requires US towers to activate, but can be moved / reinstalled later without them (didn't test it though).
Just an end user, so don't quote me on this, but I think that requirement was largely a legacy Sprint requirement.
I've purchased newer Pixel devices from my local shop and activated Google Fi just fine overseas. (with the caveat that I might not have all of T-Mobile's bands if I'm back in the US).
Probably built by a web gency who added tracking, perhaps even GA, so there was need for a cookie pop up banner. Why that website would need tracking and profiling is beyond me.
I think every website should understand how and by who their website is used. I don't consider this "spying." If you walk into a brick and mortar store the shopkeeper has every right to count that you came in, and watch where you go in the store to optimize it. The web should be no different.
Fortunately there are in fact cookieless analytics systems that people can use to get this information why not being required to have the stupid cookie popup.
Yes, a brick and mortar store can absolutely profile you without consent if they wished, and so can a website. The only condition is not collecting PII.
> The asteroid in spring hypothesis suggests that the asteroid impact that led to the K-Pg extinction event, occurred during spring season in the Northern Hemisphere.
The significance is likely more about paleontological methods of time determination than it is about what the difference of the impact would have been had it struck during another season, though that could also turn out to matter.
A massive asteroid impact is a singular event, and most especially in the realm of geology and paleontology, where the minimum timespan of concern is frequently one million years, the notion that we have reasonably postulated that specific fossil finds can be pinned to the day of the event (there's a T. Rex find that seems to have occurred on the date), and then to identify when in the year that day happened to fall (based on specimens of fish and fauna found in a deposit timed to the impact) provides methodologies which might be used to confirm (or refute) the timing both of other K-Pg boundary finds, and of paleontological / paleobiological finds more generally.
What we don't have, mind, is a speific timing of the Alvarez impact. The current estimate, based on argon dating, is "66,038,000 years ago, plus or minus 11,000 years" (<https://en.wikipedia.org/wiki/Alvarez_hypothesis#Evidence>). Though that itself is pretty remarkably precise.
# If there are < 5 items, just return the median
if len(l) < 5:
# In this case, we fall back on the first median function we wrote.
# Since we only run this on a list of 5 or fewer items, it doesn't
# depend on the length of the input and can be considered constant
# time.
return nlogn_median(l)
Hell, why not just use 2^140 instead of 5 as the cut-off point, then? This way you'd have constant time median finding for all arrays that can be represented in any real-world computer! :) [1]
Big-O notation and "real-world computer" don't belong to the same sentence. The whole point of big-O notation is to abstract the algorithm out of real-world limitations so we can talk about arbitrarily large input.
Any halting program that runs on a real world computer is O(1), by definition.
So why would you want to talk about arbitrarily large input (where the input is an array that is stored in memory)?
As I understood, this big-O notation is intended to have some real-world usefulness, is it not? Care to elaborate what that usefulness is, exactly? Or is it just a purely fictional notion in the realm of ideas with no real-world application?
And if so, why bother studying it at all, except as a mathematical curiosity written in some mathematical pseudo-code rather than a programming or engineering challenge written in a real-world programming language?
Big-O analysis is about scaling behavior - its real-world implications lie in what it tells you about relative sizes, not absolute sizes.
E.g., if you need to run a task on 10M inputs, then knowing that your algorithm is O(N) doesn't tell you anything at all about how long your task will take. It also doesn't tell you whether that algorithm will be faster than some other algorithm that's O(N^2).
But it does tell you that if your task size doubles to 20M inputs, you can expect the time required for the first algorithm to double, and the second to quadruple. And that knowledge isn't arcane or theoretical, it works on real-world hardware and is really useful for modeling how your code will run as inputs scale up.
thank you for this explanation! to me it looks like the algo sorts the whole array but in groups of 5; the number of chunks should scale O(N/5) = O(N), no? so how can you claim just by chunking you can ignore the fact that you still sorted N elements e.g. a selection sort would still perform N^2 comparisons total.
Ah, so the issue here is the difference between quickSort and quickSelect. In both cases you pick a pivot and divide the data into two partitions - but in quickSort you then recurse on both partitions, and in quickSelect you determine which partition your target is in and recurse only on that one.
So you're right that dividing into chunks of 5 and iterating over them doesn't affect the scaling - you wind up with an array of (N/5) medians, and it's still O(N) to iterate over that array. But the next step isn't to sort that array, you only need to quickSelect on it, and that's why the final step is O(N) rather than O(NlogN).
> (where the input is an array that is stored in memory)?
If the input is an array that is stored in a piece of real-world memory, then the only possible complexity is O(1). It's just how big-O works. Big-O notation is an abstraction that is much much closer to mathematics than to engineering.
> this big-O notation is pretending to have some real-world usefulness...
Big-O notation is not a person so I'm not sure whether it can pretend something. CS professors might exaggerate big-O notation's real-world usefulness so their students don't fall asleep too fast.
> fictional
Theoretical. Just like the other theoretical ideas, at best big-O notation gives some vague insights that help people solve real problems. It gives a very rough feeling about whether an algorithm is fast or not.
By the way, Turing machine is in this category as well.
Ultimately when an algorithm has worse complexity than another it might still be faster up to a certain point. In this case 5 is likely under that point, though I doubt 2^256 will.
In practice you might also want to use a O(n^2) algorithm like insertion sort under some threshold.
> Ultimately when an algorithm has worse complexity than another it might still be faster up to a certain point.
Sure, but the author didn't argue that the simpler algorithm would be faster for 5 items, which would indeed make sense.
Instead, the author argued that it's OK to use the simpler algorithm for less than 5 items because 5 is a constant and therefore the simpler algorithm runs in constant time, hence my point that you could use the same argument to say that 2^140 (or 2^256) could just as well be used as the cut-off point and similarly argue that the simpler algorithm runs in constant time for all arrays than can be represented on a real-world computer, therefore obviating the need for the more complex algorithm (which obviously makes no sense).
If you set n=2^140, then sure, it’s constant. If instead you only have n<=2^140, then n varies across a large set and is practically indistinguishable from n<=infinity (since we get into the territory of the number of atoms in the universe), therefore you can perform limit calculations on it, in particular big O stuff.
In the article n was set to 5. All of those arrays (except maybe 1) have exactly 5 elements. There is no variance (and even if there was, it would be tiny, there is no point in talking about limits of 5-element sequences).
I'm not a Python expert, but doesn't the `/` operator return a float in Python? Why would you use a float as an array index instead of doing integer division (with `//`)?
I know this probably won't matter until you have extremely large arrays, but this is still quite a code smell.
Perhaps this could be forgiven if you're a Python novice and hadn't realized that the two different operators exist, but this is not the case here, as the article contains this even more baffling code which uses integer division in one branch but float division in the other:
That we're 50 comments in and nobody seems to have noticed this only serves to reinforce my existing prejudice against the average Python code quality.
Well spotted! In Python 2 there was only one operator, but in Python 3 they are distinct.
Indexing an array with a float raises an exception, I believe.
I do agree that it is a code smell. However given that this is an algorithms article I don't think it is exactly that fair to judge it based on code quality. I think of it as: instead of writing it in pseudocode the author chose a real pseudocode-like programming language, and it (presumably) runs well for illustrative purposes.
I didn't mean to suggest anything. I was just interested in whether they thought that remaining anonymous was in keeping with their ex-colleagues character. Written communication is hard!
I think I'm missing something... isn't there an error in the proof when applying the theorem of the principle of infinite descent?
The theorem requires proving the following premise/antecedent (to deduce the consequent):
∀x ∈ X. Φ(x) ⟹ ∃y ∈ X. y ⊏ x ∧ (...)
... but I don't see how this can be proved when x=0. By substituting `x` for `0` (and using Z as the set X and |<| as the well-founded relation) you get:
Φ(0) ⟹ ∃y ∈ Z. y |<| 0
Unfolding Φ:
(∃b ∈ Z. 0^2 = 2 b^2) ⟹ ∃y ∈ Z. y |<| 0
The antecedent of this implication is true (when b = 0), so now you have to prove:
∃y ∈ Z. y |<| 0
However, this can't be proved because no `y` satisfies the |<| well-founded relation when applied to zero.
Therefore, this article's sentence doesn't seem to be true:
> Having satisfied the premises of the principle, we use it to deduce that no `a` satisfies the property
... which in fact cannot be true, because `a=0` does satisfy the property `∃b ∈ Z. a^2 = 2 b^2`, does it not? Consider `b=0`.
So what am I missing?
Edit: in fact, if the theorem could be applied in this case, then the conclusion of the theorem would be:
∀x ∈ Z. ¬(∃b ∈ Z. x^2 = 2 b^2)
Which is equivalent to:
∀x ∀y ∈ Z. ¬(x^2 = 2 y^2)
... which is clearly false when x=0 and y=0. So it seems like the theorem of infinite descent cannot be used to reach this conclusion. Some kind of false assumption would have to exist, but no false assumption was used to instantiate this theorem.
It's not wrong, but it skips some detail. (It's ironic that an article about "insight via precision" uses such imprecise language.)
This is demonstrated in a Lean tutorial for induction, where first it has you "prove" that √2 is "rational", before adding the requirement that the denominator is not 0, which then of course requires a totally different (semantically valid) proof.
0 does satisfy the theorem on integers, but it doesn't say anything about √2, because rational numbers do not allow a 0 denominator.
The √2 theorem assumes b >= 1, and infinite descent / well-foundedness is based on this subset of Z (and to the author's pedantic point about ordering, also works with Z\{0} and the magnitude ordering on |z|.)
I would argue that technically, the proof has an error because the author says:
> Let X be the integers Z; for integers a,b, let `a ⊏ b` be `a|<|b`; and let the property Φ(a) be “a^2=2 b^2 for some integer b” (formally, `∃b ∈ Z. a^2=2 b^2`).
However, the theorem of infinite descent cannot be applied to this property with the set Z which the author specifically said he would use. Instead, it needs to be applied to the set Z\{0}, which you rightly pointed out (as well as the sibling poster).
Note that this has nothing to do with the rest of the proof about √2.
I do agree that even after this error is corrected, then the proof additionally needs to be fixed by adding a few more simple proof steps to analyze what happens when either `a` or `b` are zero, which was excluded from the set. At this point you'd probably realize that yes, there is an implicit assumption that ¬(b = 0) which should be made explicit, and then you also have to account for the `a = 0` case, which should also be easy.
But still, the error greatly confused me at first because it seemed like the theorem could not be applied in this case. I only realized the theorem could be used correctly in this case when the sibling poster suggested to use a different set.
It's probably also a great way to introduce almost undetectable security vulnerabilities by using Unicode characters that look similar to each other but in fact are different.