add_new() for array like push_back() for vector

[Alex Vinokur]

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)?

 

[Thorsten Ottosen]

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]

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]

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/[email protected].

In particular I want to try
to replace vector<ulong> units_ in class BigInt
by an array of ulong's.

[snip]

 

[John Harrison]

I would like to impove performance of algorithm "Computing very long Fibonacci numbers" at
http://groups.google.com/[email protected].

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

 

[Alex Vinokur]

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 |

 

[Thorsten Ottosen]

http://groups.google.com/[email protected].

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]

http://groups.google.com/[email protected].

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])

 

[John Harrison]

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

 

[Alex Vinokur]

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/[email protected] (method getFibNumber (int n_i)).