Pathologically Eclectic Rubbish Lister PerlMonks

Comment on

 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) = @_;
}

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)) {
}
\$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;
\$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!
• Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
• Read Where should I post X? if you're not absolutely sure you're posting in the right place.
• 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
• You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
 For: Use: & & < < > > [ [ ] ]
• Link using PerlMonks shortcuts! What shortcuts can I use for linking?

Create A New User
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (3)
As of 2018-03-20 04:09 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
When I think of a mole I think of:

Results (247 votes). Check out past polls.

Notices?