Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??

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__

In reply to Re: Zeckendorf representation by ambrus
in thread Zeckendorf representation by thmsdrew

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others having an uproarious good time at the Monastery: (4)
    As of 2014-09-20 02:49 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      How do you remember the number of days in each month?











      Results (152 votes), past polls