Hi,
vector<T> v (100);
T *a = new T [100];
v.push_back(T());
Is it possible to add new T to array to get _contiguous_ storage area (for 101 element in an example above)?
--
Alex Vinokur
mailto:al****@connect.to http://mathforum.org/library/view/10978.html 18 3132
"Alex Vinokur" <al****@big.foot.com> wrote in message
news:c5*************@ID-79865.news.uni-berlin.de... Hi,
vector<T> v (100); T *a = new T [100];
v.push_back(T()); Is it possible to add new T to array to get _contiguous_ storage area (for
101 element in an example above)?
No, all you can do is allocate a new 101 element array and copy elements
from the old array to the new array.
But what's the problem? vector is contiguous already, just use a vector.
john
"Alex Vinokur" <al****@big.foot.com> wrote in message
news:c5*************@ID-79865.news.uni-berlin.de... Hi,
vector<T> v (100); T *a = new T [100];
v.push_back(T()); Is it possible to add new T to array to get _contiguous_ storage area (for
101 element in an example above)?
No, all you can do is allocate a new 101 element array and copy elements
from the old array to the new array.
But what's the problem? vector is contiguous already, just use a vector.
john
"Alex Vinokur" <al****@big.foot.com> wrote in message
news:c5*************@ID-79865.news.uni-berlin.de... Hi,
vector<T> v (100); T *a = new T [100];
v.push_back(T()); Is it possible to add new T to array to get _contiguous_ storage area (for
101 element in an example above)?
yes. A vector always has contiguous storage. Just say
const int sz = 100;
std::copy( a, a+sz, std::back_inserter( v ) );
br
Thorsten
(Btw, one should *always* stay away from builtin arrays in C++, unless there
is a *very* good reason.
Use boost::array<> and std::vector<> instead.)
"Alex Vinokur" <al****@big.foot.com> wrote in message
news:c5*************@ID-79865.news.uni-berlin.de... Hi,
vector<T> v (100); T *a = new T [100];
v.push_back(T()); Is it possible to add new T to array to get _contiguous_ storage area (for
101 element in an example above)?
yes. A vector always has contiguous storage. Just say
const int sz = 100;
std::copy( a, a+sz, std::back_inserter( v ) );
br
Thorsten
(Btw, one should *always* stay away from builtin arrays in C++, unless there
is a *very* good reason.
Use boost::array<> and std::vector<> instead.)
"John Harrison" <jo*************@hotmail.com> wrote in message news:c5*************@ID-196037.news.uni-berlin.de... "Alex Vinokur" <al****@big.foot.com> wrote in message news:c5*************@ID-79865.news.uni-berlin.de... Hi,
vector<T> v (100); T *a = new T [100];
v.push_back(T()); Is it possible to add new T to array to get _contiguous_ storage area (for 101 element in an example above)?
No, all you can do is allocate a new 101 element array and copy elements from the old array to the new array.
But what's the problem? vector is contiguous already, just use a vector.
I would like to impove performance of algorithm "Computing very long Fibonacci numbers" at http://groups.google.com/groups?selm....uni-berlin.de.
In particular I want to try
to replace vector<ulong> units_ in class BigInt
by an array of ulong's.
[snip]
--
Alex Vinokur
mailto:al****@connect.to http://mathforum.org/library/view/10978.html
"John Harrison" <jo*************@hotmail.com> wrote in message news:c5*************@ID-196037.news.uni-berlin.de... "Alex Vinokur" <al****@big.foot.com> wrote in message news:c5*************@ID-79865.news.uni-berlin.de... Hi,
vector<T> v (100); T *a = new T [100];
v.push_back(T()); Is it possible to add new T to array to get _contiguous_ storage area (for 101 element in an example above)?
No, all you can do is allocate a new 101 element array and copy elements from the old array to the new array.
But what's the problem? vector is contiguous already, just use a vector.
I would like to impove performance of algorithm "Computing very long Fibonacci numbers" at http://groups.google.com/groups?selm....uni-berlin.de.
In particular I want to try
to replace vector<ulong> units_ in class BigInt
by an array of ulong's.
[snip]
--
Alex Vinokur
mailto:al****@connect.to http://mathforum.org/library/view/10978.html
> > But what's the problem? vector is contiguous already, just use a vector.
I would like to impove performance of algorithm "Computing very long
Fibonacci numbers" at
http://groups.google.com/groups?selm....uni-berlin.de. In particular I want to try to replace vector<ulong> units_ in class BigInt by an array of ulong's.
Not sure that would give you any improvement. But of course it all depends
on your compiler and STL implementation.
One possible improvement is
BigInt Fibonacci::get_number (uint n_i)
{
fibs_.reserve(n_i + 1); // <<<------------ add this
const uint cur_size = fibs_.size ();
which will help avoid repeatedly resizing the fibs_ vector.
john
> > But what's the problem? vector is contiguous already, just use a vector.
I would like to impove performance of algorithm "Computing very long
Fibonacci numbers" at
http://groups.google.com/groups?selm....uni-berlin.de. In particular I want to try to replace vector<ulong> units_ in class BigInt by an array of ulong's.
Not sure that would give you any improvement. But of course it all depends
on your compiler and STL implementation.
One possible improvement is
BigInt Fibonacci::get_number (uint n_i)
{
fibs_.reserve(n_i + 1); // <<<------------ add this
const uint cur_size = fibs_.size ();
which will help avoid repeatedly resizing the fibs_ vector.
john
"John Harrison" <jo*************@hotmail.com> wrote in message news:c5*************@ID-196037.news.uni-berlin.de... But what's the problem? vector is contiguous already, just use a vector.
I would like to impove performance of algorithm "Computing very long
Fibonacci numbers" at http://groups.google.com/groups?selm....uni-berlin.de. In particular I want to try to replace vector<ulong> units_ in class BigInt by an array of ulong's.
Not sure that would give you any improvement. But of course it all depends on your compiler and STL implementation.
One possible improvement is
BigInt Fibonacci::get_number (uint n_i) { fibs_.reserve(n_i + 1); // <<<------------ add this
This improvement is very significant (see below).
John, thank you very much.
const uint cur_size = fibs_.size ();
which will help avoid repeatedly resizing the fibs_ vector.
john
===========================
------------------------------
Windows 2000
CYGWIN_NT-5.0 1.5.5(0.94/3/2)
GNU g++ version 3.3.1 (cygming special)
------------------------------
------ Compilation ------
$ g++ [Optimaze option] -mno-cygwin foo.cpp
-------------------------
Computing Fibonacci[50,000].
Comparative performance.
-----------------------------------------------
| Original | Algorithm with |
Optimization | Algorithm | John Harrison's |
| | improvement |
----------------|-----------------------------|
No optimization | 6.118 | 5.027 |
Optimization O1 | 3.344 | 2.423 |
Optimization O2 | 3.214 | 2.323 |
Optimization O2 | 3.294 | 2.293 |
-----------------------------------------------
Thanks again.
--
Alex Vinokur
mailto:al****@connect.to http://mathforum.org/library/view/10978.html
"John Harrison" <jo*************@hotmail.com> wrote in message news:c5*************@ID-196037.news.uni-berlin.de... But what's the problem? vector is contiguous already, just use a vector.
I would like to impove performance of algorithm "Computing very long
Fibonacci numbers" at http://groups.google.com/groups?selm....uni-berlin.de. In particular I want to try to replace vector<ulong> units_ in class BigInt by an array of ulong's.
Not sure that would give you any improvement. But of course it all depends on your compiler and STL implementation.
One possible improvement is
BigInt Fibonacci::get_number (uint n_i) { fibs_.reserve(n_i + 1); // <<<------------ add this
This improvement is very significant (see below).
John, thank you very much.
const uint cur_size = fibs_.size ();
which will help avoid repeatedly resizing the fibs_ vector.
john
===========================
------------------------------
Windows 2000
CYGWIN_NT-5.0 1.5.5(0.94/3/2)
GNU g++ version 3.3.1 (cygming special)
------------------------------
------ Compilation ------
$ g++ [Optimaze option] -mno-cygwin foo.cpp
-------------------------
Computing Fibonacci[50,000].
Comparative performance.
-----------------------------------------------
| Original | Algorithm with |
Optimization | Algorithm | John Harrison's |
| | improvement |
----------------|-----------------------------|
No optimization | 6.118 | 5.027 |
Optimization O1 | 3.344 | 2.423 |
Optimization O2 | 3.214 | 2.323 |
Optimization O2 | 3.294 | 2.293 |
-----------------------------------------------
Thanks again.
--
Alex Vinokur
mailto:al****@connect.to http://mathforum.org/library/view/10978.html
"Alex Vinokur" <al****@big.foot.com> wrote in message
news:c5*************@ID-79865.news.uni-berlin.de... "John Harrison" <jo*************@hotmail.com> wrote in message
news:c5*************@ID-196037.news.uni-berlin.de... > > But what's the problem? vector is contiguous already, just use a
vector. >
I would like to impove performance of algorithm "Computing very long Fibonacci numbers" at
http://groups.google.com/groups?selm....uni-berlin.de.
Just a quick question: why don't just use the formula for a Fibonacci
number? It's
Fib_n = 1/sqrt(5) * ((1 + sqrt(5))/2)^n - ((1-sqrt(5))/2)^n)
its been known for almost 300 years :-)
br
Thorsten
"Alex Vinokur" <al****@big.foot.com> wrote in message
news:c5*************@ID-79865.news.uni-berlin.de... "John Harrison" <jo*************@hotmail.com> wrote in message
news:c5*************@ID-196037.news.uni-berlin.de... > > But what's the problem? vector is contiguous already, just use a
vector. >
I would like to impove performance of algorithm "Computing very long Fibonacci numbers" at
http://groups.google.com/groups?selm....uni-berlin.de.
Just a quick question: why don't just use the formula for a Fibonacci
number? It's
Fib_n = 1/sqrt(5) * ((1 + sqrt(5))/2)^n - ((1-sqrt(5))/2)^n)
its been known for almost 300 years :-)
br
Thorsten
"Thorsten Ottosen" <ne*****@cs.auc.dk> wrote in message news:40***********************@news.optusnet.com.a u... "Alex Vinokur" <al****@big.foot.com> wrote in message news:c5*************@ID-79865.news.uni-berlin.de... "John Harrison" <jo*************@hotmail.com> wrote in message
news:c5*************@ID-196037.news.uni-berlin.de... > > > > But what's the problem? vector is contiguous already, just use a vector. > > > > I would like to impove performance of algorithm "Computing very long Fibonacci numbers" at >
http://groups.google.com/groups?selm....uni-berlin.de.
Just a quick question: why don't just use the formula for a Fibonacci number? It's
Fib_n = 1/sqrt(5) * ((1 + sqrt(5))/2)^n - ((1-sqrt(5))/2)^n)
its been known for almost 300 years :-)
[snip]
I wanted
* to check what (and how fast) can we compute when using _explicit_ Fibonacci formula,
* to create and to test class BigInt,
* to use this algorithm to compute _all_ Fibonacci numbers 1-n (not only Fibonaccci[n])
--
Alex Vinokur
mailto:al****@connect.to http://mathforum.org/library/view/10978.html
"Thorsten Ottosen" <ne*****@cs.auc.dk> wrote in message news:40***********************@news.optusnet.com.a u... "Alex Vinokur" <al****@big.foot.com> wrote in message news:c5*************@ID-79865.news.uni-berlin.de... "John Harrison" <jo*************@hotmail.com> wrote in message
news:c5*************@ID-196037.news.uni-berlin.de... > > > > But what's the problem? vector is contiguous already, just use a vector. > > > > I would like to impove performance of algorithm "Computing very long Fibonacci numbers" at >
http://groups.google.com/groups?selm....uni-berlin.de.
Just a quick question: why don't just use the formula for a Fibonacci number? It's
Fib_n = 1/sqrt(5) * ((1 + sqrt(5))/2)^n - ((1-sqrt(5))/2)^n)
its been known for almost 300 years :-)
[snip]
I wanted
* to check what (and how fast) can we compute when using _explicit_ Fibonacci formula,
* to create and to test class BigInt,
* to use this algorithm to compute _all_ Fibonacci numbers 1-n (not only Fibonaccci[n])
--
Alex Vinokur
mailto:al****@connect.to http://mathforum.org/library/view/10978.html
> I wanted * to check what (and how fast) can we compute when using _explicit_
Fibonacci formula, * to create and to test class BigInt, * to use this algorithm to compute _all_ Fibonacci numbers 1-n (not only
Fibonaccci[n])
Another possible optimization, replace
default :
fibs_.push_back (BigInt (get_number (i - 2), get_number (i - 1)));
break;
with
default :
fibs_.push_back (BigInt (fibs_[i - 2], fibs_[i - 1]));
break;
When you are calculating Fib(n), Fib(n-1) and Fib(n-2) must already have
been calculated and stored so this is safe to do. Might save a little time
and can't do any harm.
Actually my intuition is that it will not save any significant time, but
worth a try.
john
> I wanted * to check what (and how fast) can we compute when using _explicit_
Fibonacci formula, * to create and to test class BigInt, * to use this algorithm to compute _all_ Fibonacci numbers 1-n (not only
Fibonaccci[n])
Another possible optimization, replace
default :
fibs_.push_back (BigInt (get_number (i - 2), get_number (i - 1)));
break;
with
default :
fibs_.push_back (BigInt (fibs_[i - 2], fibs_[i - 1]));
break;
When you are calculating Fib(n), Fib(n-1) and Fib(n-2) must already have
been calculated and stored so this is safe to do. Might save a little time
and can't do any harm.
Actually my intuition is that it will not save any significant time, but
worth a try.
john
"John Harrison" <jo*************@hotmail.com> wrote in message news:c5*************@ID-196037.news.uni-berlin.de... I wanted * to check what (and how fast) can we compute when using _explicit_
Fibonacci formula, * to create and to test class BigInt, * to use this algorithm to compute _all_ Fibonacci numbers 1-n (not only Fibonaccci[n])
Another possible optimization, replace
default : fibs_.push_back (BigInt (get_number (i - 2), get_number (i - 1))); break;
with
default : fibs_.push_back (BigInt (fibs_[i - 2], fibs_[i - 1])); break;
When you are calculating Fib(n), Fib(n-1) and Fib(n-2) must already have been calculated and stored so this is safe to do. Might save a little time and can't do any harm.
Actually my intuition is that it will not save any significant time, but worth a try.
john
I have tested that.
It is unclear if it saves some time, but indeed it does no harm.
I am going to use
* fibs_.push_back (BigInt (fibs_[i - 2], fibs_[i - 1]));
P.S. That was one of options in very old algorithm : http://groups.google.com/groups?selm...40smc.vnet.net (method getFibNumber (int n_i)).
--
Alex Vinokur
mailto:al****@connect.to http://mathforum.org/library/view/10978.html
"John Harrison" <jo*************@hotmail.com> wrote in message news:c5*************@ID-196037.news.uni-berlin.de... I wanted * to check what (and how fast) can we compute when using _explicit_
Fibonacci formula, * to create and to test class BigInt, * to use this algorithm to compute _all_ Fibonacci numbers 1-n (not only Fibonaccci[n])
Another possible optimization, replace
default : fibs_.push_back (BigInt (get_number (i - 2), get_number (i - 1))); break;
with
default : fibs_.push_back (BigInt (fibs_[i - 2], fibs_[i - 1])); break;
When you are calculating Fib(n), Fib(n-1) and Fib(n-2) must already have been calculated and stored so this is safe to do. Might save a little time and can't do any harm.
Actually my intuition is that it will not save any significant time, but worth a try.
john
I have tested that.
It is unclear if it saves some time, but indeed it does no harm.
I am going to use
* fibs_.push_back (BigInt (fibs_[i - 2], fibs_[i - 1]));
P.S. That was one of options in very old algorithm : http://groups.google.com/groups?selm...40smc.vnet.net (method getFibNumber (int n_i)).
--
Alex Vinokur
mailto:al****@connect.to http://mathforum.org/library/view/10978.html This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Alex Vinokur |
last post by:
Hi,
vector<T> v (100);
T *a = new T ;
v.push_back(T());
Is it possible to add new T to array to get _contiguous_ storage area (for 101 element in an example above)?
--
Alex Vinokur
|
by: Martin Jørgensen |
last post by:
Hi,
I'm reading a number of double values from a file. It's a 2D-array:
1 2 3 4 5 6 7
-------------
1 3.2
2 0 2.1
3 9.3
4
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing,...
| |