Fibonacci sequence up to first 256 elements

5 visualizzazioni (ultimi 30 giorni)
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 Commenti
sadiqa ilyas
sadiqa ilyas il 10 Ago 2019
256 elements of fibonacci sequence will be xored with 256 different positive integers mod 256.
John D'Errico
John D'Errico il 10 Ago 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.

Accedi per commentare.

Risposta accettata

John D'Errico
John D'Errico il 10 Ago 2019
While this is surely homework, you got it almost correct, with a few major errors.
  1. Preallocate the vector!!!!!!!!!!!!!! Never grow an array dynamically, as otherwise, your next anguished question will be to ask why is my code so slow!
  2. 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

Più risposte (1)

Guillaume
Guillaume il 10 Ago 2019
See Loren's blog for an efficient way to compute the fibonacci sequence using filter.
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?

Categorie

Scopri di più su Creating and Concatenating Matrices in Help Center e File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by