Fibonacci sequence up to first 256 elements
2 次查看(过去 30 天)
显示 更早的评论
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 个评论
John D'Errico
2019-8-10
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.
采纳的回答
John D'Errico
2019-8-10
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 个评论
更多回答(1 个)
Guillaume
2019-8-10
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 个评论
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Creating and Concatenating Matrices 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!