Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister
 
PerlMonks  

Re: Zeckendorf representation

by ambrus (Abbot)
on Aug 25, 2012 at 11:38 UTC ( #989716=note: print w/ replies, xml ) Need Help??


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__


Comment on Re: Zeckendorf representation
Select or Download Code
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!

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://989716]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (14)
As of 2015-07-30 14:38 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (271 votes), past polls