Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Skyrunner]

I don't know if that formula is the fastest... trying to actually find the Nth fibbonacci number with the formula is probably very imprecise because limited precision for reals and all.

I do know that trading memory for speed is a thing... not sure if it's applicable here! I would use the naive application but also have a dict with all the already found fibbo numbers.

[miauw62]

Well, all Fibonacci numbers are natural numbers so you could probably just wrap that in a round().

[Parsely]

I'm trying to store and return values for the Balance and Owner variables. It throws an error saying the variables are already declared, but I can't get rid of the variables at the module level (can I?). What do?

Code: [Select]

Public Class ClassAccount

    Public Property Balance As Decimal
    Private modBalance As Decimal
    Public Property Owner As String
    Private modOwner As String

    Public Function Balance() As Decimal
        Get
            Return = BalanceValue
        End Get
    End Function

    Public Function Owner() As String
        get
            Return = OwnerValue
        End get
    End Function

End Class

Also I'm not sure if those Get-Set functions will work the way I want them to.

[MagmaMcFry]

Here's how to logarithmic Fibonacci:

Code: [Select]

[int, int] fib2 (int n) {
// Returns the (n-1)st and nth Fibonacci numbers
if (n = 1) {
return [0, 1];
}
if (n <= 0) {
[int a, int b] = fib2(1-n);
int p = 1-2*(n%2);
return [p*b, -p*a];
}
[int a, int b] = fib2(n/2); // Integer division
if (n%2 == 0) {
return [a*a+b*b, b*(a+a+b)];
} else {
return [b*(a+a+b), b*b+(a+b)*(a+b)];
}
}

// For completeness' sake
int fib (int n) {
[int a, int b] = fib2(n);
return b;
}
@Gunner-senpai: Wtf is that programming language?

[Mephisto]

@Gunner-senpai: Wtf is that programming language?

I'm not OP, but it looks like VB.NET.

[Putnam]

Yeah, VB.NET. For some reason, it's pretty popular, especially among Dwarf Fortress applications (see: Masterwork UI, Raw Explorer, old LNP IIRC...)

[Parsely]

It's VB, coded in Visual Studio.

[Reelya]

Code: [Select]

int fibonacci(int n)
{
    if(n>1)
        return fibonacci(n-1) + fibonacci(n-2);
    else if(n==1)
        return n;
    else
        return 0;
}

This only works for n < 40something, if I remember right.
Not saying that it is wrong, just keep in mind how a small n can produce a rabitsplosion the likes of which even Armok has never seen.

Well, a recursive solution was asked for. Exploding the stack was not specified as an issue.

It's clear since each iteration calls the ones before it twice, that +1 n will double the runtime. The above runs in O(2ⁿ) time.

Running tests, it's the slowdown that kills the recursive version around #40, and the linear time version dies after #92, because that's where 64-bit numbers are no longer sufficient to hold the number, and the number is forced to be negative. If you want to get up to fibonacci #100, special tactics are required

[Mephisto]

If you want to get up to fibonacci #100, special tactics are required

Memoization and a language that supports huge numbers?

With some simple memoization and increasing the system recursion limit, Python 3 does fib(5000) in a few thousandths of a second.

[Reelya]

If you're going to use memoization why not just store the entire thing in a lookup table and get the result in a nanosecond.

But to get the memoization table going you do need to compute the values once right? If you're not doing that, you're just importing a lookup table with precalculated values, so it's not the same problem any more.

[Putnam]

the entire thing

can you make a lookup table of countably infinite size

[Reelya]

Can you hold a memoization table of countably infinite size? no.

The memoization table is better than just the recursion by itself. Since it will reduce the main algorithm it to linear time. But doing without the recursion is clearly better in any case.

[Putnam]

Is there a number that you can input into this function that will result in a memoization table of countable infinite size?

wait what the hell are we doing here

[Reelya]

You can always resize a lookup table if the index goes over the top, and use a linear calculation to fill in the blanks. This will be quicker than using the recursive function to do similar.

Anyway you can always grab a class that does big numbers or roll your own in any language. Big numbers is no reason to use Python, the "Duplo" of programming languages.

[Bumber]

Simple non-recursive Fibonacci using ring buffer:

Code: (c/c++) [Select]

int fibonacci(int n)
{
int buffer[] = { 2, 1, 1 };

for (int i = 4; i <= n; i++)
buffer[i % 3] = buffer[(i - 1) % 3] + buffer[(i - 2) % 3];

return buffer[n % 3];
}
I think this is the dynamic programming O(n) solution miauw62 mentioned. I didn't bother accounting for invalid input. Had to use this on a final exam I had today, but in pseudocode/Python.

Edit: Simplified to a single return statement.
Edit II: Got rid of redundant 'if' statement. 'For' loop handles it.
Edit III: Coding Standards Be Damned edition:

Code: [Select]

int f(int n){int b[]={2,1,1};for(int i=4;i<=n;i++){b[i%3]=b[(i-1)%3]+b[(i-2)%3];}return b[n%3];}