2026-02-24 03:20:23
John Coltrane’s song Giant Steps is known for its unusual and difficult chord changes. Although the chord progressions are complicated, there aren’t that many unique chords, only nine. And there is a simple pattern to the chords; the difficulty comes from the giant steps between the chords.
If you wrap the chromatic scale around a circle like a clock, there is a three-fold symmetry. There is only one type of chord for each root, and the three notes not represented are evenly spaced. And the pattern of the chord types going around the circle is
minor 7th, dominant 7th, major 7th, skip
minor 7th, dominant 7th, major 7th, skip
minor 7th, dominant 7th, major 7th, skip
For more details see the video The simplest song that nobody can play.
2026-02-23 20:50:12
Big moves in roots can correspond to small moves in chords.
Imagine the 12 notes of a chromatic scale arranged around the hours of a clock: C at 12:00, C♯ at 1:00, D at 2:00, etc. The furthest apart two notes can be is 6 half steps, just as the furthest apart two times can be is 6 hours.
An interval of 6 half steps is called a tritone. That’s a common term in jazz. In classical music you’d likely say augmented fourth or diminished fifth. Same thing.
The largest possible movement in roots corresponds to almost the smallest possible movement between chords. Specifically, to go from a dominant seventh chord to another dominant seventh chord whose roots are a tritone apart only requires moving two notes of the chord a half step each.
For example, C and F♯ are a tritone apart, but a C7 chord and a F♯7 chord are very close together. To move from the former to the latter you only need to move two notes a half step.
Replacing a dominant seventh chord with one a tritone away is called a tritone substitution, or just tritone sub. It’s called this for two reasons. The root moves a tritone, but also the tritone inside the chord does not move. In the example above, the third and the seventh of the C7 chord become the seventh and third of the F♯7 chord. On the diagram, the dots at 4:00 and 10:00 don’t move.
Tritone substitutions are a common technique for making basic chord progressions more sophisticated. A common tritone sub is to replace the V of a ii-V-I chord progression, giving a nice chromatic progression in the bass line. For example, in the key of C, a D min – G7– C progression becomes D min – D♭7 – C.
2026-02-23 03:17:58
The previous post looked at the Bitcoin network hash rate, currently around one zettahash per second, i.e. 1021 hashes per second. The difficulty of mining a Bitcoin block adjusts over time to keep the rate of block production relatively constant, around one block every 10 minutes. The plot below shows this in action.
Notice the difficulty graph is more quantized than the hash rate graph. This is because the difficulty changes every 2,016 blocks, or about every two weeks. The number 2016 was chosen to be the number of blocks that would be produced in two weeks if every block took exactly 10 minutes to create.
The ratio of the hash rate to difficulty is basically constant with noise. The noticeable dip in mid 2021 was due to China cracking down on Bitcoin mining. This caused the hash rate to drop suddenly, and it took a while for the difficulty level to be adjusted accordingly.
At the current difficulty level, how many hashes would it take to mine a Bitcoin block if there were no competition? How does this compare to the number of hashes the network computes during this time?
To answer these questions, we have to back up a bit. The current mining difficulty is around 1014, but what does that mean?
The original Bitcoin mining task was to produce a hash [1] with 32 leading zeros. On average, this would take 232 attempts. Mining difficulty is defined so that the original mining difficult was 1 and current mining difficulty is proportional to the expected number of hashes needed. So a difficulty of around 1014 means that the expected number of hashes is around
1014 × 232 = 4.3 × 1023.
At one zetahash per second, the number of hashes computed by the entire network over a 10 minute interval would be
1021 × 60 × 10 = 6 × 1023.
So the number of hashes computed by the entire network is only about 40% greater than what would be necessary to mine a block without competition.
[1] The hash function used in Bitcoin’s proof of work is double SHA256, i.e. the Bitcoin hash of x is SHA256( SHA256( x ) ). So a single Bitcoin hash consists of two applications of the SHA256 hash function.
The post Bitcoin mining difficulty first appeared on John D. Cook.2026-02-23 02:30:40
When I first heard of cryptographic hash functions, they were called “one-way functions” and seemed like a mild curiosity. I had no idea that one day the world would compute a mind-boggling number of hashes every second.
Because Bitcoin mining requires computing hash functions to solve proof-of-work problems, the world currently computes around 1,000,000,000,000,000,000,000 hashes, one zettahash, per second. Other cryptocurrencies uses hash functions for proof-of-work as well, but they contribute a negligible amount of hashes per second compared to Bitcoin.
The hashrate varies over time because the difficulty of Bitcoin mining is continually adjusted to keep new blocks being produced at about one every ten minutes. As hardware has gotten faster, the difficulty level of mining has gotten higher. When the price of Bitcoin drops and mining becomes less profitable, the difficulty adjusts downward. There are other factors too, and hashrate is variable.
The prefix giga- (109) wasn’t widely known until computer memory and storage entered the gigabyte range. Then the prefix prefix tera- (1012) became familiar when disk drives entered terabyte territory. The prefixes for larger units such as peta- (1015) and exa- (1018) are still not widely known. The prefixes zetta- (1021) and yotta- (1024) were adopted in 1991 and ronna- (1027) and quetta (1030) were adopted in 2022.
When the Bitcoin hashrate is relatively low, it’s in the range of hundreds of exahashes per second. At the time of writing the hashrate is 1.136 ZH/s, 1.136 × 1021 hashes per second. This puts the hashrate per day in the tens of yottahashes and the number of hashes per year in tens of ronnahashes.
2026-02-22 09:00:31
I’ve written a couple times about Fibonacci numbers and certificates. Here the certificate is auxiliary data that makes it faster to confirm that the original calculation was correct.
This post puts some timing numbers to this.
I calculated the 10 millionth Fibonacci number using code from this post.
n = 10_000_000 F = fib_mpmath(n)
This took 150.3 seconds.
As I’ve discussed before, a number f is a Fibonacci number if and only if 5f² ± 4 is a square r². And for the nth Fibonacci number, we can take ± to be positive if n is even and negative if n is odd.
I computed the certificate r with
r = isqrt(5*F**2 + 4 - 8*(n%2))
and this took 65.2 seconds.
Verifying that F is correct with
n = abs(5*F**2 - r**2) assert(n == 4)
took 3.3 seconds.
So in total it took 68.5 seconds to verify that F was correct. But if someone had pre-computed r and handed me F and r I could use r to verify the correctness of F in 3.3 seconds, about 2% of the time it took to compute F.
Sometimes you can get a certificate of correctness for free because it is a byproduct of the problem you’re solving. Other times computing the certificate takes a substantial amount of work. Here computing F and r took about 40% more work than just computing F.
What’s not typical about this example is that the solution provider carries out exactly the same process to create the certificate that someone receiving the solution without a certificate would do. Typically, even if the certificate isn’t free, it does come at a “discount,” i.e. the problem solver could compute the certificate more efficiently than someone given only the solution.
Now suppose I have you the number F above and claim that it is the 10,000,000th Fibonacci number. You carry out the calculations above and say “OK, you’ve convinced me that F is a Fibonacci number, but how do I know it’s the 10,000,000th Fibonacci number?
The 10,000,000th Fibonacci number has 2,089,877 digits. That’s almost enough information to verify that a Fibonacci number is indeed the 10,000,000th Fibonacci number. The log base 10 of the nth Fibonacci number is very nearly
n log10 φ − 0.5 log10 5
based on Binet’s formula. From this we can determine that the nth Fibonacci number has 2,089,877 digits if n = 10,000,000 + k where k equals 0, 1, 2, or 3.
Because
log10F10,000,000 = 2089876.053014785
and
100.053014785 = 1.129834377783962
we know that the first few digits of F10,000,000 are 11298…. If I give you a 2,089,877 digits that you can prove to be a Fibonacci number, and its first digit is 1, then you know it’s the 10,000,000th Fibonacci number.
You could also verify the number by looking at the last digit. As I wrote about here, the last digits of Fibonacci number have a period of 60. That means the last digit of the 10,000,000th Fibonacci number is the same as the last digit of the 40th Fibonacci number, which is 5. That is enough to rule out the other three possible Fibonacci numbers with 2,089,877 digits.
The post 10,000,000th Fibonacci number first appeared on John D. Cook.2026-02-22 02:13:13
I’ve written before about computing big Fibonacci numbers, and about creating a certificate to verify a Fibonacci number has been calculated correctly. This post will revisit both, giving a different approach to computing big Fibonacci numbers that produces a certificate along the way.
As I’ve said before, I’m not aware of any practical reason to compute large Fibonacci numbers. However, the process illustrates techniques that are practical for other problems.
The fastest way to compute the nth Fibonacci number for sufficiently large n is Binet’s formula:
Fn = round( φn / √5 )
where φ is the golden ratio. The point where n is “sufficiently large” depends on your hardware and software, but in my experience I found the crossover to be somewhere 1,000 and 10,000.
The problem with Binet’s formula is that it requires extended precision floating point math. You need extra guard digits to make sure the integer part of your result is entirely correct. How many guard digits you’ll need isn’t obvious a priori. This post gave a way of detecting errors, and it could be turned into a method for correcting errors.
But how do we know an error didn’t slip by undetected? This question brings us back to the idea of certifying a Fibonacci number. A number f Fibonacci number if and only if one of 5f2 ± 4 is a perfect square.
Binet’s formula, implemented in finite precision, takes a positive integer n and gives us a number f that is approximately the nth Fibonacci number. Even in low-precision arithmetic, the relative error in the computation is small. And because the ratio of consecutive Fibonacci numbers is approximately φ, an approximation to Fn is far from the Fibonacci numbers Fn − 1 and Fn + 1. So the closest Fibonacci number to an approximation of Fn is exactly Fn.
Now if f is approximately Fn, then 5f2 is approximately a square. Find the integer r minimizing |5f2 − r²|. In Python you could do this with the isqrt function. Then either r² + 4 or r² − 4 is divisible by 5. You can know which one by looking at r² mod 5. Whichever one is, divide it by 5 and you have the square of Fn. You can take the square root exactly, in integer arithmetic, and you have Fn. Furthermore, the number r that you computed along the way is the certificate of the calculation of Fn.
