Fibonacci sequence up to first 256 elements

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

[KALYAN ACHARJYA]

I have deleted my answer.

@Guillaume Comments Moved here

I don't have the symbolic toolbox so can't test, but I suspect that calculating the whole sum as symbolic would be very slow.

@sadiqa, I assume you mean binary bitxor, because using the logical xor, it's very easy to know the result, xor(fibo_num, something) is simply going to be ~something since from the point of view of plain logical xor fibo_num is always true.

[Guillaume]

What we're missing here is an explanation of the need for this (or is it homework?).

Also. note that the fibonacci sequence modulo any number is periodical (for modulo 256, if I got it right the period is 384).

[sadiqa ilyas]

256 elements of fibonacci sequence will be xored with 256 different positive integers mod 256.

[John D'Errico]

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.

Answer 1

[John D'Errico]

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

Answer 2

[Guillaume]

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?