Here's a fun little CS project I assigned myself on a boring plane flight:
How much space would it take to create and store every possible song?
I'd like to compose every song that could possibly be written, and then sue everyone else who ever writes a song for violating my copyright.
It's a noble goal! Read all about how I plan to accomplish it.
EverySong
*Only recording the melody line of a song
Song Data:
Key - 20 options?
Time - 20 options?
Total number of notes
Smallest note increment // if we've got 64th notes, or if the // smallest is a 16th, or whatever
Each note:
3 octaves, 7 notes each octave, sharp or flat notation
21 possible note values
OR it could be a rest...
Every note should be a NOTE/DURATION pair
For instance...
C3#,4
If the smallest note increment is a 16th, that means we've got a C# in the third octave, and it's a quarter note. (Four of the smallest increments.)
How many bits does it take to represent one note/duration pair
=====================
Note
=====================
To represent the note itself: 5 bits
To represent a sharp or flat... It would take two bits to represent each note, sharp or flat.
However, we can set bit 6 to 0 for non-accidental notes, then say that if bit 6 is a 1, we have an accidental. In that case, bit 7 will represent the nature of the accidental -- 0 for flat, 1 for sharp.
So the sharp or flat takes two bits on accidentals, one on naturals.
TOTAL: 6 bits (natural), 7 bits (accidental)
======================
Duration
======================
The duration will be a multiplier of the base increment, listed in the header. Worst case (that I'm pulling out of the air) is a 64th note base -- and it might be good to set that as a limit, and set a multiplier on the tempo, if it comes to that.
So, with a 64th base increment, a two-measure whole note would be 128. That's 7 bits. Allowing 8 bits for duration covers up to a four measure whole note, or if we disregard the assumption about minimum base increment, that would get us the two-measures even at a 128th base increment.
=======================
So...
=======================
Let's look at doing 8 bits for the note, and 8 bits for the duration. That's two bytes per note.
12345678901234567890123456
"Mary had a little lamb" is 26 notes long. That would cost 52 bytes to encode.
A longer song, at 120bpm with nothing but 8th notes, in 4/4 time, would have 240 notes per minute. At four minutes long, that song has 960 notes. At 2 bytes per note, such a song would require 1920 bytes. That's 1.9K per song.
1000 songs would fill 1.9 megs.
10,000 songs would fill 19 megs.
100,000 songs would fill 190 megs.
1,000,000 songs would take 1.9 gigs.
1 trillion songs would take 1.9 terrabytes, or 19, 100GB hard drives. For one TRILLION songs.
========================
How many songs are there?
========================
Well... We said we could encode a note in two bytes. But we can cut that down a bit for this. There are 61 possible notes, with 256 possible durations, and each could be either a rest or a note. So, that's effectively 122 possible notes, with 256 possible durations, or... 31,232 possible values for each slot. That's our base (like base 10, base 2, etc.). Um... Crummy.
960^31232
Is that really the number?
10^3 is how many possibilities we have in a three-digit number in decimal. Right? 10^(digits-1). Yes, that seems better.
So it's... 31232^960
Which is 6.5*10^4314
Which is probably more storage space than the universe presently holds.
BUT! If we cut those numbers down dramatically, maybe we can do something. Let's assume a simplified duration structure that only allows for sixteenth notes to whole notes. Our 256 possible durations becomes 9 possible durations. That, alone, brings us to a new calculation:
122 possible notes with 9 possible durations. 1098 possible values.
1098^960
9.5*10^2918
And let's remove the rests. Just for fun.
1098^480
1.8*10^1368
And that's still 13 googol possible songs.
=========================
Possible patterns to prune
=========================
I could set it up with a verse/chorus thing, and eliminate many random songs. We could also put in patterns, popular rythms and so forth. And generate the one hundred million most likely songs. I like that idea!
=========================
Future Research
=========================
How do those chess guys prune trivial moves? I need to learn more about that. It seems like there might be a lot that we could clear out of here. And I wonder about the validity of the assumptions I've made here.