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

Software G'MIC
1

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]);
     dec_out_vec[q]&=bit_mask;
     if(dec_out_vec[q]>4,
      print(reverse(dec_out_vec));
      dec_out_vec[q]+=3;
     );
     dec_out_vec[q]&=bit_mask;
     print(reverse(dec_out_vec));
     if(q==last_pos?dec_out_vec[q]>msd_cond,++last_pos;);
    );
   );
   reverse(dec_out_vec);"
  fi
}

rm.
2

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. :frowning:

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);
    add_mode=add_pos=last_pos=select_pos=0;
   );
   while(select_pos<bin_size,
    for(p=last_pos,p>-1,--p,
     dec_out_vec[p]<<=1;
     dec_out_vec[p]&=bit_mask;
     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,
      add_mode=1;
      add_pos=p;
     );
     if(p==last_pos?dec_out_vec[p]>msd_cond,++last_pos;);
    );
    if(add_mode&&select_pos<w#-1,
     dec_out_vec[add_pos]+=3;
     if(add_pos==last_pos,++last_pos;);
     add_mode=0;
    );
   );
   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
4

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
Type "help", "copyright", "credits" or "license" for more information.
>>> 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;
     );
     dec_out_vec[p]&=bit_mask;
     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