17
\$\begingroup\$

Write a function or program that outputs Quater-imaginary base displayed as binary digits. The number base is 2i, where i is the square root of -1. See Complex Number for more details on i. Each digit position can go from 0 to 3 (quaternary), as each real and imaginary part is -4 times as large as the previous real and imaginary part. The quaternary digits in binary are as follows: 0: 00, 1: 01, 2: 10 & 3: 11.

Breakdown of digit positions:

re   im       16 -8i  -4  2i   1 -0.5i, etc.
 4    0        1   0   3   0   0        (quaternary representation)
              01  00  11  00  00        (binary representation)

The number 100110000 is 1x16 + 3x-4 = 16 + -12 = 4.

re   im       16 -8i  -4  2i   1 -0.5i, etc.
 0    5        0   0   0   3   0   2    (quaternary representation)
              00  00  00  11  00 .10    (binary representation)

The number 1100.1 is 3x2i + 2x-0.5i = 6i + -i = 5i.

Your code will take a pair of numbers, which could be integer or floating point, and will output the complex number as a string of binary digits. The first number will be real, the second input number will be the imaginary value. A binary point must only be printed if there are non-zero number positions below 1 (i.e. if any of the positions for -0.5i, -0.25, 0.125i, etc. have a non-zero digit). Leading and trailing zeros are not allowed, except for a single zero digit immediately before the binary point if there are no other digits. The output must not start with a binary point (*00.1 - wrong, 0.1 - right, *.1 - wrong, *0.10 - wrong). You may assume that all input numbers will have finite binary representations.

Test numbers:

re   im            output
 0    0                 0
 1    0                 1
 2    0                10
 3    0                11
 4    0         100110000
-1    0             10011
-2    0             10010
-3    0             10001
 0    1               100.1
 0    2               100
 0    3              1000.1
 0    4              1000
 0   -1                 0.1
 0   -2           1001100
 0   -3           1001100.1
 3    4              1011
 4    3         100111000.1
 6   -9         101110010.1
-6    9       10011100110.1
-9   -6           1110111
 0.5 14.125   10011001101.001001

Note: The output of all integer values will end in .1 if the imaginary part is odd.

Standard code-golf.

\$\endgroup\$
  • 4
    \$\begingroup\$ This is a good challenge, but the explanation could be a whole lot clearer. You should clarify the process: it goes from complex numbers, to an interleaved quaternary representation, to a binary representation mapping 0 → 00, 1 → 01, 2 → 10, 3 → 11. \$\endgroup\$ – Lynn Jan 11 '16 at 3:20
  • \$\begingroup\$ @Mauris I've made a whole bunch of edits to address your comment. Let me know if I can improve it further. \$\endgroup\$ – CJ Dennis Jan 11 '16 at 10:32
  • 2
    \$\begingroup\$ What if it is recurring in binary? \$\endgroup\$ – Leaky Nun Apr 29 '16 at 11:37
  • 1
    \$\begingroup\$ @LeakyNun It says right in the challenge: "You may assume that all input numbers will have finite binary representations." \$\endgroup\$ – user45941 Nov 4 '16 at 17:43
2
\$\begingroup\$

JavaScript (ES6), 340 bytes

f=x=>[0,...x.toString(16)].reverse().map(d=>s=d<'.'?s:d<`0`?d+s.slice(0,-1):`${(c=+`0x${d}`+(c>>4)+m^m)>>2&3}${c&3}`+s,c=s='.',m=x<0?3:12)&&s
g=(s,t,n=s.indexOf`.`,m=t.indexOf`.`)=>n<m?g(0+s,t):n>m?g(s,0+t):t[s.length]?g(s+0,t):s.replace(/\d/g,(c,i)=>`${t[i]>>1}${t[i]&1}${c>>1}${c&1}`).replace(/^0+(\d)|\.?0*$/g,'$1')
(r,i)=>g(f(r),f(i/2))

f converts a number into base -4 (with trailing . if the number is an integer). g takes two base -4 numbers, pads them at both ends to the same length and . position, shuffles the digits together, converts everything from base 4 to base 2, then finally strips leading and trailing zeros.

Explanation: To represent the given complex number in modified-base 2i we need to represent the real part and half of the complex part (i.e. dividing the imaginary part by 2i) in base 2i² (i.e. -4), shuffle the digits together, and then convert them from base 4 to base 2. To represent a real number in base -4 we start with the base 4 conversion. Alternate digits have the correct sign (in the case of a positive number, these are the digits in the even positions; in the case of a negative number, these are the digits in the odd positions) but the remaining digits have the wrong sign and a correction needs to be applied. Examples:

 0 -> 000 -> 000 (no correction needed)
 4 -> 010 -> 130 }
 8 -> 020 -> 120 } (correction includes carry)
12 -> 030 -> 110 }

As you can see, the correction is 8 minus the original digit, mod 8. However a slightly more convenient calculation is the original digit, plus 3, xor 3 (indeed in 32-bit integer arithmetic we could simply write +0xCCCCCCCC^0xCCCCCCCC to convert the entire number in one go). Finally as the correction applies to alternate digits it is simpler to do an initial conversion to base 16 which automatically picks up pairs of base 4 digits, then correct using a factor of either 3 or 0xC as appropriate. It just remains to ignore the - sign.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Perl - 313 bytes

Since no-one has posted an answer yet I thought I'd kick it off myself.

$r=$ARGV[0];$i=$ARGV[1]/2;$m=1;while($r!=int($r)||$i!=int($i)){$c++;$m*=-1;$i*=4;$r*=4}while($r||$i){$r-=($d[$n++]=$r/$m%4)*$m;$i-=($d[$n++]=$i/$m%4)*$m;$m*=-4}$_=join("",map({sprintf"%02b",$_}reverse splice(@d,$c*2)))||"0";@d and$_.=".".join("",map({sprintf"%02b",$_}reverse@d));s/^0+1/1/;s/(\.\d*1)0+$/$1/;print

I'm sure there are lots of opportunities to golf this further.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.