|
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?
|
Japan11286 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.
|
Japan11286 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.
|
United Kingdom13775 Posts
I don't really like C++ Primer. No specific feedback, I just always felt whenever I was reading it that it didn't really go about teaching things the right way. CS books are generally all available online for free though, so Google the book and give it a read-through before buying if that's you cup of tea.
"Advanced" beginner is basically that you've done some work before and that you'd be fairly quick at picking new things up. The Stroustrup book makes you a better programmer, especially in C++, but it will absolutely make you have to work pretty hard for it. I will say that I definitely feel that I understood C++ on a much deeper level after I got through that book though. Ultimately it's only a first step, because there are further fundamentals of software that you simply don't get from an introductory course, but it's enough to put you on a solid foundation for moving forward. Self-study always comes with the downside that it's easy to get off course, learn something poorly, and never really be able to move on because you just get lost in the more advanced material.
|
Oh wow, that is cheap. Ordered.
Yeah, I bet there's a lot of "self-taught programmers" out there that make CS professionals roll their eyes, and I guess I'm joining their ranks. I'm hoping to try to avoid too many bad habits by trying to be fairly careful in the early chapters before jumping to the other stuff. Pointers seem like a big one that make it very easy to get yourself into trouble – there's all kinds of mistakes I can make with them that the compiler won't tell me about, and a lot of them will still give the right output in most cases so I won't realize I screwed up.
Maybe I'll keep writing blogs like this one so TL coders can keep me on track (if they're willing).
|
United Kingdom13775 Posts
CS professionals tend to have huge egos; there is a lot of things that will make them roll their eyes  .
In all seriousness: yeah, there's definitely a lot of people here that are fairly experienced in software. For me, it's a secondary, albeit critical, part of my job (I'm a rocket engineer first and foremost), but there's definitely a lot of people around here who are very skilled in software and do it as their primary job. Video games and software development tend to go hand-in-hand for reasons that are both obvious and not.
As for pointers: a C coder would very much have a tendency to overuse those. I'd say the best way to get a handle on how to best use them is to take some form of algorithms course once you feel you have the basics of C++ down. Quora has a decent list of courses that are available; pick one that is C++ based (because C++ is the best language for that kind of study).
|
On August 14 2017 03:49 LegalLord wrote:
I don't really like C++ Primer. No specific feedback, I just always felt whenever I was reading it that it didn't really go about teaching things the right way. CS books are generally all available online for free though, so Google the book and give it a read-through before buying if that's you cup of tea.
"Advanced" beginner is basically that you've done some work before and that you'd be fairly quick at picking new things up. The Stroustrup book makes you a better programmer, especially in C++, but it will absolutely make you have to work pretty hard for it. I will say that I definitely feel that I understood C++ on a much deeper level after I got through that book though. Ultimately it's only a first step, because there are further fundamentals of software that you simply don't get from an introductory course, but it's enough to put you on a solid foundation for moving forward. Self-study always comes with the downside that it's easy to get off course, learn something poorly, and never really be able to move on because you just get lost in the more advanced material.
EDIT: Damnit, you guys were talking about a book called "C++ Primer Plus". I noticed too late. That is a very different book from the legendary "C++ Primer".
My original post:
I love C++ Primer! It teaches the whole language in a no bullshit approach. Very academic and to the point. But also very thorough with all the details of C++. Definitely not an easy book. I already had experience with C when I read it. It's a challenge for a complete beginner.
I totally agree with your advice to check out various books by googling. That's what I did too. My choice was C++ Primer 
|
C++ primer 5th edition is by far the best book for learning c++ from scratch in my opinion, primer plus has (had maybe?) quite a few flaws in it, while primer went in and taught you proper practices very quickly.
For what it's worth, using pointers quite a lot of the time is unnecessary over engineering, but if you're teaching yourself at home I'd try and put them in just about everything until you are super comfortable using them, as there are times when you will have to use them, and they will be complicated as hell otherwise. This includes const pointers as well.
|
United Kingdom13775 Posts
I looked back over the book and basically confirmed my criticisms. Primer suffers from a bad case of being overly pedantic and missing the forest for the trees in terms of a book meant to teach the younglings how to code. A bit too basic to be a good reference, but far too convoluted to be a good starter book.
I saw one example there that instantly bugged me, in like chapter 1 or 2. It was something like "well the proper way is return x+4; because its faster but if you aren't comfortable with that to int y = x+4; return y; but that's bad." Lots of little tidbit micro-optimizations that frankly don't add anything to the learning experience, but that kind of just overload you with minutia that is best saved for when you can actually understand the concepts behind certain coding choices - at which point it becomes less of an artificial rule and more of an automatically ingrained concept.
Not that it's a bad book by any means - it's still a pretty solid resource - but I wouldn't recommend trying to learn from it, at least not without further resources. It can lead to making a simple exercise like a factorial turn into a convoluted pile o' crap. Of course, it's always nice to have multiple resources to reference because books are seldom universally perfect at doing everything.
|
I don't recall any such instance, are you certain that wasn't primer plus?
|
United Kingdom13775 Posts
On August 15 2017 13:44 bo1b wrote:
I don't recall any such instance, are you certain that wasn't primer plus?
Nope, Primer 5th as referenced above.
I will say that I do appreciate its focus on style and "doing things right" - but frankly that is best learned incrementally rather than through up-front where it's going to lead to coding paralysis and still kind of bad results.
|
On August 15 2017 13:36 LegalLord wrote:
I looked back over the book and basically confirmed my criticisms. Primer suffers from a bad case of being overly pedantic and missing the forest for the trees in terms of a book meant to teach the younglings how to code. A bit too basic to be a good reference, but far too convoluted to be a good starter book.
I saw one example there that instantly bugged me, in like chapter 1 or 2. It was something like "well the proper way is return x+4; because its faster but if you aren't comfortable with that to int y = x+4; return y; but that's bad." Lots of little tidbit micro-optimizations that frankly don't add anything to the learning experience, but that kind of just overload you with minutia that is best saved for when you can actually understand the concepts behind certain coding choices - at which point it becomes less of an artificial rule and more of an automatically ingrained concept.
Not that it's a bad book by any means - it's still a pretty solid resource - but I wouldn't recommend trying to learn from it, at least not without further resources. It can lead to making a simple exercise like a factorial turn into a convoluted pile o' crap. Of course, it's always nice to have multiple resources to reference because books are seldom universally perfect at doing everything. Harsh! I thought I was pretty clear that I thought the simple solution was the best, and I was just trying to think about these other ways to do it as an exercise in thinking about the consequences of using these more complicated mechanisms.
Speaking of needlessly overcomplicating the factorial function, what if I had the function return a union which can hold either a long long or a long double? Then if the answer fits in a long long I return that, otherwise I return the next-best long double. Too hacky? Convoluted pile of crap?
|
United Kingdom13775 Posts
Don't use unions unless you have a good reason to. Read this for some commentary about it.
|
Oh I think I misunderstood what would happen. I thought I could decide in the function whether to return a long long or long double, but I guess returning a union would be like returning a struct, except if I tried to access the wrong member it would break. What I wanted was something that could intelligently decide which to return based on whether I would overload the long long or not.
Oh well. I promise I'll stop trying to make my factorial function more complicated and just move on to learning other stuff
|
Ok fair enough, I don't recall it but it was a while ago.
|
Sanya12364 Posts
So is this exercise going to have an arbitrary length number? Are we thinking like 100! ?
With factorials you're probably doing counting, Which means doing full precision integer math. We want long long for such a calculation, and with large factorials, we go Beyond long long easily. C++ Has exercises with big nums. See http://www.cplusplus.com/forum/lounge/32041/
The declaration might look like:
bigNum* factorial(int);
This makes your factorial code allocation of bigNum. And there is no need to have factorials go Beyond int. The values become too big. The computation is too slow.
Concern for structure passing is an optimization with consideration with How your code translates into Machine code. At this Point, you also WanT to look at other optimizations. If you are going to call this function over and over again, you WanT to memoize and store results. Hash or an array for this memoization can work. Depending on how you do it, you may WanT to convert to:
const bigNum* factorial(int);
RIP capitalization. I pressed the TLPD button.
|
United Kingdom13775 Posts
If you want bignums, my personal favorite (for C++) is ttmath. It's not arbitrary precision like most (you define a precision at compile-time) but it's easy to use and it's the most performant I've ever used. For a task quite similar to factorials (the Gamma function) I also had issues with overflow and ttmath took care of that problem like a charm, with 0.1% of the trouble of most of the solutions I have seen.
|
Sanya12364 Posts
On August 16 2017 05:15 LegalLord wrote:If you want bignums, my personal favorite (for C++) is ttmath. It's not arbitrary precision like most (you define a precision at compile-time) but it's easy to use and it's the most performant I've ever used. For a task quite similar to factorials (the Gamma function) I also had issues with overflow and ttmath took care of that problem like a charm, with 0.1% of the trouble of most of the solutions I have seen.
ttmath is one of the best open source libraries you can use in C++ for bignums.
For storage sizes:
double itself is 10 bits of exponents and can compute 171 factorials. If you need factorials and care about runtime performance, you might just precompute at compile time and have an array.
long double with GCC is 80-bit precision with 15 bits of exponents. That's a bit more than 3000 distinct answers. Getting a full precision for factorials greater than 3000 is sizeable. Something to think about.
With bignums, you can really get up there with the precision and size of answers. Consider your needs before using and implementing.
|
|
|
|
|
|
EPT
