no shit man! but im getting help from Durafei and he's making time to explain it to me man once i'll understand this, i'll remember these code

___________________
Breaks, house, electro & downtempo.

quote:

Originally posted by Durafei ok.. conversion to binary.. destination is an array which will contain the binary representation WITH leading zeroes. void toBinary(int number, char*destination){ int cur=1; int i; for (i=0;i<32;i++){ if ((number&cur)!=0){ destination[31-i]=1; }else { destination[31-i]=0; } cur = cur<<1 } destination[32]=0; } I think it works, didn't test though.. it's pretty fast, no divisions at all

Didn't they teach you to line up your {}??

quote:

Originally posted by Backlight Didn't they teach you to line up your {}??

looks like it doesn't matter for him hehe

___________________
Breaks, house, electro & downtempo.

quote:

Originally posted by Durafei int fibonacci(int n) { int a=1, b=1(or is it 2??), temp; int i; if (n==1) return 1; if (n==2) return 1; //or is 2nd fibonacci number 2 ? i forget for (i=3;i<=n;i++) { temp=a+b; a=b; b=temp; } return temp; }

This is the iterative method to calculate the Fibonacci sequence.
There are also two other methods which I know of:

1) Recursive Method: (this is in C++)

class Alg1
{
public:
unsigned int Fib(unsigned int n); //computes the n-th Fibonacci number
};

unsigned int Alg1::Fib(unsigned int n)
{
if (n == 0 || n == 1) //return input n if 1st or 2nd in sequence
return n;
else
return Fib(n - 1) + Fib(n - 2); //compute n-th value recursively
}

2) FUCKED up matrix multiplication method: (Also in c++)

class Alg3
{
public:
void matrix_mult1(unsigned int A[2][2], unsigned int B[2][2]); //[2][2] * [2][2] matrix
void matrix_mult2(unsigned int A[2][2], unsigned int B[2][1]); //[2][1] * [2][2] matrix
unsigned int Fib(unsigned int expon); //computes n-th Fibonacci number
Alg3(); //constructor

private:
unsigned int Result1[2][2]; //stores [2][2] * [2][2] result
unsigned int Result2[2][1]; ////stores [2][1] * [2][2] result
unsigned int p[2][2]; //base matrix
unsigned int r[2][1]; //base matrix
};

Alg3::Alg3() //intialize values
{
r[0][0] = 1;
r[1][0] = 0;

p[0][0] = 1;
p[0][1] = 1;
p[1][0] = 1;
p[1][1] = 0;
}

unsigned int Alg3::Fib(unsigned int expon) //computes n-th value
{
if (expon == 0 || expon == 1) //if input n is less than 2 return it
return expon;
else //compute if input n is greater than 1
{
expon = expon - 1; //power matrix is raised to

//compute n-th Fibonacci value
while (expon > 0)
{
if (expon % 2) //if number is odd
{
matrix_mult2(p, r); //multiple the matrices
for (int i = 0; i < 2; i++)
for (int j = 0; j < 1; j++)
r[i][j] = Result2[i][j]; //copy result in another location
}

matrix_mult1(p, p); //multiple the matrices
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
p[i][j] = Result1[i][j]; //copy result in another location
expon = expon / 2; //divide input value by 2
}

int temp = r[0][0]; //store the answer
//reintialize the matrices
r[0][0] = 1;
r[1][0] = 0;
p[0][0] = 1;
p[0][1] = 1;
p[1][0] = 1;
p[1][1] = 0;

return temp; //return answer
}

}

//[2][2] * [2][2] matrix
void Alg3::matrix_mult1(unsigned int A[2][2], unsigned int B[2][2])
{
Result1[0][0] = A[0][0] * B[0][0] + A[0][1] * B[1][0];
Result1[1][0] = A[1][0] * B[0][0] + A[1][1] * B[1][0];
Result1[0][1] = A[0][1] * B[0][0] + A[1][1] * B[0][1];
Result1[1][1] = A[1][0] * B[1][0] + A[1][1] * B[1][1];

}

//[2][1] * [2][2] matrix
void Alg3::matrix_mult2(unsigned int A[2][2], unsigned int B[2][1])
{
Result2[0][0] = A[0][0] * B[0][0] + A[1][0] * B[1][0];
Result2[1][0] = A[0][1] * B[0][0] + A[1][1] * B[1][0];

}

//btw, this method is the fastest of the three
//lol, have fun!

Dude, the fastest of the three? the iterative method posted earlier is O(N) and only uses additions. how can the last method be faster?

___________________

My Blog: durafei.blogspot.com - Last Update March 23, 2006

quote:

Originally posted by Durafei Dude, the fastest of the three? the iterative method posted earlier is O(N) and only uses additions. how can the last method be faster?

the last method is O(logN)

i've done simulations with all 3 methods...

1) the recursive method yields an expontential growth as the n-th fib. number increases

2) the iterative method yields an linear growth...

3) the matrix method yields an logarithmic growth...
you got to take note of this line:
"expon = expon / 2; //divide input value by 2"
(this algorithm uses a divide and conquer method)

(i got timings, but i'm not posting those)

Last edited by Intense_Sounds on Oct-19-2002 at 23:11

quote:

Originally posted by bluE_Neon hey there fellow TA's this is a question for the TA programmers that we have out there... i have an assignment where i need to convert interger to 32-bit binary, a Fibonacci generator & HTML Color Converter.. the thing is i have no idea how to write the code to convert ill have a look also at some web-sites, maybe they have can help...in the mean time, would you guys help me out plz btw...the convertions must be done in function format, not basic logic thnx

most integers are 32bits.. at least on MS OS's

___________________

get font

I see your 4 Crushs and raise you 3 As The Rush Comes. - Yan from PvD's first summerstage event in '03