|
I decided to get back into trying to teach myself programming recently. I'm still very much a novice at programming, so to any readers who are more seasoned, bear with me as I struggle to understand concepts you no doubt consider trivial.
I decided it would be an interesting challenge to try to write a function that would calculate the factorial of an int passed into it. Seems simple enough.
Goal: A Function that Calculates Factorials
Solution # 1: The simple solution
I figured the function declaration would look like this:
long double factorial(int);
Then the function call would look something like this:
long double facn = factorial(n);
//Initializes a long double called facn to the factorial of an int called n.
Pros: This function would be relatively simple to write, and it's perfectly simple to call. you pass it an int, and it returns a long double with the value of the factorial (since the factorial tends to be a very large number, I thought a long double made sense).
Cons: To my limited understanding of programming, having a function pass around big variables is inefficient in terms of runtime; better to pass a pointer to big variables rather than pass the variables themselves around. This might not matter so much here, just because a long double isn’t all that big. But part of this exercise is to practice dealing with some of the challenges programming might provide later. In a future function I might be passing around big structures or arrays with lots of elements, so I might as well try to face the challenges involved with such things now, with my only-kind-of-big long double variable.
Solution # 2: Call and return with pointers instead
Now I figured my function declaration would look like this:
long double* factorial(int*);
There’s not that much need to take a pointer to an int as an argument instead of just taking an int, but whatever, I’m trying to practice using pointers without breaking things. At any rate, now a function call should look something like this:
long double facn = *(factorial(&n));
//Initializes a long double called facn to the factorial of an int called n.
That’s fine as far as it goes. But the function I came up with looked like this:
long double* factorial(int* n)
{
long double facn = *n; // Initializes a long double to the value of n
for (int i = *n; i > 1; i --)
facn = facn * (i - 1);
//Multiplies facn by each number less than n, stopping at 1
return &facn;
}
Pros: This function would appear to achieve the same goal as Solution # 1, but it does so by passing around pointers to variables instead of passing the variables themselves. However...
Cons: The pointer returned by this function points to a variable that was created within factorial(), meaning it was killed when factorial() ended. In general, pointers to dead variables seem like a bad practice, because there’s no guarantee that the data in that address hasn’t been rewritten. I tried this program out and it seemed to work anyway; I had it print the first 16 factorials and they seemed to be right. But if I understand this problem correctly, there’s no guarantee that they would always be right, or that they would still be right on other systems.
At this point it seems like what I need is for the variable that stores the factorial to still be in scope when I exit the factorial() function.
Solution # 3: Declare the long double in main()
I could give the function a pointer to a long double that already exists. Then the function declaration looks like this:
void factorial(int*, long double*);
Now a function call has to look like this:
long double facn; //Creates a long double to hold the factorial
factorial(&n, &facn);
//Takes the factorial of an int n and assigns it to the long double facn
Pros: It accomplishes the initial goal (just like Solution # 1), with the subgoal of Solution # 2 (passing pointers instead of passing a long double), without using a pointer to an out-of-scope variable.
Cons: It's really ugly and unwieldy. I’m willing to put some dereferencing operators in a function call, but when it comes down to it, the mathematical idea of a factorial function is a one-input, one-output concept, not this two-input, zero-output monstrosity. What if I want to use the factorial of a variable as an expression, without creating a variable inside main() to assign that factorial to? Then I'm going to have to create a copy of that variable in main() to hold the value temporarily, which is basically why it was bad to have the function return a long double in the first place.
But there's another way to use a variable that doesn't pass out of scope when the function ends:
Solution # 4: Allocate the long double from the heap
long double* factorial(int* n)
{
long double* facn = new long double; // Allocates a long double from the heap
*facn = n // Initializes the long double to the value of n
for (int i = *n; i > 1; i --)
*facn = *facn * (i - 1);
//Multiplies facn by each whole number less than n, stopping at 1
return facn;
}
Pros: Now we’re returning a pointer to a variable that still exists. It accomplishes the goal, it accomplishes the subgoal, and the function call should look the same as the call for Solution 2 (not the ugliness that was the function call for Solution 3).
Cons: Now we’ve got an even worse problem! The pointer to that variable has passed out of scope, and we have no way of deleting that long double. That means every time the factorial() function gets called, we’ll leak a bit of memory the size of one long double. If we don’t call the function that often we might not notice, but the whole point of doing this with pointers was to do something that would hurt performance less! Memory leaks are hardly the way to do that.
Rethinking the problem
If I try to boil this problem down to it’s purest form, this is what I want to happen:
- We call a function and pass it an int (or pointer to an int, as I originally did).
- That function allocates memory space for a long double to hold the factorial of that int.
- It calculates the factorial and stores it in that long double.
- It returns that long double, or a pointer to it, for our use.
- The memory space for the long double is deallocated.
5. is the one that's giving me trouble. It can't happen inside factorial() because the last thing factorial() does is 4. And it can't happen before 4. because then the variable will be deallocated when the function returns it (sort of like Solution # 2). If we skip 5. entirely, we wind up with Solution # 4 and a memory leak. Normally you want to pair each new with a delete so you don't create memory leaks, but as established, we can't put the delete inside factorial().
At this point the simple solution is looking pretty attractive; it takes the int, creates a long double, calculates the factorial and puts it in the long double, creates a copy of the long double to pass back to main(), and kills the original long double when the function ends. The only part that seems inefficient is creating a copy of the long double, but it certainly beats out-of-scope variables and memory leaks.
+ Show Spoiler [An Aside] +There's another option here, which is to create a global temp long double, and use it whenever I need to calculate a factorial. But to my understanding, global variables are often considered bad practice, in part because they open the possibility of accidentally referencing them in other functions. If I only really need this variable for this one task, I don't want it to be global; I want it to exist when I need it, and not exist when I don't.
Solution 5: A memory manager
I have an idea for another, more general solution that could solve this problem (and maybe others), but I'm not quite sure how to go about it. The idea would be to have another function which acts as a memory manager. When we need memory, we tell it what we need and it allocates it for us; it also keeps track of all the variables it's created with flags for each one and whether it can be deallocated yet. Then each time it's called, it creates whatever variable it was called to create, deallocates anything flagged to be deallocated, and returns the newly created variable. A useful side effect is that for debugging purposes, I could ask my memory manager at any time what variables I currently have allocated.
Now factorial() could ask the memory manager for a long double, fill it with the factorial value, flag the long double to be deallocated, and return a pointer to it. The long double isn't deallocated yet, but it will be the next time the memory manager is called.
Pros: This seems like a good general solution to the problem of wanting to create memory, use it, and get rid of it, while simultaneously giving me a list of all the memory I have allocated, which could be useful for other purposes.
Cons: I haven't done something like this before, and I don't know how. Do I use an array from the heap to keep track of all the memory elements? Maybe a 2D array, where [x][1] is a pointer to the element itself, and [x][2] is its flag for deallocation? Do I just set a big array size and fill it, or do I try to use a vector or something to have a variable length array? What about a linked list or something? Would all of these be really expensive for performance? I don't know the answers to these questions.
Now I turn to you, coding TL denizens: how would you solve this apparently simple coding problem? Did I get something wrong? Is there an obvious solution I'm missing? I'd love to hear what more experienced coders have to say.
+ Show Spoiler [Edit] +I accidentally hit "Post" instead of "Preview" at one point while I was writing this, so if you clicked on this blog and saw an incomplete version at first, that's why.
|
First of all factorials don't need decimal points, so you shouldn't be using a double. Just use a long long. Also there's no reason to use a pointer for something like this.
|
But doubles can store much bigger numbers, no? Factorials get big awfully quickly.
And yeah, I was mostly trying to figure out how to do it with pointers for the sake of seeing if I could. Obviously solution #1 seems easiest and best.
|
On August 13 2017 07:09 ChristianS wrote:
But doubles can store much bigger numbers, no? Factorials get big awfully quickly.
No, they can't. A double is a variable that can store floating point values (with double precision). The keyword long actually makes the variable take up more memory in order to store bigger numbers. Use a (long) integer instead
|
On August 13 2017 07:18 Knatterking wrote:Show nested quote +On August 13 2017 07:09 ChristianS wrote:
But doubles can store much bigger numbers, no? Factorials get big awfully quickly. No, they can't. A double is a variable that can store floating point values (with double precision). The keyword long actually makes the variable take up more memory in order to store bigger numbers. Use a (long) integer instead
I must be misunderstanding something, so tell me where I'm wrong here if you don't mind.
int (and long, and long long) variables store whole numbers, with a range big enough to store 2^n numbers where n is the number of bits used to store it. On my computer I think a long long is 8 bytes, making the maximum around 10^19. That means the largest factorial it could hold is 20!.
Float (and double, and long double) store variables in decimal floating point, which works like scientific notation. Some of the bits are used for the significand, some are used for the mantissa. I don't know how exactly it decides the number for each, or whether it can give more bits to one if the other doesn't need as many. But because it uses scientific notation, it can store decimals. It can also store really really big numbers (because it uses scientific notation), at the expense of precision.
So if I store a 15 digit whole number in a long long, it will store every digit precisely correctly, whereas in a long double it will truncate some of the later digits. But if I store a 21 digit number in each, it will overload the long long whereas the long double will still have it approximately right.
So if I want factorials of numbers 20 and below, the function would be more accurate with a long long, but if I want factorials of numbers 21 and higher, a long double with its truncation errors is my only choice.
Did I get it wrong somewhere?
|
On August 13 2017 07:57 ChristianS wrote:Show nested quote +On August 13 2017 07:18 Knatterking wrote:On August 13 2017 07:09 ChristianS wrote:
But doubles can store much bigger numbers, no? Factorials get big awfully quickly. No, they can't. A double is a variable that can store floating point values (with double precision). The keyword long actually makes the variable take up more memory in order to store bigger numbers. Use a (long) integer instead I must be misunderstanding something, so tell me where I'm wrong here if you don't mind. int (and long, and long long) variables store whole numbers, with a range big enough to store 2^n numbers where n is the number of bits used to store it. On my computer I think a long long is 8 bytes, making the maximum around 10^19. Thst means the largest factorial it could hold is 20!. Float (and double, and long double) store variables in decimal floating point, which works like scientific notation. Some of the bits are used for the significand, some are used for the mantissa. I don't know how exactly it decides the number for each, or whether it can give more bits to one if the other doesn't need as many. But because it uses scientific notation, it can store decimals. It can also store really really big numbers (because it uses scientific notation), at the expense of precision. So if I store a 15 digit whole number in a long long, it will store every digit precisely correctly, whereas in a long double it will truncate some of the later digits. But if I store a 21 digit number in each, it will overload the long long whereas the long double will still have it approximately right. So if I want factorials of numbers 20 and below, the function would be more accurate with a long long, but if I want factorials of numbers 21 and higher, a long double with its truncation errors is my only choice. Did I get it wrong somewhere?
That's true, but having your factorial function return a double that isn't quite right for all values above 21 sounds horrible. Use a library like gmplib if you want to deal with huge numbers.
|
Hmm. Fair enough, I guess I don't need to plan for eventualities like massive 20-digit numbers without even having an application for this function in mind (especially since any application for it might need the answers to be precise and totally accurate, and the long double approach isn't).
Any comment on the way I went about trying to use pointers instead of just passing the variable? Acknowledging it's not necessary for such a simple function, is there at least a better way to do it?
|
Japan11285 Posts
I'll echo ziggurat's replies:
- using double for a factorial function doesn't look right. A past me would like this solution as well but this looks hacky and the meaning can easily get lost.
- use of pointers here reeks of overthinking or overengineering. Always try to keep things simple but not dumbed-down.
|
Alright. My thinking was that in the future with more complex programs I might want a function that returns something like a big structure or a 100-element array and I'd want to use pointers, so I might as well practice now. But I guess I might as well wait until then to start trying to solve the problems involved.
By the way I maybe should have said this sooner, but thanks everyone for the feedback. I'm sure it's dull watching someone try to figure out such basics.
|
Japan11285 Posts
If the challenge was partly to integrate and practice using pointers then by all means, disregard my second point. The challenge didn't seem like that at all when I read it.
|
United Kingdom13775 Posts
Why not just do it as a simple multiplication for loop? There is something to be said for simplicity of structure and that gives you the best memory and time usage you can hope for.
|
France9034 Posts
To be honest I expected to see the template version of factorials listed as well looking at the title.
Although it's very impractical in real life.
|
On August 13 2017 14:00 LegalLord wrote:
Why not just do it as a simple multiplication for loop? There is something to be said for simplicity of structure and that gives you the best memory and time usage you can hope for.
At risk of sounding very dumb, I'm not sure what you mean? At this point it seems like this is the function I'd go with:
long long factorial(int n)
{
long long facn = n;
for (int i = n; i > 1; i--)
facn *= n - 1;
return facn;
}
(I just typed this and didn't test it, so it might have a typo somewhere)
Is this not the multiplication for loop you're referring to?
On August 14 2017 00:53 Ragnarork wrote:
To be honest I expected to see the template version of factorials listed as well looking at the title.
Although it's very impractical in real life.
I know neither what that is, nor what makes it impractical. Like I said, novice.
|
United Kingdom13775 Posts
Yeah that (assuming correctness), but also handling the case of zero.
|
United Kingdom13775 Posts
Oh by the way, I think you might like this page which gives you what you're looking for with an explanation.
My opinion on "which implementation" is that you should do the simplest method that from a cursory view looks best, and then let the compiler do its optimizations. It's generally better at that than you. And the for-loop makes the most intuitive sense here.
|
On August 14 2017 02:41 LegalLord wrote:
Yeah that (assuming correctness), but also handling the case of zero.
Oh, right. In that case:
long long factorial(int n)
{
long long facn = 1;
for (int i = n; i; i--) //runs until i = 0
facn *= n;
return facn;
}
|
United Kingdom13775 Posts
(int i = n; i; i--)
Don't do that. That's stylistically really hacky and while it kind of gets the job done, you should be writing so that it's intuitively obvious what's going on. Plus you might want to be able to handle the case of a negative value. Not necessarily, since you might just assume correctness and check validity elsewhere, but it's something to keep in mind.
How I'd do it:
long long factorial(int n)
{
long long facn = 1;
// optional: if (n < 0) return -1;
for (int i = n; i > 0; i--) //runs until i = 0
facn *= i; // this was a typo on your part btw
return facn;
}
|
Oh woops. Okay, thanks.
Yeah, it does always look weird when my textbook does that. I'm not sure how much I can trust the programming book not to teach me bad habits. Once I'm a little further along I was going to try to read some kind of style guide, go back through my programs, and find instances where I could change things to fit the style guide.
Thanks!
|
United Kingdom13775 Posts
My favorite C++ book for "advanced" beginners is Programming: Principles and Practice Using C++, made by the guy who originally developed C++. It's a bit older now so it's cheap to buy, but it kind of tells you exactly what kind of style is most suitable for C++. I won't lie, it's a hefty read, but if you can get through it you will already be a pretty alright C++ programmer.
|
I bought C++ Primer Plus a few years back based on CecilSunkure's recommendation, and only just got around to reading it. But I might check that one out too once I feel like I've gotten more out of this one. I have a bad habit of buying massive textbooks and never getting around to reading them.
Edit: I have no idea what an "advanced" beginner is or whether I qualify. I took a C programming class once but kinda stopped going and got a C in it (no joke), then spent a little while after that trying to learn from the textbook on my own – that's my only programming experience before now.
|
|
|
|
|
|
EPT
