98 lines
2.2 KiB
Perl
98 lines
2.2 KiB
Perl
use v5.36;
|
|
|
|
package Zeckendorf;
|
|
use overload qw("" zstring + zadd - zsub ++ zinc -- zdec * zmul / zdiv ge zge);
|
|
|
|
sub new ($class, $value) {
|
|
bless \$value, ref $class || $class;
|
|
}
|
|
|
|
sub zinc ($self, $, $) {
|
|
local $_ = $$self;
|
|
s/0$/1/ or s/(?:^|0)1$/10/;
|
|
1 while s/(?:^|0)11/100/;
|
|
$$self = $self->new( s/^0+\B//r )
|
|
}
|
|
|
|
sub zdec ($self, $, $) {
|
|
local $_ = $$self;
|
|
1 while s/100(?=0*$)/011/;
|
|
s/1$/0/ || s/10$/01/;
|
|
$$self = $self->new( s/^0+\B//r )
|
|
}
|
|
|
|
sub zadd ($self, $other, $) {
|
|
my ($x, $y) = map $self->new($$_), $self, $other;
|
|
$x++, $y-- while $$y;
|
|
$x
|
|
}
|
|
|
|
sub zsub ($self, $other, $) {
|
|
my ($x, $y) = map $self->new($$_), $self, $other;
|
|
$x--, $y-- while $$y;
|
|
$x
|
|
}
|
|
|
|
sub zmul ($self, $other, $) {
|
|
my ($x, $y) = map $self->new($$_), $self, $other;
|
|
my $product = Zeckendorf->new(0);
|
|
$product = $product + $x, $y-- while $y;
|
|
$product
|
|
}
|
|
|
|
sub zdiv ($self, $other, $) {
|
|
my ($x, $y) = map $self->new($$_), $self, $other;
|
|
my $quotient = Zeckendorf->new(0);
|
|
$quotient++, $x = $x - $y while $x ge $y;
|
|
$quotient
|
|
}
|
|
|
|
sub zge ($self, $other, $) {
|
|
my $l; $l = length $$other if length $other > ($l = length $$self);
|
|
0 x ($l - length $$self) . $$self ge 0 x ($l - length $$other) . $$other;
|
|
}
|
|
|
|
sub asdecimal ($self) {
|
|
my($aa, $bb, $n) = (1, 1, 0);
|
|
for ( reverse split '', $$self ) {
|
|
$n += $bb * $_;
|
|
($aa, $bb) = ($bb, $aa + $bb);
|
|
}
|
|
$n
|
|
}
|
|
|
|
sub fromdecimal ($self, $value) {
|
|
my $z = $self->new(0);
|
|
$z++ for 1 .. $value;
|
|
$z
|
|
}
|
|
|
|
sub zstring { ${ shift() } }
|
|
|
|
package main;
|
|
|
|
for ( split /\n/, <<END ) # test cases
|
|
1 + 1
|
|
10 + 10
|
|
10100 + 1010
|
|
10100 - 1010
|
|
10100 * 1010
|
|
100010 * 100101
|
|
10100 / 1010
|
|
101000 / 1000
|
|
100001000001 / 100010
|
|
100001000001 / 100101
|
|
END
|
|
{
|
|
my ($left, $op, $right) = split;
|
|
my ($x, $y) = map Zeckendorf->new($_), $left, $right;
|
|
my $answer =
|
|
$op eq '+' ? $x + $y :
|
|
$op eq '-' ? $x - $y :
|
|
$op eq '*' ? $x * $y :
|
|
$op eq '/' ? $x / $y :
|
|
die "bad op <$op>";
|
|
printf "%12s %s %-9s => %12s in Zeckendorf\n", $x, $op, $y, $answer;
|
|
printf "%12d %s %-9d => %12d in decimal\n\n",
|
|
$x->asdecimal, $op, $y->asdecimal, $answer->asdecimal;
|
|
}
|