# Tag Info

45

BOTH SAEM Fibo2 AN BIGGR OF Num AN Fibo2 O RLY? YA RLY DIFFRINT Num AN Fibo1, O RLY? YA RLY DIFFRINT Num AN Fibo2, O RLY? YA RLY VISIBLE "BOO, IZ NO FIBONACCI NUM!" GTFO NO WAI OIC GTFO NO ...

28

Indentation and formatting are fine, as is the algorithm itself. Your naming is inconsistent, compare n and Value; _value and _FnMinus1. There are a variety of conventions to follow, but consistency is the most important thing. _FnMinus1 and _FnMinus2 are only used in one method, so they can be made local to that method. The API is a little odd: fib.n = ...

25

Separation of concerns I like that you extracted ProovFibo... but I find it's doing too many things: I would have expected a function that returns a Boolean (Troof), and does nothing else.. but your procedure is keeping that information all for itself, and takes the responsibility of also outputting the result. Readability/naming You are declaring a Num ...

22

I have found a couple of things that could help you improve your code. Don't abuse using namespace std Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid. Avoid the use of global variables It may make some sense to have SIZE_OF_GENERIC_ARRAY as a global variable, but not arithmeticAverage. It's generally ...

18

Your code is quite nice, and can't really be improved. However, let's put the “generator” back into the code. Go has channels which can be used to write elegant generators/iterators. We spawn of a goroutine that fills the channel with the fibonacci sequence. The main thread then takes as many fibonacci numbers as it needs. So let's write a function ...

18

It's possible to calculate the nth Fibonacci number directly thanks to Binet's formula. Due to floating point errors, the formula doesn't give correct values if n is too large, but it works fine in order to calculate the number of digits. from math import log10, floor, ceil def fibonacci_digits(n): if n < 2: return 1 ϕ = (1 + 5**0.5) / ...

17

A few things: Naming: It's neither Fibonaci, nor febonani, nor fibonanci it's fibonacci. Please get your names to reflect what you're actually talking about and not some disfigured mutation of it :( memoized OTOH is a relatively nice name, I'd probably prefer memoizedFibonacciNumbers, but that's a thing of preference Calculating: quoting wikipedia: ...

17

Two comments: There isn't any reason to keep a list of all the fib numbers. You only need the last two numbers to compute the next one. A number with 1000 digits satisfies 1e1000 <= f < 1e1001. It might be faster to compare f to the numbers rather than to convert it to a string and get its length. def fib_of_length(n): """returns index of the ...

16

What you did well on: Your program is easy to read. You are allocating memory, even though it is unsafe in certain cases (other answers have addressed this, so I won't cover it). You prepare for some corner cases. Things you could improve: You are returning 0 when your program runs into a problem (except in one spot where there are too many parameters ...

16

The following is similar to Flambino's approach, but creates a Swift SequenceType so that you can use the Swift library functions filter() and reduce() to iterate over the elements: struct FibonacciSequence : SequenceType { let upperBound : Int func generate() -> GeneratorOf<Int> { var current = 1 var next = 1 ...

16

Generators, not lists Rather than returning a list of Fibonacci numbers, it would be much more useful to simply return an infinite generator of them. That is, yield them. This way, you don't even need the max: def get_fibonacci_numbers(): ''' Generator for all the fibonacci numbers ''' fib1 = 1 fib2 = 1 yield fib1 yield fib2 ...

16

Your code looks good and is well documented. I have a few suggestions anyway. Naming calc_fibonacci_num is a long name for such a function. The calc_ prefix is probably not useful and neither is the _num. The expression fibonacci(5) is probably explicit enough without additional information. The same kind of comment applies to the other function names. ...

16

Correctness calc_fibonacci_num doesn't say anything about range of accepted inputs >>> calc_fibonacci_num(100) 354224848179263111168L according to wolframalpha, it should be 354224848179261915075 Floating-point arithmetic is not precise enough to handle this

15

About this code: function TestFibo() { InputNum = document.getElementById("InputNum").value; The convention for function names is camelCase, not PascalCase. The same for variable names. Even more importantly, variables should be declared using the var keyword when used for the first time: var inputNum = document.getElementById("InputNum")...

15

My Assumptions about your requirements Here are a few points, assuming that you want performance and maintainability. Assumption: Since you did not put the generation of the sequence and the sum of the evens in separate methods, I assume that a separate generation of the sequence is explicitly not a requirement and therefore it's okay if all functionality ...

14

Microsoft's .NET style guide recommends against the use of underscores or any Hungarian notation in identifiers. You're right that overflow will occur for large enough values of n. It is possible to avoid overflow by using System.Numerics.BigInteger. However, that adds a lot of clutter to your program, and is more tedious than you would probably like for ...

14

Class vs Method This class is structured so that you give it an input (OrdinalPosition), and then from it you get an output (Value). Well, we already have something that's much more specifically suited for that than a class: a method! Instead of private void Calculate() you should have public BigInteger Calculate(int ordinalPosition) There are ...

14

The first trick of this exercise is recognizing you don't need to calculate the odd fibonacci numbers. The series of only the even numbers is : 0, 2, 8, 34, 144, 610, 2584, 10946, 46368, 196418, 832040, 3524578, ... So starting with 0 and 2 the next element is always 4 times the preceding one plus the one before that : 34 = 8*4 +2 144 = 34*4 + 8 ... ...

14

Since you are asking what are the cases to consider, I'll give you a very simple one. Following that, there is a further refinement to achieve a final solution as well as a few comments to consider. Trading space for speed using memoization Definition: https://en.wikipedia.org/wiki/Memoization Basically, we want to keep a look-up table of Fibonacci ...

14

Since other answers have focused on the code quality itself, I'll focus on performance. Recursive Fibonacci by itself is $O(2^n)$ time. Memoized fibonacci is linear time (check out functools.lru_cache for a quick and easy one). This is because fibonacci only sees a linear number of inputs, but each one gets seen many times, so caching old input/output ...

13

I would use separately Fibonacci generator def even_fib(limit): a, b = 0, 1 while a < limit: if not a % 2: yield a a, b = b, a + b And sum function to calculate sum of items print sum(even_fib(4000000))

13

I'd suggest a couple of things. Firstly, this is a typical Euler problem example in that Euler usually provides an example test case. Build that into your code so that you confidently refactor. Secondly, I recommend separating the algorithm from the reporting of its results; this again supports writing built in tests without generating unwanted output. ...

13

With regard to your time complexity: With your calculation of the nth Fibonacci number, you could do it in $O(1)$ time by using the relation: $$F_n = \left\lfloor \frac{\varphi^n}{\sqrt{5}} + \frac{1}{2} \right\rfloor$$ So the 484th Fibonacci number would be equal to: \left\lfloor \frac{\varphi^{484}}{\sqrt{5}} + \frac{1}{2} \right\rfloor \approx 6....

13

This isn't a full review but something I found very interesting about this problem: I would have thought that keeping a list of every Fibonacci number would get expensive over larger numbers but that doesn't seem to be the case with my testing. Instead it seems the bottleneck is the line: len(str(fibs[-1])) < n: I ran the function for n = 10,000 and it ...

12

You C is very good. Just a few comments: The start parameter is pointless. Just print the whole sequence. Don't allocate memory until you know your parameters are valid. Else you have a memory leak. You don't check that the numbers[] array was allocated successfully and you have overflowed the array by one place. Define loop variables in the loop ...

12

Class Design Some of class design is a matter of doing what will cause the least surprise to others. There is nothing functionally wrong with passing the value into the constructor and reading the answer from a value, or in explicitly setting the count, can calculating; they both work; but a more expected shape would be along the lines of public class ...

12

Assuming you're using the current c++ standard, since you don't specify in your question. Prefer stoi to atoi. atoi has issues. Prefer standard int types: std::uint128_t instead of unsigned long long int Create a type alias for your map type since you use it a lot. Don't include unnecessary headers in the fibbonacci.h file. Include them in the ...

12

Is this a generator or a calculator? Generators are objects that behave like iterators, yielding the next value on every call. std::map<int, unsigned long long int> __fib_result_map = initializeMap(); #ifndef __fibonacci #define __fibonacci Know the rules regarding underscore usage. From the C++ Standard: 17.6.4.3.2 Global names [global.names] ...

12

Short answer: don't use recursion. Slightly longer answer: don't use recursion if you have more than a single recursive call of your function in the non-trivial paths without memoization. Your fibonacci calls itself twice, except when num is in range(0,3). Those two calls will call fibonacci again twice (unless one of them is already in your base case), so ...

12

Your function uses global variables, which is bad for several reasons: The variables must be reset before the function can be called again. The variables can be modified from outside of your function, causing wrong results. The function is not thread-safe. In addition, The program logic is not immediately obvious (at least it wasn't to me). Calling the ...

Only top voted, non community-wiki answers of a minimum length are eligible