The Imaginary Quartet

Wherein we reveal perfectly normal looking numbers to hold within them complex truths that bend the imagination…

THE WEEKLY CHALLENGE – PERL & RAKU #178 Task 1

---

“Realism is a bad word. In a sense everything is realistic. I see no line between the imaginary and the real.”

— Federico Fellini

---

Quater-imaginary Base

Submitted by: Mohammad S Anwar

Write a script to convert a given number (base 10) to quater-imaginary base number and vice-versa. For more informations, please checkout wiki page.

For example,

$number_base_10 = 4
$number_quater_imaginary_base = 10300

Background

Wow. Well this has been a wild ride. I laughed — I cried — I looked at the page and reread what I had in front of me yet again. I found other sources and periphrial topics. I hunted down Knuth’s original paper and read that. It’s really such an… interesting piece of math.

As it is, some of our previous efforts here at the PWC have introduced me to various ideas in alternate bases. From the very beginning in PWC we converted to base-35. Along the way I wrote base-conversion tools that evolved and became rarefied. You know what would make a really interesting numbering system? Using prime numbers. You could describe any number by the exponent values in its prime factorization, with the primes each assigned fixed positions. Or Fibonacci numbers. Yes you can construct an insane numbering system from these things too.

Today, however we have a brace of novel ideas that link together. The first is the idea of negative bases. How does that work? Well, the same as any other, really. If the base is negative, than given a positional expansion:

xyz_base = x * base² + y * base¹ + z * base⁰

every other value will wind up negative, and hence be subtracted,

xyz_base = x * |base|² – y * |base|¹ + z * |base|⁰

because a negative value raised to an even power will be positive, and to any other negative.

This, interestingly enough, allows us to write negative values without designating a special sign for them.

This leads us to an application, base (-2) or negabinary, which because of the aforementioned property is occasionally of interest to computer scientists who are sick of twos-complement for one reason or another. It’s intriguing in a number of ways, and has some interesting properties, but never much caught on in computing due to difficulty in division.

More immediate to the task at hand is base (-4), or negaquaternary. Having four available values for each digit does condense things a bit. We’ll be using this later.

Wait what? Why, for all that is good and holy, WHY?

Because Donald Knuth wasn’t satisfied with simply toying around in negabinary, I suppose, and wanted to take matters into a different dimension. Off the line, that is, up and into the complex plane.

Complex numbers are constructed from two values, a real and an imaginary component. The real part is just a number as we know it, but the imaginary part is a real number multipllied by the square root of negative 1, denotated i.

Imaginary numbers, as it works out, can be an extremely useful idea.

So what we’re talking about here is really just the same conceptualization of negative bases mapped on over. How’s that work, you ask? By making the base 2i.

As i² = -1, every other position in a positional expansion here is both real and negative. And let me tell you, I know a thing or two about being real negative. Game recognizes game. However in this case every other real position will be a negative number squared, and hence will become positive. The imaginary comonents follow the same alternating pattern as well.

So in the same way that by alternately adding and subtracting values we can home in on any real value in negaquaternary, we can similarly home in on any real value for the complex component, all with only the digits 0,1, sometimes 2 and 3 and perhaps a lot of space.

Knuth originally commented in his 1955 paper that the quater-imaginary number system could be potentially quite useful due to its ease in multiplication and addition, which is remarkably straighforward. However a graceful technique for division eluded him, and to this day quater-imaginary numbers remain largely a mathematical curiosity.

METHOD

In this task, however, we are only getting our feet wet, as we are asked to convert base-10 real numbers to their quater-imaginary equivalent and back. Real numbers are still represented on the complex plane, of course, being a real number coupled with an imaginary value set to 0. Thus those alternating positions holding the complex components will all be 0. The remaining positions, viewed skipping over the zeros , will be the decimal number converted to negaquaternary.

Converting bases is old hat by this point: we divide out and append the remainders to the converted value. There is one twist, though, in that for this to work the remainder must be positive. Should the remainder be negative, we need to carry a digit from the quotient backwards, subtracting 1 from the quotient and adding 4 to the remainder. With this additional new step everything works out properly.

To convert back to decimal there is no similar problem with powers, so like any other conversion we raise (-4) to the power of the position and multiply by the value found there, adding the result, be it sometimes positive, sometimes negative, to the decimal value.

PERL 5 SOLUTION

use warnings;
use strict;
use utf8;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';

## a spread of values converted to quater-imaginary and back again

say " dec : quater-i   : dec ";
say "-----+------------+-----";
for (-16..16) {
    my $qi = dec2quater_i( $_ );
    say sprintf "%4d : %-10d : %d", $_, $qi, quater_i2dec( $qi );
    
}


sub dec2quater_i ( $num ) {
## variant on normal base conversion
## non-imaginary integers only!
## converts from base-10 to quater-imaginary
## converts to base -4 and then inserts 0s between digits for +i components 
    my $rem;
    my $quot;
    my @nqt;
    
    ## divide out -4s and save remainders
    ## remainders must be positive
    while ( $num != 0  ) {
        $quot = int($num / -4);
        ($num, $rem) = ($quot, $num - ($quot * -4));   
        if ($rem < 0) {
            ## flip remainder to positive if necessary (subtract -4 and carry)
            ($num, $rem) = ($num + 1, $rem + 4) 
        }
        unshift @nqt, $rem;
    }
    return scalar @nqt          ## required to ensure 0 value
        ? join '0', @nqt
        : 0 ;               
}

sub quater_i2dec( $num ) {

## non-imaginary integers only!
## converts quater-imaginary to non-imaginary base-10
## strips +i components (which will be zeros) and converts from base -4

    ## filter out every other position
    my $i = 1;
    my @num = grep { $i++ & 1 } split //, $num; 
    
    ##  convert by computing expanded form
    my $out;
    my $pos = 0;
    for ( reverse @num ) {
        $out += $_ * (-4) ** $pos++;
    }
    
    return $out;
}

The results are reasonably wild. Here we use our converter to create quater-imaginary numbers and then convert those same numbers back to decimal.

 dec : quater-i   : dec 
-----+------------+-----
 -16 : 1030000    : -16
 -15 : 1030001    : -15
 -14 : 1030002    : -14
 -13 : 1030003    : -13
 -12 : 300        : -12
 -11 : 301        : -11
 -10 : 302        : -10
  -9 : 303        : -9
  -8 : 200        : -8
  -7 : 201        : -7
  -6 : 202        : -6
  -5 : 203        : -5
  -4 : 100        : -4
  -3 : 101        : -3
  -2 : 102        : -2
  -1 : 103        : -1
   0 : 0          : 0
   1 : 1          : 1
   2 : 2          : 2
   3 : 3          : 3
   4 : 10300      : 4
   5 : 10301      : 5
   6 : 10302      : 6
   7 : 10303      : 7
   8 : 10200      : 8
   9 : 10201      : 9
  10 : 10202      : 10
  11 : 10203      : 11
  12 : 10100      : 12
  13 : 10101      : 13
  14 : 10102      : 14
  15 : 10103      : 15
  16 : 10000      : 16