Calculating

I'm working on a little program to play with some numbers and I need an array of the appropriate size. It's easy to do, you decide on some array size and then you ask the O.S. for a chunk of memory that big. If you are a well behaved program, and the O.S. likes the cut of your jib, he might let you have it.

You don't want to ask for anymore than you need because if you ask for a great deal, that might interfere with whatever else you are trying to do, like trying to watch YouTube videos. Also, large amounts of memory can involve lots of processor time, and you might not want to run the program for that long, so you run on it a smaller set of data.

In the C programming language there are a couple of ways to do this. The traditional way is call malloc, the O.S.'s memory allocation procedure with number of bytes you want. It will return a pointer which you will base your data structure on.

    fraction_s* a = malloc(q * sizeof(fraction_s));

Another way is to declare your array in the main procedure (which is where the program starts), and use another variable as the size of the array. You need to assign a value to the size variable before you try and make use of it in the declaration of the array. Get all that? Sounds kind of convoluted. Maybe it's just my explanation is convoluted. Let's see if a bit of code helps.

int main(int argc, char** argv)
{
    int q = 1000;    // default value
    if (argc>1)
        q = atoi(argv[1]);    // pick up value from command line

    fraction_s    a[q];       // declare an array of data blocks
    memset(a, 0, sizeof(a));  // zero out the array

Last thing is to fill the array with zeros. Saves having to do it explicitly whenever we are loading data, we can just skip all those locations for which we don't have data. That way, come run time, we can be sure we won't misinterpret them for data. We might want to set a flag in each block that does have valid data.

Took a while to get here, but we have finally got to the crux of the matter. I'm working on a program to check out Farey Addition of fractions. I need an array to hold of all the possible fractions that can be generated using any pair of integers, up to some limit. For instance if my limit was 1,000, I would need an array to hold a million numbers. If I confine my self to proper fractions (the numerator is smaller than the denominator), then I only need half as much. Roughly.

You don't want to get a size calculation like this wrong, because while it might be a nuisance when the program is only going to run for a few seconds, it would be the shitz if your program got a memory fault after it had been running for a week and it lost all your work, all because you got the memory request size calculation wrong.

You screw up once or twice and you start taking pains to get it right. Getting it right also insures that your program doesn't get kicked off for asking for too much memory, when a properly sized request would allow you to run. It also tells you how much memory you need for the kinds of problems you are working with.

There's probably a name for the series that tells you how many fractions you are going to generate. Fibonacci or Bernoulli, or maybe, I dunno, Flatulence? I think I'm getting burned out on the math section of Quora. Seems like half the questions over there are talking about some obscure thing named after an even more obscure, old, dead, white guy (usually). Numberphile does that some too, but usually it's just kind of a decoration, like ribbons and bows, on their presentation. On Quora, these names are in these questions and understanding what the term means is crucial to understanding the question. Sometimes it's really simple, like this fraction thing I am working around to explaining, which is great, it means I can understand the question. But sometimes it's such an esoteric term that only the half dozen people who are writing theses on it have any idea what it means. I'm not going into those ratholes, I have plenty of my own, thank you.

Back to our array. For a denominator of 1 you can have two values in the numerator: 0 or 1. We're only going to count the zero. One over one is one, which really isn't a fraction. We aren't going to count the one, so for one, we have one value. For a denominator of 2 you can have two real values: 0 or 1. Plus 1 for zero gives you three. Like so:

Denominator /
Number of Proper Fractions    Total
            1              1
            2              3
            3              6
            4             10
            5             15
            6             21
            7             28
            8             36
            9             45
           10             55

It kind of looks (n+1) * n/2. It looks an exact calculation to me. No issue with rounding due to division by 2 (of n and (n+1) ), one is going to be even and the other will be odd, so the product will always be even and divisible by two.

We could eliminate the zeros, and maybe I will, all zeros are alike, am I right? But right now it's handy becuase I've been using zero based arrays for so long it's like second nature. Taking out the zeros, oh boy, I dunno if that's ever been done before Mr. Halliday (figment of my imagination, my inner Jimmy Stewart talking to big fat boss man with the straw hat, bifocals and a cigar).