It's fun to figure out why things are going so slow.
So I am making a program to calculate the partition function.
I made an oversight while building it.
So basically it's a recursive function that depends on the results of smaller values. So I figured a way to make it fast, would be to save the value in an array. It basically checks if the value is 0, and then if it isn't it'll return the value. This is nice, as the array starts off with all 0's, so any value that hasn't been calculated should be 0.
A problem here is that since I'm doing this function (mod 11), any function is likely to be 0 quite a bit of the time. And it looks like this function is 0 (mod 11) a large portion of the time. So the function sees that f(N) is apparently still 0 (figuring that it hasn't been calculated), and it decides to calculate it, returning 0.
So I fixed it, by giving the array a number it can't have. So a -1 means it hasn't been calculated yet, and a 0 is a 0.
Way faster.
Just to have a picture of how much faster:
In the improved function,
F(100) looks something like this:
F(100) =F(99) + F(98) - F(95)-F(93)+F(88) + F(85)-F(78)-F(74)+F(65)+F(60)-F(49)-F(44)+F(33)+F(27)-F(14)-F(7)
For F(100), it should be 16 additions.
Instead, for the old function:
It would recalculate most of those, so for F(100), it was closer to 188 additions instead of 16.
And actually it gets so, so, so, so much worse than that, because it would still have to recalculate all the values for F(99) in a similar fashion.
And it would have to recalculate F(98) for both F(99) and F(100). That might be another ~380 additions.
And it would have to recalculate F(95) for F(100), F(97), and F(96). That might be another ~570 additions.
We're likely at around 1000 additions to calculate 3 numbers, F(100), F(98), F(95), and that is basically assuming that we don't calculate any of the smaller numbers.
So that should give you a picture of how stupidly, monstrously inefficient this one small error made for.
And if it does not. I decided to put everything back, add in a variable to count how many additions it took to calculate F(100) and only F(100).
And it is a fricken monster of a number.
Like wtf.
The new function gives me this output for 100: (assuming all the previous values are calculated)
Assuming none of the values are previously calculated, it comes to 1054 additions.
So yeah, I'm feeling pretty giddy right now.
So I am making a program to calculate the partition function.
I made an oversight while building it.
So basically it's a recursive function that depends on the results of smaller values. So I figured a way to make it fast, would be to save the value in an array. It basically checks if the value is 0, and then if it isn't it'll return the value. This is nice, as the array starts off with all 0's, so any value that hasn't been calculated should be 0.
A problem here is that since I'm doing this function (mod 11), any function is likely to be 0 quite a bit of the time. And it looks like this function is 0 (mod 11) a large portion of the time. So the function sees that f(N) is apparently still 0 (figuring that it hasn't been calculated), and it decides to calculate it, returning 0.
So I fixed it, by giving the array a number it can't have. So a -1 means it hasn't been calculated yet, and a 0 is a 0.
Way faster.
Just to have a picture of how much faster:
In the improved function,
F(100) looks something like this:
F(100) =F(99) + F(98) - F(95)-F(93)+F(88) + F(85)-F(78)-F(74)+F(65)+F(60)-F(49)-F(44)+F(33)+F(27)-F(14)-F(7)
For F(100), it should be 16 additions.
Instead, for the old function:
It would recalculate most of those, so for F(100), it was closer to 188 additions instead of 16.
And actually it gets so, so, so, so much worse than that, because it would still have to recalculate all the values for F(99) in a similar fashion.
And it would have to recalculate F(98) for both F(99) and F(100). That might be another ~380 additions.
And it would have to recalculate F(95) for F(100), F(97), and F(96). That might be another ~570 additions.
We're likely at around 1000 additions to calculate 3 numbers, F(100), F(98), F(95), and that is basically assuming that we don't calculate any of the smaller numbers.
So that should give you a picture of how stupidly, monstrously inefficient this one small error made for.
And if it does not. I decided to put everything back, add in a variable to count how many additions it took to calculate F(100) and only F(100).
And it is a fricken monster of a number.
Spoiler for Hidden:
Like wtf.
The new function gives me this output for 100: (assuming all the previous values are calculated)
Spoiler for Hidden:
Assuming none of the values are previously calculated, it comes to 1054 additions.
Spoiler for Hidden:
So yeah, I'm feeling pretty giddy right now.