Zeckendorf representation

[thmsdrew]

The following script employs Zeckendorf's_theorem and prints the Zeckendorf representation for a given number.

#!/usr/bin/perl

use strict;
use warnings;

zeck($ARGV[0]);

sub zeck {
    if (is_fibonnacci($_[0])) {
        print "$_[0]\n";
        exit;
    }
    my $count = 0;
    my $prev = 0;
    my $curr = 0;
    while (($curr = fibonnacci($count)) < $_[0]) {
        $prev = $curr;
        $count++;
    }
    print "$prev\n";
    zeck($_[0] - $prev);
}

sub fibonnacci {
    my $a = 0;
    my $b = 1;
    for (0..$_[0]) {
        my $c = $a;
        $a = $b;
        $b = $c + $b;
    }
    return $a;
}

sub is_fibonnacci {
    my $plus = (5 * $_[0] * $_[0]) + 4;
    my $mins = (5 * $_[0] * $_[0]) - 4;
    return is_perfect_square($plus) || is_perfect_square($mins);
}

sub is_perfect_square {
    my $sqrt = int(sqrt($_[0]));
    return $sqrt * $sqrt == $_[0];
}

[jwkrahn]

sub is_fibonnacci {
    my $plus = (5 * $_[0] * $_[0]) + 4;
    my $mins = (5 * $_[0] * $_[0]) - 4;
    return is_perfect_square($plus) | is_perfect_square($mins);
}

No need to calculate 5 * $_[0] * $_[0] twice, and you probably meant to use the logical or operator instead of the bit-wise or operator.

sub is_fibonnacci {
    my $plus = (5 * $_[0] * $_[0]) + 4;
    my $mins = $plus - 8;
    return is_perfect_square($plus) || is_perfect_square($mins);
}

(The logical operators short-circuit so is_perfect_square($mins) will only execute if is_perfect_square($plus) is true.)





sub is_perfect_square {
    my $sqrt = int(sqrt($_[0]));
    return $sqrt * $sqrt == $_[0];
}

Or just:

sub is_perfect_square { int( $_[0] ** .5 ) ** 2 == $_[0] }

[thmsdrew]

Thanks for your input! What do you mean by "short circuit"? Also, the difference between your is_perfect_square sub and mine is that mine is much more clear. I can afford the extra line for a bit of clarity.

[lidden]

What do you mean by "short circuit"?

It means that the part after || will only be evaluated if it is needed know the result of the operator. In the case of the or-operator the second half is redundant if the first is true, since the total will be true no matter what the second part is.

[Athanasius]

Hello thmsdrew,

I agree with tye — this is cool! And I’m impressed with the speed at which the calculations are done; this calculation:

zeck(1019377012345) = 956722026041 + 53316291173 + 7778742049 + 113490
+3170 + 267914296 + 102334155 + 39088169 + 14930352 + 514229 + 196418 
++ 46368 + 17711 + 6765 + 987 + 377 + 55 + 21 + 8 + 1

(see code below) takes less than a second on my machine!

My only quibble is with the design of the zeck subroutine. A sub containing exit is a red flag for me, and even print statements are better deferred to the caller. To my mind, zeck should return the sum as a list of Fibonacci numbers. And in Perl, this is surprisingly easy to do:

my @zeck = zeck($ARGV[0]);
print 'zeck(',  $ARGV[0], ') = ', join(' + ', @zeck), "\n";

sub zeck
{
    return $_[0] if is_fibonnacci($_[0]);

    my $count = 0;
    my $prev  = 0;
    my $curr  = 0;

    while (($curr = fibonnacci($count)) < $_[0])
    {
        $prev = $curr;
        $count++;
    }

    return ($prev, zeck($_[0] - $prev));
}

Note that by restricting sub zeck to a single responsibility, the code becomes both more flexible and shorter.

Again, thanks for a cool demo!

P.S. I actually find jwkrahn’s one-line version of sub is_perfect_square to be clearer than the original. I guess clarity is in the eye of the beholder!

[thmsdrew]

Thank you for that. I see what you mean, and prefer yours. Why do you say that a sub containing exit is a red flag?

[Athanasius]

Why do you say that a sub containing exit is a red flag?

From exit:

Don't use exit to abort a subroutine if there's any chance that someone might want to trap whatever error happened. Use die instead, which can be trapped by an eval.

Think of a subroutine as a server providing a service to its clients (callers). It’s up to the client to decide how to handle the information returned by its server. Even an exception (thrown by die) is information which the client can use or ignore as desired. The server should never preempt the client in determining how to proceed.

Hope that helps,

[ambrus]

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.

Read more... (235 Bytes)

{ # a natural number represented as a Zeckendorf sum
package Zeckendorf;

Read more... (1064 Bytes)

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;
}

}

Read more... (700 Bytes)

{ # 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__

[thmsdrew]

Awesome! Thanks for flexing your true manliness!

[tye]

Very cool! Thanks.