#!perl use warnings; use strict; ##```## { # a natural number represented as a Zeckendorf sum package Zeckendorf; ##``````## 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; } ##``````## 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; } } ##``````## 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; } } ##``````## { # 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__ ```