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

--
Alex Vinokur
mailto:al****@connect.to
http://mathforum.org/library/view/10978.html

[John Harrison]

"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

[John Harrison]

"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

[Thorsten Ottosen]

"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.)

[Thorsten Ottosen]

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

"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

[Alex Vinokur]

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

> >

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]

> >

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

[Alex Vinokur]

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

"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

[Thorsten Ottosen]

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

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

"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

[Alex Vinokur]

"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

[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

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

"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

[Alex Vinokur]

"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