This is on a job application pre-test. Is this a trick question...

This is on a job application pre-test. Is this a trick question? If I put a simple fibonacci function in there it will satisfy the question, but it will be inefficient as fuck. Anyone who has ever done one of those fibonacci tests for a programming test knows that you need to make it efficient for large values of n (>40) or it gets exponentially slow. However, on this test they don't offer much room. What would you do? do math with simple ints or BigInteger classes?

Other urls found in this thread:

math.berkeley.edu/~arash/55/8_2.pdf
wolframalpha.com/input/?i=Fibonacci[8181]
twitter.com/SFWRedditGifs

Write it as a for loop you dumbass.
Recursive functions are a meme.

Then it doesn't accurately follow the pattern of the equation. They might think you dont know how to do recursion.

It doesn't say anything about efficiency.
Write it how you want it user. I would write it personally in haskell since they taught me in class the solution to a similar problem.

The part 2 to the question would be impossible with a standard basic recursive fibonacci sequence, so I'm kind of thinking they want me to make it efficient. Just thought I would confer with yall.

>Asks you to evaluate f(8181)
>A recursive function would be unable to do this
Clearly they would like you to recognize that a recursive function would fail and as such not write a recursive function

This is 1st grade stuff user

Write in the recursive function and calculate the result with a non-recursive version. Tell them you did that and to pm you for the epic version :^)

f(0) = 0
f(1) = 1
f(2) = f(2 - 1) + f(2-2) = 1
f(3) = f(3-1) + f(3-2) = 2 + 1 = 3
f(4) = f(4-1) + f(4-2) = 3 + 2 = 5
f(5) = f(5-1) + f(f-2) = 4 + 3 = 7

This isn't the Fibonacci sequence, brainlet.

FibbSeq = 0,1,1,2,3,5,8,13,21,34,etc. Where the previous 2 elements add to equal the present 1.
ThisSeq = 0, 1, 1, 3, 5, 7, 9, 11, 13, etc. Where f(n) = f(n-1) + f(n-2).

This shit is easy though, here i'll do it right now in python:
funcFind(n):
if n

Holy shit the absolute state of Sup Forums. None of you tards know the difference between a fibbonachi sequence and a simple function.

...

fuck off newfag

Wrong f(3) don't exist f(2) = 2

Loop version Fibonacci seque
0,1,1,2,3,5,8,13
Just sum last two number and update variables or Store array.

Use Python or Java biginteger, number is huge.

Another method is use Fibonacci power matrix, but loop is OK.

This is bait right?
>f(2)=1
>f(3-1)=f(2)=2?

what do you mean f(3) doesnt exist? ofcourse if does

f(2) is 1

What is f(3-1)?

f(0) = 0
f(1) = 1
f(2) = f(1) + f(0) = 1
f(3) = f(2) + f(1) = 2
f(4) = f(3) + f(2) = 3
f(5) = f(4) + f(3) = 5

...

this is the Fibonacci sequence

this isn't f(n) = (n-1)+(n-2)
its f(n) = f(n-1)+f(n-2)

For your own sake I hope you are trolling and not actually this stupid.

>f(0) = 0
>f(1) = 1
>f(2) = f(1) + f(0) = 1
>f(3) = f(2) + f(1) = 2
>f(4) = f(3) + f(2) = 3
>f(5) = f(4) + f(3) = 5
please explain how.
Not other user, but curious anyways since i never learned this math?

>tfw memoization

The absolute state of neo-Sup Forums.

In you code, you need to use
n= funcfind(n-1) + funcFind(n-2);
return n;

Else it's wrong.

brainlet...

>This is on a job application pre-test. Is this a trick question?
no. You should have learned how to convert recursive functions to closed form in your 1st or 2nd year. If you didn't go to college, then find a "college is a meme" thread where you can circlejerk with all the other faggots that will get replaced by pajeets in a year.

It's possible if you memoize it.

>first semester CS student
>Even I can figure this out
Get your shit together, son

def fib(n):
if n==0:
return 0
large = 1
small = 0
for i in range(n-1):
old = large
large = small+large
small = old
return large

>recursive functions are a meme!

>most of Sup Forums would fail a basic interview question

I don't understand why not do this recursively? The algorithm is most naturally expressed recursively.

f(2) which is 1

Well I'm not going to use a recursive function with a depth of 8000...

return (phi^n-(1-phi)^n)/sqrt(5)
I'll take your job please.

It's weird that they don't just the ask the result of f(8181) mod [something less than INT_MAX].
This way you don't need to deal with BigInt crap but the program will be (almost) the same.

1 - 1 = 0
1 - 2 = -1

Yet somehow 0 + (-1) is supposed to be 1? What the fuck?

I honestly can't tell if people in this thread are trolling or not. You'll obviously get a stack overflow if you try to do this unless you're using some fancy language.

try not being an idiot and you'll see why. go ahead and answer the 2nd question if you don't understand why.

the answer is
math.berkeley.edu/~arash/55/8_2.pdf
this is a 200 level class btw

Coz they tarded

...

>He doesn't know how to make a reasonably efficient Fibonacci function

The fact that these idiots can't just tell you that you're doing a fibonacci sequence speaks volumes, that being said:

int main()
{
int a = 0, b = 1, fib;


for(int i = 1; i < 25; i++){
fib = a + b;
a = b;
b = fib;
cout

oops forgot to divide by 2^n

This is why you fuckers learn math:

def f(n):
return floor(golden_ratio^n)

What language is that supposed to be in? Please provide an actual implementation.

Why are you stupid fucks spoonfeeding OP?

this that's his fucking homework you tards

That's the lucas numbers you retard. Although they are much more interesting than the Fibonacci ones.

unsigned long long int

Here goes nothin'

size_t smol_fib_helper(size_t a, size_t b, size_t n)
{
if(n == 0) return a + b;
else return smol_fib_helper(b, a+b, n-1);
}

size_t smol_fib(size_t n)
{
if(n == 0 || n == 1) return 1;
else return smol_fib_helper(0, 1, n-1);
}

int main()
{
printf("f(5) == %zu\n", smol_fib(5));
printf("f(8181) == %zu\n", smol_fib(8181));
}

Thanks, SICP

So how is golden_ratio defined and what does that function output when you call f(8181)?

Hey guys, heres the funny part... not a single one of these code snippets yall posted could even yeild the correct answer for the next part. Fucking top lel m8.

Your shit just overflows

Try again bucko

Use the right tool for the job. Here it is with barely any recursion allowed and using almost no memory to store things.

$ cat fib.py
import sys
import functools

# don't need a big stack
sys.setrecursionlimit(10)

def fib(n):
# don't need a ton of memory
@functools.lru_cache(maxsize=5)
def fib_r(n):
if n

too slow

def fpow(a, x):
def fpow_h(a,x):
if x > 1:
return fpow_h(a*a, x/2)
return a
if x % 2 == 1:
return fpow_h(a,x) * a
else:
return fpow_h(a,x)

def f(n):
return floor(fpow(golden_ratio, n))

Pajeet wins

hmmm dont you have to use memoization and store the return value in a dictionary? There are youtube videos explaining in detail the exact answer to this problem. I'm still leaning addition/subtraction so I can't help personally im afraid.

But why? You don't even need recursion and that solution is significantly slower.

Real talk, whats so bad about java or bigint? Im applying for an android development position, what do you expect me to do?

It was just pseudo code. Here's js so you can run it in your browser:
phi = (1 + Math.sqrt(5))/2
function fib(n){
return (Math.pow(phi, n) - Math.pow((1-phi),n))/Math.sqrt(5)
}

It's true for all fibonacci like sequences you retard.

print(0)
print(1)
print(1)
print(2)
print(3)
print(5)
print(8)
print(13)
print(21)
print(34)
print(55)
print(89)
print(144)
print(233)
print(377)


You guys are dumb.

how is it the right tool, they're asking you for the answer. you say barely any recursion and almost no memory but try doing it in your head.

I'm sorry, you do not get the job

int fib(int count, int a=0, int b=1){
if (count==0) return a;
return fib(--count,b,a+b);
}

The easier to maintain your program is the better.

I'd love for this to work but most languages will round phi off and you'll get the wrong answer.

>int

nope

Nice. Except it doesn't work. It gives infinity for 8181. That was the whole point of OP's question.

No it's not. Code it up and see and you will get the wrong answer because the Lucas numbers are completely different.

>true for all sequences
could only be true if all sequences are the same. how the fuck did this not jump out at you? it's not even the right formula. fuck you're retarded.

Java is good, time ago I practice programming challenge a lot Indian practice but usually Russian or chines were better, but still Indians are better than burger boys.

Some funny joke is pajeet are better then average burger programmer.

why isn't that overflowing? does python use primitive int data types?

How is it easier to maintain? It's more complicated, it adds a layer of abstraction and more dependencies and makes it slower. Please explain how that is easier to maintain. There's literally nothing about that solution that is better in any single way.

Yeah I forgot change that for a long or even unsigned.

neither of those would work either.

I'm as surprised as you. I honestly expected it to overflow and to get to jump into a language with a nice number tower like scheme.

It's nice and simple. The code mirrors the problem description with a little boilerplate. If I wasn't limiting the stack size and memory usage for fun it'd be even simpler.

So it's exactly the same as the fibonacci sequence

Only feesible way to win is to write out a normal recursive statement and delete every previous element as you go along. For example:

[0]
[0, 1]
[0, 1, 1]
[1, 1, 2]
[1, 2, 3]
[2, 3, 5]
etc.

pic related. Thinking of using python list functions to do this.

What data type will suffice? I really don't know the correct number.

nvr mind I found out

You have to use multiprecision arithmetic. There are no standard sizes that are large enough.
You can see the number (truncated) in this guy's post. The actual number consists of roughly 5 times as many digits.

see attached op

Use a size 2 array and alternate storing the previous answer in f[0] then f[1]

def fib(n):
a = 0
b = 1
c = 0
for i in range(n):
c = a + b
a = b
b = c
return c
print(fib(8181))

pop in 8181 and lets see what happens

now answer 2)

why is the indentation so weird

Best answer itt

Range error
N = 0 OK don't run loop
N= 1 a + b = 1 OK
N = 2 a = 1 b= 1 c = 2 Fail
Sequence
0 1 1 2
You sequence
0 1 2 3

I think I'm stupid, why doesn't this work?

def fib(n):
prev = 0
current = 1
for x in xrange(n):
current += prev
prev = current - prev
return current

print fib(8181)


Answer looks ok to me? Is Python doing something smart without me realizing?

my "program" written in mathematica
> Fibonacci[n]
since you might not have a copy:
wolframalpha.com/input/?i=Fibonacci[8181]

post test results so we can see.

0, 1, 2, 3, 4, 5 and 8181

HAJAHAHHAHAHAHAJHSJSHDAJKNXZX,CNMmxncxzm,cnm,zcnaskcnsdkl

This is what peak performance looks like.

from numpy import matrix
(matrix([[1,1],[1,0]], dtype='object')**8181)[1,0]

Winner

Okay I spotted a problem, I think this is good now?

1474

Well, to start with, it gives fib(0) = 1 which is incorrect. It also gives fib(2) = 2 which is incorrect. Then it continues in the expected manner, so why do you get the wrong result? Well, user tried fib(8180), you'll never believe what happened next...