Fast addition for n+1 or n+0

[Walter Roberson]

|> That's a good thought, but my profiling experiments on his code show
|> that the amount of time spent in those areas is in the noise level,
|> with the arithmetic functions of the routine the OP indicate
|> being the bottleneck.

|Did you profile for _large_ Fib numbers, numbers much greater than can be
|represented by ordinary 'long', which is what the code seems to be all about?

75000

:And does your profiler account for out-of-process time such as e.g. swapping?

I was using a hardware program counter sampler, so out-of-band times
would not have been included.

The system I was running on has over a gigabyte of available memory.. it
would take rather some time to get to the point of swapping.


rofiling is a tricky business, and without analyzing that code in detail
I just skimmed it) it seemed to me have at least O(n log n) memory
:consumption for computation of a Fib number number n...

Experimentally, it is O(n^2) in time.

O(n log n) would take about n = 2^26 to fill a gigabyte.
On the system I am testing on (which is a decade old, 250 MHz),
the lapsed time is fairly close to 1 minute for n = 150000.
At that rate, it would take very close to 139 days of computation
to fill a gigabyte.

Other architectures would, of course, have different constants of
proportionality.

 

[Alex Vinokur]

On 2005-02-18 12:54:57 -0500, "Alex Vinokur" <[email protected]> said:
[snip]

I would like to optimize (speed) an algorithm for computing very large
Fibonacci numbers using the primary recursive formula.
The algorithm can be seen at
http://groups-beta.google.com/group/alt.sources/msg/42e76b12150613a1

Function AddUnits() contains a line
n1 += (n2 + carry_s); // carry_s == 0 or 1

The question is if is it possible to make that line to work faster?

No, the question is: "Is that line the bottleneck?"

I think function AddUnits() is the bottleneck. So, it is worth improving speed of that function.

How do you know that line is the problem?
Have you measured the performance of your code?

Yes. The program contains built-in speed measurement's (simple) tool.

[snip]

 

[Alex Vinokur]

* Alex Vinokur:

Attacking an optimization problem at the level of fundamental additions is
seldom a Good Idea.

Thinking about what goes on is almost always a Better Idea.

Almost any way of computing Fibonacci numbers is faster than the recursive formula.

I am interested in creating fast C++-algorithm using the primary recursive formula.

But you're not using the recursive formula directly, you're summing
iteratively, storing results in a std::vector of std::vector.

Results are storing in std::vector Fibonacci::fibs_.
Computing Fib(n):
If Fibonacci::fibs_.size() > n then Fib(n) = Fibonacci::fibs_[n];
else Fib(n) is computed according to the primary recursive formula.

[snip]

 

[Alex Vinokur]

|In article <[email protected]>,

|:Consider the following statement:
|:n+i, where i = 1 or 0.
|:Is there more fast method for computing n+i than direct computing that sum?

|It depends on the costs you assign to the various operations -- a
|matter which is architecture dependant.

There is a possibility that would be slower in any real
architecture that I've ever heard of, but which could be faster
under very narrow circumstances.

(n&1) ? (n+i) : (n|i)

[snip]

In g++ 3.3.3 (Mingw) on Windows 2000 that doesn't improve the speed.

 

[Richard Bos]

I need that in C/C++ program.

_Need_ that? Are you sure? Have you measured it? Frankly, I doubt that,
even if you _do_ find a highly system-specific measure to perhaps shave
a milli-cycle or so off your addition, the effect will be very
noticable. If your program spends a lot of time adding 0 or 1 to an
integer, it is highly probable that either you have an inefficient
(probably multiple) loop in which this is merely the inner statement, or
your problem is just that time-consuming.

Richard