Keep It Simple, Stupid PerlMonks

### Re: Zeckendorf representation

by ambrus (Abbot)
 on Aug 25, 2012 at 11:38 UTC ( #989716=note: 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) = @_;
}

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__

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!

Create A New User
Node Status?
node history
Node Type: note [id://989716]
help
Chatterbox?
 [choroba]: Programming is dangerous.

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (6)
As of 2018-03-24 12:22 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
When I think of a mole I think of:

Results (298 votes). Check out past polls.

Notices?