Fibonacci positions (task 67) in JavaScript
Back to Problem Solutions forum
Hi!
I am using JavaScript to solve these, and it seems to handle large numbers quite fine, but somehow, on some numbers it seems to fail. I have tried solving this task 6-7 times now, and always one, rarely two, of the positions comes out wrong, simply because the calculations are off. My fibonacci-numbers are usually off by a few digits here and there. Has anyone solved this with Javascript and can help with my code?
Thanks!
-Finchnixer
Hi! Thanks for your message!
I'm afraid that we can't simply store these long values in javascript numbers - they are
IEEE 754 doubles - so
popular in other languages, I believe, i.e. 8 bytes so they only keep about 14 digits and exponenta (up to ~300).
Nevertheless it is still possible to solve the problem in JavaScript, though this will require some trick - I can think of two:
- more straightforward - to store numbers as arrays of digits or as strings, and implement addition function on them (i.e. implement simple long arithmetic);
- more cunning - to calculate some hashes of numbers only, say numbers modulo
1e12- you can do this for both fib sequence - and with numbers which you read from input.
I'm not quite sure about second idea, but it looks simpler. Feel free to ask for more explanations if these are too clumsy! :)
P.S. the data-generator / checker for this problem is written in PHP and therefore
suffer from the same problem - so it uses the first approach (as I needed to generate whole numbers,
not some hashes).
Okey, thanks, I will try to implement this as an array and see how it goes! :)
I've taken this as a challenge, and tried to implement the second approach :)
I'm not very well acquainted with JavaScript, but after kicking around it for some time - here is my solution - so at least without deep testing the idea looks correct :o
Grats, Rodionische! Well done, and seemingly a lot shorter than using arrays :)
But, I finally finished solving this with arrays, and it works! I have not spent a single minute optimizing the code, so it's probably filled with overhead, but after two days I don't care! :-D I am also left with a few nice array-functions, like the decimaking one, which converts [1,2,14] into [1,3,4]. I haven't touched programming since college, back in '96. Quite pleased getting this far with JavaScript in only a few days. :-)
And to be sure it doesn't hang, I have included a limit to the iteration count of 1000 now. And moving on to the next task. :)
> I haven't touched programming since college, back in '96.
Wow, that's impressive! I started programming only in the latest classes of school in '98, and when I started my acquaintance with javascript it took much much longer than few days. Congrats on this - I feel somewhat envious! :)
P.S. sorry for writing from different accounts - I still have no feature to solve problems as admin. :(
P.P.S. I've peeked at your code and it looks really quite short! Probably it could be shorter if we store
values in arrays in the reverse direction - probably then padArray(inarray,padvalue) is not necessary. If I
understood the code correctly :)
Ah, very good point! Heh, my brain could only handle a limited amount of computation and problem solving while working on this. Of course, yes, storing the digits in reverse would mean you could just perform the math directly. Smart!!
I also want to take the opportunity to say that this is BY FAR the best help to learn programming I have ever seen! Fun challenges and wonderful interface! Thank you!
Oh, thank you but you are too kind :)
Probably you have not seen HackerRank yet? I dare to recommend it because it is really great - both in rich interface and wide range of exercises. I believe it is driven by some university people from India...
> Of course, yes, storing the digits in reverse would mean you could just perform the math directly. Smart!!
I thought the same when I first heard of this trick :)
Hi everyone!
I am trying to solve "Fibonacci Sequence" problem in pure JavaScript as well. By now, the program that I've written, handles only short numbers correctly, but there are severe problems at calculating long numbers. I've understood, that there are several ways to solve this problem, and way one sounds more applicable for my case. Currently, I'm quite new to the programming and not still not good at Algebra. Could someone give me a detailed hint how could I solve this problem, or at least direct me to any web resources, that may be useful to find the solution? I would appreciate any help. Thanks in advance!
By the way, here follows the piece of code, that I've coped to write by this moment.
<!Doctype html>
<html>
<head>
<title>Fibonacci Sequence</title>
</head>
<body>
<p>How many array elements are there? </p><input id = "input1" type = "number" size = "12"></br>
<p>Enter the array: </p><input id = "input2" type = "text" size = "100"></br>
</br><button onclick = "ar_count()"> The results are: </button>
<p> The result is: </p> <p id = "result"></p>
<script>
function ar_count() {
var quant = document.getElementById('input1').value;
var numbers = document.getElementById('input2').value;
var splitted = numbers.split(" ").map(Number);
var result = [];
for (var i = 0; i < quant; i++) {
var fib = 0;
var count = 1;
var first = 0;
var second = 1;
while (splitted[i] != fib){
fib = first + second;
first = second;
second = fib;
count++;
}
if (splitted[i] == 0){
count--;
}
result.push(count);
}
var spaces = result.join(' ');
document.getElementById('result').innerHTML = spaces;}
</script>
</body>
</html>