-
February 7th, 2014, 09:17 PM
#1
[NOOB QUESTION] Really large numbers in C++
G'day, I've recently been teaching myself some C++ and one of the first programs I made was a Fibonacci generator, which can generate the first n numbers in the Fibonacci sequence, or calculate the nth:
I came to a problem though when n became greater than 47, which was also when the numbers generated reached 11 figures. I'm guessing there is a limit to the number of digits in an int type variable, so I changed the type to a float, but then numbers were expressed in scientific notation. I made a similar program in Python and that calculated the 10,000th number in the Fibonacci sequence in literally the blink of an eye:
So how would I do the same thing in C++?
Also, what is happening in terms of the memory when lists like this are generated? Just for reference, the code I used was:
Code:
int a = 0;
int b = 1;
int c = 0;
int n = 0;
cin >> n;
n -= n;
for (i = 0; i != n; i++){
a = b;
b = c;
c = a + b;
cout << c << endl;
}
Is the variable c allocated a new slot in the memory each time the program is iterated, so that all previous print outs of c are still visible, or is the memory overwritten and the previous versions of c stored by the console? I was monitoring my memory usage while generating a list of the first 500,000 numbers in the Fibonacci sequence, and it didn't seem to go up. Is that because 500,000 integers is still a negligible amount when you have 8GB of RAM?
On a side note, to stop the program from closing when it finished, I used cin.get() right at the end, but I had to use it at the end of all the if statements as well in order for it to actually work. So instead, right at the end I used:
Code:
string k = ' ';
cin >> k;
This is more compact, but it seems messy and unnecessary. What would be a good alternative?
Thanks!
-
February 7th, 2014, 10:38 PM
#2
Re: [NOOB QUESTION] Really large numbers in C++
Originally Posted by OeBoe
I made a similar program in Python and that calculated the 10,000th number in the Fibonacci sequence in literally the blink of an eye:
So how would I do the same thing in C++?
Get a "big number" library. There are many out there.
Is the variable c allocated a new slot in the memory each time the program is iterated
No. Assignment overwrites the variable on the left hand side of the equal sign.
Regards,
Paul McKenzie
-
February 8th, 2014, 01:22 AM
#3
Re: [NOOB QUESTION] Really large numbers in C++
Originally Posted by Paul McKenzie
Get a "big number" library.
Like this,
https://gmplib.org/
-
February 8th, 2014, 07:45 AM
#4
Re: [NOOB QUESTION] Really large numbers in C++
The limits of c++ types are defined in the header file limits.h (#include <climits>).
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
February 10th, 2014, 08:57 AM
#5
Re: [NOOB QUESTION] Really large numbers in C++
Originally Posted by razzle
gmp is pretty well developed, but it's also quite elaborate.
For something as simple as Fibonacci numbers (which is just addition), you could also create your own class based on vector<char> or a std::string (or some other string class). The class just does the addition the same way you would add big numbers with pen and paper. (it's a good c++ exercice even).
-
February 10th, 2014, 11:56 AM
#6
Re: [NOOB QUESTION] Really large numbers in C++
Originally Posted by OReubens
gmp is pretty well developed, but it's also quite elaborate.
For something as simple as Fibonacci numbers (which is just addition), you could also create your own class based on vector<char> or a std::string (or some other string class). The class just does the addition the same way you would add big numbers with pen and paper. (it's a good c++ exercice even).
I posted a simple large number class in a previous thread. See
http://forums.codeguru.com/showthrea...rge-Factorials
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
February 10th, 2014, 12:12 PM
#7
Re: [NOOB QUESTION] Really large numbers in C++
I think part of the fun (and certainly the learning experience) is to roll your own. You can always use established libraries like GMP to cross check your own implementation attempts.
-
February 10th, 2014, 12:18 PM
#8
Re: [NOOB QUESTION] Really large numbers in C++
Originally Posted by laserlight
I think part of the fun (and certainly the learning experience) is to roll your own..
There's certainly no fun in using someone else's implementation - and where would programmers be without scope for a bit of fun.
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
February 11th, 2014, 08:01 AM
#9
Re: [NOOB QUESTION] Really large numbers in C++
Originally Posted by laserlight
I think part of the fun (and certainly the learning experience) is to roll your own. You can always use established libraries like GMP to cross check your own implementation attempts.
that's why I said it's a good C++ exercice.
A "big number" class that only needs to do addition as a requirement (sufficien for Fibonacci) is fairly easy / fast to do and onc eyou have it running it's fairly straightforward to do subtraction.
Multiplication can be done "the hard way", or as an extention that uses the regular add operator.
Division... well... that takes a while to figure out... especially if you need it to be performant.
-
February 17th, 2014, 03:10 AM
#10
Re: [NOOB QUESTION] Really large numbers in C++
Apart from all the rest mentioned above....to end the program you could use getch() function.
P.S. You will have to include the conio.h header file.
Hope I could help...
-
February 17th, 2014, 03:21 AM
#11
Re: [NOOB QUESTION] Really large numbers in C++
Originally Posted by parikshit6321
Apart from all the rest mentioned above....to end the program you could use getch() function.
P.S. You will have to include the conio.h header file.
I recommend against this suggestion as getch is a non-standard function and conio.h is a non-standard header file. You can just run your program from a terminal window (or something along those lines) instead of introducing a dependency on a library that might not be available.
-
February 17th, 2014, 04:18 AM
#12
Re: [NOOB QUESTION] Really large numbers in C++
In fact in my system.... ubuntu linux i don't have that library conio.h and therefore I can't use getch(). It works in windows ok. (but this is a bit of red herring)
-
February 26th, 2014, 08:39 PM
#13
Re: [NOOB QUESTION] Really large numbers in C++
Boost has a large integer class: Boost Multiprecision
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|