http://www.perlmonks.org?node_id=989716


in reply to Zeckendorf representation

This is indeed the easy way to convert a perl number to Zeckendorf represenation.

However, real men take the hard way, so let's do the conversion by doing arithmetic on Zeckendorf representated numbers.

#!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( "447646609612720026679772188216156319579732822483159870068 +013" . "998208154068081506426020644244060537628059907897697264231 +688"); } $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__

Replies are listed 'Best First'.
Re^2: Zeckendorf representation
by thmsdrew (Scribe) on Aug 27, 2012 at 03:43 UTC

    Awesome! Thanks for flexing your true manliness!