P is for Practical PerlMonks

### Zeckendorf representation

by thmsdrew (Scribe)
 on Aug 24, 2012 at 15:16 UTC ( #989567=CUFP: print w/replies, xml ) Need Help??

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

Replies are listed 'Best First'.
Re: Zeckendorf representation
by jwkrahn (Monsignor) on Aug 25, 2012 at 02:58 UTC
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] }

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.

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.
Re: Zeckendorf representation
by Athanasius (Archbishop) on Aug 25, 2012 at 04:30 UTC

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!

Athanasius <°(((><contra mundum

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?

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,

Athanasius <°(((><contra mundum

Re: Zeckendorf representation
by ambrus (Abbot) on Aug 25, 2012 at 11:38 UTC

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.

{ # a natural number represented as a Zeckendorf sum package Zeckendorf;
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; } }
{ # 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__

Awesome! Thanks for flexing your true manliness!

Re: Zeckendorf representation (cool!)
by tye (Sage) on Aug 24, 2012 at 22:08 UTC

Very cool! Thanks.

- tye

Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: CUFP [id://989567]
Approved by moritz
Front-paged by Arunbear
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others chanting in the Monastery: (3)
As of 2023-12-09 05:23 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
What's your preferred 'use VERSION' for new CPAN modules in 2023?

Results (37 votes). Check out past polls.

Notices?