# Fibonacci string

#### Do you have a question? Post it now! No Registration Necessary.  Now with pictures!

•  Subject
• Author
• Posted on

Here's a fun fact I ran across in the book _The Golden Ratio_, by
Mario Livio.  Take the string '1' and replace it with '10'.
Thereafter, replace any occurrence of '1' with '10' and '0' with '1'.
Then count the number of 0s and 1s in the string.  You get a
Fibonacci sequence for each count (offset by one iteration).

Here's Perl code to do it.  You get about the same results if you

use strict;
use warnings;

my \$v = '1';
for (1 .. 20) {
my (\$n0, \$n1) = (0, 0);
\$v = join '',
map {
if (\$_) {
\$n1++;
'10';
}
else {
\$n0++;
'1';
}
} split //, \$v;
printf "%10d %10d\n",  \$n0, \$n1;
}

--
David Wall

## Re: Fibonacci string

David K. Wall wrote:

Very cool.  Thanks!

wana

## Re: Fibonacci string

David K. Wall wrote:

You can make that shorter and faster:

my \$v = '1';
for ( 1 .. 20 ) {
printf "%10d %10d\n", \$v =~ y/0//, \$v =~ y/1//;
\$v =~ s/([01])/ \$1 ? '10' : '1' /eg;
}

:-)

John
--
use Perl;
program
fulfillment

## Re: Fibonacci string

We're not worthy !!

--
unix@zeouane.org

## Re: Fibonacci string

John W. Krahn wrote:

A bit faster.   :-)

my \$v = '1';
for ( 1 .. 20 ) {
printf "%10d %10d\n", \$v =~ y/0//, \$v =~ y/1//;
\$v =~ s/./ \$& ? '10' : '1' /eg;
}

John
--
use Perl;
program
fulfillment

## Re: Fibonacci string

I bow to greater perl-fu, but with the caveat that I was more
interested in making the idea clear than in coming up with a fast
implementation.  I'd accuse you of having too much time on your hands
if I weren't guilty of the same sort of thing myself.

## Re: Fibonacci string

John W. Krahn (someone@example.com) wrote on MMMMCCLXXXIV September
##
##  A bit faster.   :-)
##
##  my \$v = '1';
##  for ( 1 .. 20 ) {
##       printf "%10d %10d\n", \$v =~ y/0//, \$v =~ y/1//;
##       \$v =~ s/./ \$& ? '10' : '1' /eg;
##  }

Much faster:

my \$v = '1';
for ( 1 .. 20 ) {
printf "%10d %10d\n", \$v =~ y/0//, \$v =~ y/1//;
\$v =~ s/1/12/g; \$v =~ y/02/10/;
}

Benchmark:

#!/usr/bin/perl

use strict;
use warnings;
no warnings qw /syntax/;

use Benchmark qw 'cmpthese';

our @a = (1, 10);
our (\$j, \$a);
our \$max = 20;

cmpthese -5 => {
john    => '\$j = 1; for (1 .. \$max) {\$j =~ s/./\$& ? "10" : "1"/eg;}',
abigail => '\$a = 1; for (1 .. \$max) {\$a =~ s/1/12/g; \$a =~ y/02/10/}',
};

die unless \$a eq \$j;

__END__
Rate    john abigail
john    21.3/s      --    -62%
abigail 55.4/s    160%      --

Abigail
--
perl -we 'eval {die ["Just another Perl Hacker\n"]}; print \$}[\$#}}]'

## Re: Fibonacci string

Abigail wrote:

Thanks Abigail,

I wonder if Ton can come up with a Perl program that does the same thing
in ~50 characters?  :-)

John
--
use Perl;
program
fulfillment

## Re: Fibonacci string

Avoiding s/// altogether gains another factor of 50 or so:

my \$v = 1;
for ( 1 .. 20 ) {
printf "%10d %10d\n", \$v =~ y/0//, \$v =~ y/1//;
\$_ .= length > 1 ? substr( \$_, 0, tr/1/1/) : 0 for \$v;
}

Benchmark:

#!/usr/bin/perl
use strict; use warnings; \$| = 1; # @^~`
use Vi::QuickFix;

use Benchmark qw 'cmpthese';

our (\$j, \$a, \$b);
our \$max = 20;

cmpthese -5 => {
john    => '\$j = 1; for (1 .. \$max) {\$j =~ s/./\$& ? "10" : "1"/eg;}',
abigail => '\$a = 1; for (1 .. \$max) {\$a =~ s/1/12/g; \$a =~ y/02/10/}',
anno    => '\$b = 1; for (1 .. \$max) ' .
'{ \$_ .= length() > 1 ? substr( \$_, 0, y/1/1/) : 0 for \$b}',
};

die unless \$a eq \$j and \$b eq \$j;
__END__

Anno

## Re: Fibonacci string

If we're allowed to change the algorithm as long as the same strings
are produced, I think I can do even better:

my \$v = 1; my \$v2 = 0;
for ( 1 .. 20 ) {
printf "%10d %10d\n", \$v =~ y/0//, \$v =~ y/1//;
my \$t = \$v; \$v .= \$v2; \$v2 = \$t;
}

Benchmark:

#!/usr/bin/perl
use strict;
use warnings;
use Benchmark qw 'cmpthese';

our (\$j, \$a, \$b, \$c);
our \$max = 10;

cmpthese -3 => {
john    => '\$j = 1; for (1 .. \$max) {\$j =~ s/./\$& ? "10" : "1"/eg}',
abigail => '\$a = 1; for (1 .. \$max) {\$a =~ s/1/12/g; \$a =~ y/02/10/}',
anno    => '\$b = 1; for (1 .. \$max) {\$_ .= length() > 1 ? substr( \$_, 0,
y/1/1/) : 0 for \$b}',
ilmari  => '\$c = 1; my \$c2 = 0; for (1 .. \$max) {my \$t = \$c; \$c .= \$c2;
\$c2 = \$t}',
};

die unless \$a eq \$j and \$b eq \$j and \$c eq \$j;

__END__

--
Ilmari Karonen

## Re: Fibonacci string

I think we should *always* consider a change in algorithm when playing
optimization games.  It is the most promising approach, if applicable.
This thread has shown it again.

Ah, an append-only solution.  Yes, it beats my fastest version

use constant PHI => ( 1 + sqrt(5))/2;
my \$c = 1;
for (1 .. 20) {
\$c .= length( \$c) > 1 ? substr( \$c, 0, int 0.5 + length()/PHI) : 0;
}

slightly.

Anno

## Re: Fibonacci string

I think I know perl pretty well, but I have to carefully study most of
these alternatives to see how they work! You guys are amazing!

Tom

## Re: Fibonacci string

I think we should *always* consider a change in algorithm when playing
optimization games.  It is the most promising approach, if applicable.
This thread has shown it again.

Ah, an append-only solution.  Yes, it beats my fastest version

use constant PHI => ( 1 + sqrt(5))/2;
my \$c = 1;
for (1 .. 20) {
\$c .= length( \$c) > 1 ? substr( \$c, 0, int 0.5 + length( \$c)/PHI) : 0;
}

slightly.

Anno

## Re: Fibonacci string

Very nice...

I might do it this way and let the regex engine do some of the heavy
lifting.. :-)

use strict;
use warnings;

\$_=0;
foreach my \$loop ( 1 .. 20 )
{
s/(.)/\$1?10:1/eg;
my \$ones = tr/1//;
printf "%10d %10d\n", length() - \$ones, \$ones;
}

--
Darren Dunham                                           ddunham@taos.com
Senior Technical Consultant         TAOS            http://www.taos.com /
Got some Dr Pepper?                           San Francisco, CA bay area
< This line left intentionally blank to confuse you. >

## re: fibonacci string

Well, lessee...

If string v has n0 zeroes and n1 ones, substituting all ones with
'10' gives n1 ones and n1 zeroes.  Substituting zeroes with '1' adds
another n0 ones (and no zeroes). So the number n0' of zeroes in the
next string is n1, and the number n1' of ones is n0 + n1.

If (n0, n1) are subsequent Fibonacci numbers, then (n0', n1') =
(n1, n0 + n1) are the next two Fibonacci numbers.  Since this is true
for the very first string '1', with 0 = fib[ 0] zeroes and 1 = fib[ 1]
ones, it is true for all strings thus generated.

The observation that it doesn't matter where the zeroes and ones
appear in the strings leads to a solution that doesn't use s///:

my \$v = '1';
for ( 1 .. 20 ) {
my \$n0 = \$v =~ tr/0/1/;
printf "%10d %10d\n",  \$n0, length( \$v) - \$n0;
\$v .= '0' x ( length( \$v) - \$n0);
}

I generates a different sequence of strings \$v (less fancy patterns),
but with the same distribution of ones and zeroes.  If you prefer
to call it "cheating" I won't object.

Anno

## Re: fibonacci string

Anno Siegel wrote:

Not bad. Very nice to see that there are still people around who can
_prove_ that an algorithm does what it is supposed to do rather than
deduce from a small set of results that all results follow a pattern.

Congratulations!

No, I'd call this professionalism.
I wish I'd be as thorough as you.

Josef
--
Josef Möllers (Pinguinpfleger bei FSC)
If failure had no penalty success would not be a prize
-- T.  Pratchett

## Re: fibonacci string

Agreed.  I just wanted to generate it so I could look at the pattern
for longer strings than the book contained.

The original string does have some interesting properties that do
depend on the order of the ones and zeroes.  Some of them are
described at this URL:
http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibrab.html
The book I was reading mentions a few others.

Sorry, this is getting a bit removed from Perl.

## Re: fibonacci string

Yes, but in an interesting way.  I'll stick with it for one more remark.

The sequence of \$v, as defined by the substitution rule, can also
be generated by concatenating strings that have already be generated.
The rule is exactly that for generation of fibonacci numbers, with
addition replaced by concatenation.  In particular (code untested,
but the algorithm is):

my ( \$prev, \$v) = qw( 0 1);
for ( 1 .. 20 ) {
printf "%10d %10d\n", \$v =~ y/0//, \$v =~ y/1//;
( \$prev, \$v) = ( \$v, \$v . \$prev);
}

I bet that's one of the interesting properties mentioned on the web site.
(or the book).  I haven't proved any of this, just observed it, but an
inductive proof seems entirely feasible.  It should create the original
sequence at the speed of the "cheating" solutions shown above.

Anno

## Re: fibonacci string

comp.lang.perl.misc:

[...]

Well, it's only a step away from generating the fibonacci numbers the
way they are defined and creating \$v on the side:

my( \$n0, \$n1) = ( 0, 1);
for ( 1 .. 20 ) {
my \$v = '1' x \$n1 .  '0' x \$n0;
printf "%10d %10d\n",  \$n0, \$n1;
( \$n0, \$n1) = ( \$n1, \$n0 + \$n1);
}

That generates the same sequence \$v as above, and it *would* be cheating.
It *is* dramatically faster (either way) than the s///-solutions we've seen.
These strings get large fast, and s/// does a lot of tail-copying for
all the size-changing replacements.

BTW, I have no idea how this subthread lost connection to the main thread
on the subject, at least for my newsreader.

Anno