asked on

bigger storage variable and performance analysis

/*

These are two standard algorithms of generating Fibonnaci (Fib) numbers, I was just learning them.

The problem is the program starts giving negative output after first 48 Fib numbers. Is there any way to
print first 100 numbers or more than them . How can i utilize memory another example say I have to calcualte factorial of 2^50

I was trying to calculate the performance statistics of the two algos. By just putting counter
variables in both functions and then finding how many times each function is being called .

But if I want to put something like time stamps - that is by reading the system clock in microseconds
how can I attempt this ?

Can some body suggest me good tools for performance analysis of algorithms

*/

#include <iostream>
#include <string>

using namespace std;

/*
int F( int i)

{

if (i<1) return 0;
if(i==1) return 1;

return F (i-1)+ F(i-2);

}

*/

#define MAX 1000
int F(int n)
{
static int knownF[MAX] = {0};
if (n == 0 || n == 1)
knownF[n] = n;
else if (knownF[n] == 0)
knownF[n] = F(n-1) + F(n-2);
return knownF[n];
}

int main()

{

unsigned long int fib_no = 0, index = 0;
int max;

while (index < 70)
{
fib_no = F(index);
cout<<index+1 <<": "<<fib_no<<endl;
index++;
}
return 0;

}

frogger1999

Two questions in one eh? Anyway for your first question for a little while you will get away with instead of using ints use "unsigned ints"

e.g. first algo declaration

unsigned int F(unsigned int i)

<implementation same>

and the second

unsigned int F(unsigned int n)
static unsigned int knownF[MAX] = {0};

this will get you the full 32 bits for your numbers (as all fibonacci numbers are >=0 anyway

But this will only last so long and ceratainly will not last to calculate (2^50)! (actually it wont calc (2^50).

So what you will need to write is a class that will hold your integer and perform the normal aritmatic ops on it (at least addition for fibo numbers) for an aribtrary number of digits.

I don't have a real example of doing this, Java has one called Big Integer, I think, and likely there may be examples for C++ on the web.

As for the performace timer

look up QueryPerformanceCounter if you are on windows: here is an example

#include <windows.h>
#include <iostream>

using namespace std;

int main()
{
LARGE_INTEGER start, end, freq;

QueryPerformanceFrequency(&freq); //how often we sample
QueryPerformanceCounter(&start);
Sleep(1000);
QueryPerformanceCounter(&end);

cout<<((double)(end.QuadPart-start.QuadPart)/(double)freq.QuadPart)<<endl; //prints how many seconds have elapsed
return 0;
}

amitpsu

ASKER

hi frogger1999,

it still didn't work. After 48 - the program starts truncating the tail of numbers.

and by the way could you be explicit in the performance analysis too.

I will add more points to it, if you want ;-)

frogger1999

no problem....

on windows the best timer there is is the performance counter

my example before with comments

int main()
{
LARGE_INTEGER start, end, freq;
QueryPerformanceFrequency(&freq); //this will tell you how often the sample is taken (e.g on my maching it is 1.19MHZ)

QueryPerformanceCounter(&start); //get the starting tick count
Sleep(1000); //do somthing here like your function call fibo() but remove Sleep()
QueryPerformanceCounter(&end);//get end count here

cout<<((double)(end.QuadPart-start.QuadPart)/(double)freq.QuadPart)<<endl; //lets see how long the function took by subtracting the end time from the start time
//put the answer in seconds (e.g. 1.00025s) for this example
return 0;
}

frogger1999

so just call QueryPerformanceFreguency to get the tics per second

then call QueryPerformanceCounter before you do something you want to time

then immediately after you do that something call QueryPerformanceCounter again to get the end time

so then you get

tics elapsed = (end-start)tics

put in seconds is

tics elapsed/tics per second == (end-start)/freq (use the quad part of the union)

hope that helps with the timer.

Mayank S

Alf,

If you happen to visit this page, then please also check:

https://www.experts-exchange.com/questions/20564717/printing-the-number-of-function-calls.html

Mayank.

frogger1999

yep seems like you run out of bits at about the 48th number or so. As I said before you are going to have to write a class or find one that will keep a string of the digits and do the math internally. I really can't help there as I suspect this may be homework.

Good luck.

substand

you should declare your variable as:

unsigned long int variableName;

Amit

frogger please comment on this. One more thing Please don't think that people always ask about their homework. I have done my hw part already in a longer and generic manner. But now I am trying to learn something.

To solve the problem I first declared a global variable. Later on to encapsulate I declared a class counter to replicate the global variable. Is this the right way of declaring global variables.

#include <iostream.h>

//int global=0;

class countme
{
private:
int global;

public:

countme()
{global=0;}

void setglobal(int p)
{
global=p;
}

returnglobal()
{
return global;
}

};

countme pit;

int F1(int i)
{
//countme pit;
static int m=1;
// cout<<"****"<<m<<endl;
m=m+1;
// global=m;

pit.setglobal(m);

if (i < 1) return 0;
if (i == 1) return 1;
return F1(i-1) + F1(i-2);
}

int F2(int i)

{

const int maxN=100;

static int knownF[maxN];

//static int m=1;
//cout<<"****"<<m<<endl;
//m=m+1;
//global=m;

//countme pit;
static int m=1;
// cout<<"****"<<m<<endl;
m=m+1;
// global=m;

pit.setglobal(m);

if (knownF[i] != 0) return knownF[i];
int t = i;
if (i < 0) return 0;
if (i > 1) t = F2(i-1) + F2(i-2);
return knownF[i] = t;
}

void main()

{
const int max=21;

int x;

//cout<<endl<< F1(25)<<endl;
int counter[max];

for (int i=0;i<max;i++)
{
//x= F2(i);

x= F1(i);

//counter[i]=global;

counter[i]=pit.returnglobal();

cout<<"------------------"<<endl<<"Number " <<i<<"..="<<x<<endl;

}

cout<<"------------------******************-----------------------"<<endl;

for (int k=0;k<max-1;k++)
{

cout<<counter[k+1]-counter[k]<<endl;

//cout<<counter[k]<<endl;
}

}

ASKER CERTIFIED SOLUTION

frogger1999

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

frogger1999

here is a little sample on how to get time stats on your functions

int main()
{
const int max=21;

LARGE_INTEGER freq;
QueryPerformanceFrequency(&freq); //this will tell you
for (int i=0;i<max;i++){
LARGE_INTEGER start, end;
QueryPerformanceCounter(&start);
x= F1(i);
QueryPerformanceCounter(&end);
cout<<"------------------"<<endl<<"Number " <<i<<"..="<<x<<endl;
cout<<"F1:"<<i<<" took"<<((double)(end.QuadPart-start.QuadPart)/(double)freq.QuadPart)<<" seconds"<<endl;
}
}

substand

consider taking a course or reading a book on algorithm comparison and design. doing it yourself will works better than writing just a time comparison for the 2 functions, as the functions will surely both be fast enough that the margin of error in timing them will likely be large- not to mention the fact that you are timing the timer as well. because of this, you may get the result that one function is 113% (or choose a number) faster than the other. however, over the lifetime of the function or when 1 million simultaneous users on a system use it at the same time, this may not be the real case- so it would be better to have an overall feel for the efficiency of the function.

bcladd

No comment has been added lately, so it's time to clean up this TA. I will
leave a recommendation in the Cleanup topic area that this question is:

Answered: Points to frogger1999

Please leave any comments here within the next seven days.

Experts: Silence means you don't care. Grading recommendations are made in light
of the posted grading guidlines (https://www.experts-exchange.com/help.jsp#hi73).

PLEASE DO NOT ACCEPT THIS COMMENT AS AN ANSWER!

-bcl (bcladd)
EE Cleanup Volunteer