Help with dec2bin conversion

I have to create a code using a while loop that will output the binary form of a number(that is less than 1). The code I have works but I need it to stop when the binary number begins to repeat. Like .13 begins to repeat at index 22.

n=input('Enter a positive decimal value=');
i=n; j=1; k=1; stop=0; binary=0; binaryStr='0';

while i~=1
    if stop==1
       break; %break the main while-loop
    end
    i=i-floor(i); %subtracts the lead integer, 1 or 0, from the decimal.
    value(j)=i;
    while j>=2 && k<j %a loop that compares i to all previous values of i
        if value(k)==value(j)
            stop=1; %a value to break the main loop.
            break %breaks this inner while-loop
        end
        k=k+1;
    end %end of comparison loop
    i=i*2;
    binary(j)=floor(i);
    j=j+1;
    k=1;    
end
for k=1:length(binary)
    binaryStr(k)=num2str(binary(k));
end
binaryStr=strcat('.',binaryStr); %adds '.' to the front of binaryStr
disp(binaryStr);

Answer 1

[James Tursa]

You are trying to solve what is essentially a very difficult problem when using floating point arithmetic. First, the number 0.13 isn't represented exactly as 0.13 in IEEE double since that exact number is not in the double precision floating point set. This is the exact decimal equivalent of the number that is stored:

>> num2strexact(0.13)
ans =
0.13000000000000000444089209850062616169452667236328125

So already there is a discrepancy between what you may think you are working with and what you are actually working with.

Second, when you start picking off fractions and multiplying them up by 2 each iteration, all those trailing discrepancies become more and more significant. So any hope of taking this algorithm to the extreme and looking for a pattern in the bits will likely be doomed to failure as the iterations progress.

E.g., take a look at the exact IEEE double precision bit pattern for the number 0.13 using this code:

function double2bits(d)
h = num2hex(d);
n = numel(h);
b = char(zeros(4,n));
for k=1:n
    b(:,k) = dec2bin(hex2dec(h(k)),4)';
end
b = b(:)';
fprintf('Sign bit = %s\n',b(1));
fprintf('Exponent = %s\n',b(2:12));
fprintf('Mantissa = %s\n',['1' b(13:end)]); % add in leading hidden bit
end

>> double2bits(0.13)
Sign bit = 0
Exponent = 01111111100
Mantissa = 10000101000111101011100001010001111010111000010100100

If you break apart the mantissa looking for a repeating pattern you might do this:

10000101000111101011
10000101000111101011
1000010100100

It looks good for the first two patterns, but then breaks down in the last pattern. So any scheme that is trying to find a pattern even using the IEEE double precision floating point bits isn't going to work. And likely any scheme you invent yourself that starts with a floating point value isn't going to work either.

You can come up with some type of test for the code you have (e.g., like the test you have ... testing the last calculated value(j) against all previously saved value elements to see if it is there ... and hence a repeating pattern is starting), but it probably will not work well given that you are starting with floating point values that are not "exact" for the numbers you think you are working with to begin with. So value(j) might be very close to a previous value element, but not exactly the same and hence you would not detect the start of a repeating pattern. Etc.

What one could do is start with two integers, e.g., 13 and 100, and then work with those two integers as a ratio to come up with an algorithm for getting the binary conversion. By working with integers one could come up with an exact algorithm that worked and could detect a repeating pattern with certainty. But that would be a totally different algorithm than the one you are currently working with.