How to resolve the algorithm Zeckendorf arithmetic step by step in the Raku programming language

Published on 12 May 2024 09:40 PM

How to resolve the algorithm Zeckendorf arithmetic step by step in the Raku programming language

Table of Contents

Problem Statement

This task is a total immersion zeckendorf task; using decimal numbers will attract serious disapprobation. The task is to implement addition, subtraction, multiplication, and division using Zeckendorf number representation. Optionally provide decrement, increment and comparitive operation functions. Like binary 1 + 1 = 10, note carry 1 left. There the similarity ends. 10 + 10 = 101, note carry 1 left and 1 right. 100 + 100 = 1001, note carry 1 left and 2 right, this is the general case. Occurrences of 11 must be changed to 100. Occurrences of 111 may be changed from the right by replacing 11 with 100, or from the left converting 111 to 100 + 100; 10 - 1 = 1. The general rule is borrow 1 right carry 1 left. eg: A larger example: Here you teach your computer its zeckendorf tables. eg. 101 * 1001: Lets try 1000101 divided by 101, so we can use the same table used for multiplication. Efficient algorithms for Zeckendorf arithmetic is interesting. The sections on addition and subtraction are particularly relevant for this task.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Zeckendorf arithmetic step by step in the Raku programming language

Source code in the raku programming language

my $z1 = '1'; # glyph to use for a '1'
my $z0 = '0'; # glyph to use for a '0'

sub zorder($a) { ($z0 lt $z1) ?? $a !! $a.trans([$z0, $z1] => [$z1, $z0]) }

######## Zeckendorf comparison operators #########

# less than
sub infix:($a, $b) { $a.&zorder lt $b.&zorder }

# greater than
sub infix:($a, $b) { $a.&zorder gt $b.&zorder }

# equal
sub infix:($a, $b) { $a eq $b }

# not equal
sub infix:($a, $b) { $a ne $b }

######## Operators for Zeckendorf arithmetic ########

# post increment
sub postfix:<++z>($a is rw) {
    $a = ("$z0$z0"~$a).subst(/("$z0$z0")($z1+ %% $z0)?$/,
      -> $/ { "$z0$z1" ~ ($1 ?? $z0 x $1.chars !! '') });
    $a ~~ s/^$z0+//;
    $a
}

# post decrement
sub postfix:<--z>($a is rw) {
    $a.=subst(/$z1($z0*)$/,
      -> $/ {$z0 ~ "$z1$z0" x $0.chars div 2 ~ $z1 x $0.chars mod 2});
    $a ~~ s/^$z0+(.+)$/$0/;
    $a
}

# addition
sub infix:<+z>($a is copy, $b is copy) { $a++z; $a++z while $b--z nez $z0; $a }

# subtraction
sub infix:<-z>($a is copy, $b is copy) { $a--z; $a--z while $b--z nez $z0; $a }

# multiplication
sub infix:<×z>($a, $b) { 
    return $z0 if $a eqz $z0 or $b eqz $z0;
    return $a if $b eqz $z1;
    return $b if $a eqz $z1;
    my $c = $a;
    my $d = $z1;
    repeat { 
         my $e = $z0;
         repeat { $c++z; $e++z } until $e eqz $a;
         $d++z;
    } until $d eqz $b;
    $c
}

# division  (really more of a div mod)
sub infix:($a is copy, $b is copy) {
    fail "Divide by zero" if $b eqz $z0;
    return $a if $a eqz $z0 or $b eqz $z1;
    my $c = $z0;
    repeat { 
        my $d = $b +z ($z1 ~ $z0);
        $c++z;
        $a++z;
        $a--z while $d--z nez $z0
    } until $a ltz $b;
    $c ~= " remainder $a" if $a nez $z0;
    $c
}

###################### Testing ######################

# helper sub to translate constants into the particular glyphs you used
sub z($a) { $a.trans([<1 0>] => [$z1, $z0]) }

say "Using the glyph '$z1' for 1 and '$z0' for 0\n";

my $fmt = "%-22s = %15s  %s\n";

my $zeck = $z1;

printf( $fmt, "$zeck++z", $zeck++z, '# increment' ) for 1 .. 10;

printf $fmt, "$zeck +z {z('1010')}", $zeck +z= z('1010'), '# addition';

printf $fmt, "$zeck -z {z('100')}", $zeck -z= z('100'), '# subtraction';

printf $fmt, "$zeck ×z {z('100101')}", $zeck ×z= z('100101'), '# multiplication';

printf $fmt, "$zeck /z {z('100')}", $zeck /z= z('100'), '# division';

printf( $fmt, "$zeck--z", $zeck--z, '# decrement' ) for 1 .. 5;

printf $fmt, "$zeck ×z {z('101001')}", $zeck ×z= z('101001'), '# multiplication';

printf $fmt, "$zeck /z {z('100')}", $zeck /z= z('100'), '# division';


  

You may also check:How to resolve the algorithm Empty program step by step in the Crystal programming language
You may also check:How to resolve the algorithm Disarium numbers step by step in the Phix programming language
You may also check:How to resolve the algorithm Abundant, deficient and perfect number classifications step by step in the F# programming language
You may also check:How to resolve the algorithm Arithmetic/Integer step by step in the SNUSP programming language
You may also check:How to resolve the algorithm Faulhaber's formula step by step in the GAP programming language