# Implementing Double Dabble algorithm within G'MIC ( Solved for sure now!)

I decided to implement double dabble algorithm to convert binary of any side into decimal representation and vice versa. Practically, there’s a limit, but I honestly doubt you’ll reach that limit.

Source: Double dabble - Wikipedia

However, it seems that I have a problem here:

``````C:\Windows\System32>gmic rep_bin2dec_dd 1111111011011100 echo \${}
[gmic]./ Start G'MIC interpreter (v.3.3.3).
9,8,2,4,4
[gmic]./ End G'MIC interpreter.
``````

As you can see, it’s suppose to be 6,5,2,4,4 in the end result. So, some digits shows up correctly, others do not.

``````#@cli rep_bin2dec_dd:
#@cli : Convert binary numbers to digit representation using the double dabble method. Large binary number is supported here.
rep_bin2dec_dd:
\$=arg

repeat \$# {
p:=\$>+1
('\${arg\$p}')
if im<_'0'||iM>_'1' error inv_char_det fi
-. {'0'}

if (w<=53)&&0
eval[-1] <begin(m=0;n=0;);n|=i<<m;++m;end(set('\{\}',n);); rm.
else
eval "
const max_dec_digits=ceil(w#-1*log10(2));
const bit_mask=15; # equal to 1111
const msd_cond=7; # equal to 111
const shift_above=4; # If a value is greater than 4, then add 3.
dec_out_vec=vector(#max_dec_digits);
last_pos=0;
repeat(w#-1,p,
for(q=last_pos,q>-1,--q,
dec_out_vec[q]<<=1;
if(q
,dec_out_vec[q]|=dec_out_vec[q-1]>>3;
,dec_out_vec[q]|=i[#-1,p]);
if(dec_out_vec[q]>4,
print(reverse(dec_out_vec));
dec_out_vec[q]+=3;
);
print(reverse(dec_out_vec));
if(q==last_pos?dec_out_vec[q]>msd_cond,++last_pos;);
);
);
reverse(dec_out_vec);"
fi
}

rm.
``````

Ok, it appears that it finally works (after edits to code):

``````C:\Windows\System32>gmic rep_bin2dec_dd 11111111 echo \${}
[gmic]./ Start G'MIC interpreter (v.3.3.3).
255
[gmic]./ End G'MIC interpreter.

C:\Windows\System32>gmic rep_bin2dec_dd 11110011 echo \${}
[gmic]./ Start G'MIC interpreter (v.3.3.3).
243
[gmic]./ End G'MIC interpreter.
``````

I’ll be making options to have coders to work with giant binaries and decimals. This is going to allow options down the road too!

EDIT: Actually, I tested on 110000111 and it doesn’t work.

Here’s current code:

``````#@cli rep_bin2dec_dd:
#@cli : Convert binary numbers to digit representation using the double dabble method. Large binary number is supported here.
rep_bin2dec_dd:
\$=arg

res,sep=

repeat \$# {
p:=\$>+1
('\${arg\$p}')
if im<_'0'||iM>_'1' error inv_char_det fi
-. {'0'}

if (w<=53)&&0
eval[-1] <begin(m=0;n=0;);n|=i<<m;++m;end(set('\{\}',n););
else
status {`"begin(
const bin_size=w#-1;
const max_dec_digits=ceil(w#-1*log10(2));
const bit_mask=15; # equal to 1111
const msd_cond=7; # equal to 111
const shift_above=4; # If a value is greater than 4, then add 3.
dec_out_vec=vector(#max_dec_digits);
);
while(select_pos<bin_size,
for(p=last_pos,p>-1,--p,
dec_out_vec[p]<<=1;
if(p
,dec_out_vec[p]|=dec_out_vec[p-1]>>3;
,dec_out_vec[p]|=i[#-1,select_pos++];
);
if(dec_out_vec[p]>4,
);
if(p==last_pos?dec_out_vec[p]>msd_cond,++last_pos;);
);
);
);
reverse(dec_out_vec)+_'0';
"`}
fi

res.=\$sep\${}
sep=,
rm.
}

status \$res
``````

EDIT:

I attempted the edge case by hand, but I’m getting the wrong output:

``````0000 0000 0000 | 10110011 => Initialized
0000 0000 0001 | 0110011  => Shift
0000 0000 0010 | 110011   => Shift
0000 0000 0101 | 10011    => Shift
0000 0000 1000 | 10011    => Add 3
0000 0001 0001 | 0011     => Shift
0000 0010 0010 | 011      => Shift
0000 0100 0100 | 01       => Shift
0000 1000 1000 | 1        => Shift
0000 1011 1000 | 1        => Add 3
0001 0111 0001 |          => Shift
``````

That’s 171, so, what am I missing here?

Hmm, it appears that this is the correct interpretation:

``````0000 0000 0000 | 10110011 => Initialized
0000 0000 0001 | 0110011  => Shift
0000 0000 0010 | 110011   => Shift
0000 0000 0101 | 10011    => Shift
0000 0000 1000 | 10011    => Add 3
0000 0001 0001 | 0011     => Shift
0000 0010 0010 | 011      => Shift
0000 0100 0100 | 11       => Shift
0000 1000 1001 | 1        => Shift
0000 1011 1100 | 1        => Add 3
0001 0111 1001 |          => Shift
``````

I finally got it to work!

``````C:\Windows\System32>gmic rep_bin2dec_dd 11110011 echo \${}
[gmic]./ Start G'MIC interpreter (v.3.3.3).
243
[gmic]./ End G'MIC interpreter.

C:\Windows\System32>gmic rep_bin2dec_dd 11111111 echo \${}
[gmic]./ Start G'MIC interpreter (v.3.3.3).
255
[gmic]./ End G'MIC interpreter.

C:\Windows\System32>gmic rep_bin2dec_dd 10110011 echo \${}
[gmic]./ Start G'MIC interpreter (v.3.3.3).
179
[gmic]./ End G'MIC interpreter.

C:\Windows\System32>python
Python 3.10.6 (tags/v3.10.6:9c7b4bd, Aug  1 2022, 21:53:49) [MSC v.1932 64 bit (AMD64)] on win32
>>> 0b111111111111000000000001011111111111111100000000000011111111111111111111111111111111111111111111100000000000000000000000000001111111111111111111111111110000000000000000
374053108755155564133519097268318592963603263848448
>>> exit()

C:\Windows\System32>gmic rep_bin2dec_dd 111111111111000000000001011111111111111100000000000011111111111111111111111111111111111111111111100000000000000000000000000001111111111111111111111111110000000000000000 echo \${}
[gmic]./ Start G'MIC interpreter (v.3.3.3).
374053108755155564133519097268318592963603263848448
[gmic]./ End G'MIC interpreter.
``````

Done with this code:

``````#@cli rep_bin2dec_dd:
#@cli : Convert binary numbers to digit representation using the double dabble method. Large binary number is supported here.
#@cli : \$ echo \${rep_bin2dec_dd\ 111111111111000000000001011111111111111100000000000011111111111111111111111111111111111111111111100000000000000000000000000001111111111111111111111111110000000000000000}
rep_bin2dec_dd:
\$=arg

res,sep=

repeat \$# {
p:=\$>+1
('\${arg\$p}')
if im<_'0'||iM>_'1' error inv_char_det fi
crop. {xM},100%
-. {'0'}

if w<=53
eval[-1] <begin(m=0;n=0;);n|=i<<m;++m;end(set('\{\}',n););
else
status {"begin(
const bin_size=w#-1;
const d_bin_size=bin_size-1;
const max_dec_digits=ceil(w#-1*log10(2));
const LSD=max_dec_digits-1;
const bit_mask=15; # equal to 1111
const msd_cond=7; # equal to 111
dec_out_vec=vector(#max_dec_digits);
last_pos=select_pos=0;
MSD=LSD;
);
repeat(bin_size,q,
for(p=MSD,p<max_dec_digits,++p,
dec_out_vec[p]<<=1;
if(p==LSD
,dec_out_vec[p]|=i[#-1,select_pos++];
,dec_out_vec[p]|=dec_out_vec[p+1]>>3;
);
if(q==d_bin_size,continue(););
if(dec_out_vec[p]>4,
dec_out_vec[p]+=3;
);
if(p==MSD?dec_out_vec[p]>msd_cond,--MSD;);
);
);
set('MSD',MSD);
set('count_of_decimals',max_dec_digits-MSD);
dec_out_vec;
"}

status {`([\${}])[\$MSD,\$count_of_decimals]+_'0'`}
fi

res.=\$sep\${}
sep=,
rm.
}

status \$res
``````
2 Likes