note
ambrus
<p>
This is indeed the easy way to convert a perl number to Zeckendorf represenation.
<p>
However, [id://849259|real men take the hard way], so let's do the conversion by doing arithmetic on Zeckendorf representated numbers.
<readmore><c>
#!perl
use warnings; use strict;
</c></readmore><c>
{ # a natural number represented as a Zeckendorf sum
package Zeckendorf;
</c><readmore><c>
use warnings; use strict; use 5.012;
use Scalar::Util; use Math::BigInt;
sub _make {
my($o, @v) = @_;
bless \@v, Scalar::Util::blessed($o) || $o;
}
sub zero {
my($o) = @_;
$o->_make();
}
sub one {
my($o) = @_;
$o->_make(1);
}
sub _comps {
my($o, $b) = @_;
my @v = @$o;
my($u, $v) = (0, @v < 44 ? 1 : Math::BigInt->bone);
for my $d (@v) {
$v = $v + $u;
$u = $v - $u;
if ($d) {
&$b($v);
}
}
}
sub str { # return the string representation showing terms
my($o) = @_;
my @r;
$o->_comps(sub { push @r, $_[0] });
@r ? "(" . join(" + ", @r) . ")" : "0";
}
sub val { # return the value as a perl number
my($o) = @_;
my $r = 0;
$o->_comps(sub { $r += $_[0]; });
$r;
}
</c></readmore><c>
sub _norm {
my($o, @v) = @_;
my $a = 1;
while ($a) {
no warnings qw"uninitialized";
$a = 0;
for my $i (keys @v) {
if (1 < $v[$i]) {
$v[$i] -= 2;
$v[$i + 1]++;
if (2 <= $i) {
$v[$i - 2]++;
} elsif (1 <= $i) {
$v[0]++;
}
$a++;
}
if (0 < $v[$i] && 0 < $v[$i + 1]) {
$v[$i]--;
$v[$i + 1]--;
$v[$i + 2]++;
$a++;
}
}
}
$o->_make(@v);
}
sub add { # return the sum of two Zeckendorf objects
my($o, $t) = @_;
my @v = @$o;
my @w = @$t;
for my $i (keys @w) {
$v[$i] += $w[$i];
}
$o->_norm(@v);
}
sub twice {
my($o) = @_;
$o->add($o);
}
our @poweroftwo = (Zeckendorf->one);
sub fromnat { # create a Zeckendorf object from a perl natural number
my($o, $g) = @_;
my $t = 1 + 0 * $g;
my $i = 0;
my $z = Zeckendorf->zero;
while ($t <= $g) {
my $y = $poweroftwo[$i] //= $poweroftwo[$i - 1]->twice;
if (0 < ($t & $g)) {
$z = $z->add($y);
}
$t <<= 1;
$i++;
}
$z;
}
}
</c><readmore><c>
if (0) { # perform some random tests on the Zeckendorf class. disabled by default because slow.
for my $i (1 .. 100) {
my $m = int rand(1e7);
my $x = Zeckendorf->fromnat($m);
$m == $x->val or die;
my $n = int rand(1e7);
my $y = Zeckendorf->fromnat($n);
$n == $y->val or die;
my $s = $m + $n;
my $z = $x->add($y);
$s == $z->val or die;
}
}
</c></readmore><c>
{ # demonstrate
use Math::BigInt;
my $n = 6303152187;
if (0) {
$n = Math::BigInt->new(
"447646609612720026679772188216156319579732822483159870068013" .
"998208154068081506426020644244060537628059907897697264231688");
}
$ARGV[0] and $n = $ARGV[0]; # choose a number, any number
my $z = Zeckendorf->fromnat($n);
$n == $z->val or die;
print $n, " = ", $z->val, " = ", $z->str, ".\n";
}
__END__
</c>
<!-- kw: obfu (?), fibonacci numbers, radix conversion, number system, mathematics -->
989567
989567