Fibonacci sequence up to first 256 elements
2 views (last 30 days)
Show older comments
sadiqa ilyas
on 10 Aug 2019
Answered: John D'Errico
on 10 Aug 2019
I want to generate first 256 fibonacci sequence elments . the code is repeating a fixed number after some terms, I think that we can use maximum of uint 64 and if a number gets begger we just stuck or is there any other reason or mistake in the code.
clear
format long g
n(1) =uint64(1);
n(2) = 1;
k = 3;
while k <= 256
n(k) = [n(k-2) + n(k-1)];
k = k + 1;
end
ff=mod(n,256);
%fprintf('%g,',n)
what I m getting is
Columns 91 through 105
69 189 2 255 255 255 255 255 255 255 255 255 255 255 255
Columns 106 through 120
255 255 255 255 255 255 255 255 255 255 255 255 255 255 255
Columns 121 through 135
4 Comments
John D'Errico
on 10 Aug 2019
Note that the periodicity of the Fibonacci sequence is not actually relevant, since as long as you work in mod 256 always, there is no overflow.
Accepted Answer
John D'Errico
on 10 Aug 2019
While this is surely homework, you got it almost correct, with a few major errors.
- Preallocate the vector!!!!!!!!!!!!!! Never grow an array dynamically, as otherwise, your next anguished question will be to ask why is my code so slow!
- Recognize that the modulus operation can be done inside the loop! This applies to the identity:
mod(a+b,P) = mod(mod(a,P) + mod(b,P),P)
Why is that important? Because you will never need to overflow. Your code can now become:
n = zeros(1,256);
n(1:2) = 1;
for k=3:256
n(k) = mod(n(k-2) + n(k-1),256);
end
fprintf('%g,',n)
As you see, there is no need to use uint64 either. Double precision is entirely adequate. In fact uint16 or int16 would have been entirely adequate.
1,1,2,3,5,8,13,21,34,55,89,144,233,121,98,219,61,24,85,109,194,47,241,32,17,49,66,115,181,40,221,5,226,231,201,176,121,41,162,203,109,56,165,221,130,95,225,64,33,97,130,227,101,72,173,245,162,151,57,208,9,217,226,187,157,88,245,77,66,143,209,96,49,145,194,83,21,104,125,229,98,71,169,240,153,137,34,171,205,120,69,189,2,191,193,128,65,193,2,195,197,136,77,213,34,247,25,16,41,57,98,155,253,152,149,45,194,239,177,160,81,241,66,51,117,168,29,197,226,167,137,48,185,233,162,139,45,184,229,157,130,31,161,192,97,33,130,163,37,200,237,181,162,87,249,80,73,153,226,123,93,216,53,13,66,79,145,224,113,81,194,19,213,232,189,165,98,7,105,112,217,73,34,107,141,248,133,125,2,127,129,0,129,129,2,131,133,8,141,149,34,183,217,144,105,249,98,91,189,24,213,237,194,175,113,32,145,177,66,243,53,40,93,133,226,103,73,176,249,169,162,75,237,56,37,93,130,223,97,64,161,225,130,99,229,72,45,117,162,23,185,208,137,89,226,59
0 Comments
More Answers (1)
Guillaume
on 10 Aug 2019
As for your question,
% Calculating first 256 terms.
% As soon as the values are >flintmax, they're just approximate
x = [1, zeros(1, 255)];
fib = filter(1, [1, -1, -1], x);
find(fib > flintmax, 1) %when does it overflow double?
find(fib > intmax('uint64'), 1) %when does it overflow uint64?
shows that the fibonacci sequence overflows flintmax at element 79, so from then on the values are approximations when stored as double.
It also shows that the sequence overflows uint64 at element 94. In matlab, integer overflows simply returns intmax, so from element 94, your sequence is simply going to be intmax('uint64'). And indeed, mod(intmax('uint64'), 256) is 255, so there's nothing surprising in your result.
So, there's no way that you can calculate more than 93 terms as a 64-bit integer. In fact, if you want to go to 256 terms, you'll need around 180 bits to store it as an integer.
However, since it looks like you're interested in computing it in the ring of integers modulo 256, there may be an algorithm that allows you to do that directly without computing the actual terms. Have you searched for it?
0 Comments
See Also
Categories
Find more on Creating and Concatenating Matrices in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!