File Coverage

blib/lib/Math/NumSeq/SpiroFibonacci.pm
Criterion Covered Total %
statement 65 87 74.7
branch 12 22 54.5
condition 6 18 33.3
subroutine 15 20 75.0
pod 5 7 71.4
total 103 154 66.8


line stmt bran cond sub pod time code
1             # Copyright 2012, 2013, 2014 Kevin Ryde
2              
3             # This file is part of Math-NumSeq.
4             #
5             # Math-NumSeq is free software; you can redistribute it and/or modify
6             # it under the terms of the GNU General Public License as published by the
7             # Free Software Foundation; either version 3, or (at your option) any later
8             # version.
9             #
10             # Math-NumSeq is distributed in the hope that it will be useful, but
11             # WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
12             # or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13             # for more details.
14             #
15             # You should have received a copy of the GNU General Public License along
16             # with Math-NumSeq. If not, see .
17              
18              
19             # cf
20             # A092360 Spiro-tribonacci numbers: a(n) = sum of three previous terms that are nearest when terms arranged in a spiral.
21             # A092369 Spiro-tetranacci numbers: a(n) = sum of four previous terms that are nearest when terms arranged in a spiral.
22             # A094769 Square spiral of sums of selected preceding terms, starting at 0 followed by 1 (a spiral Fibonacci-like sequence).
23              
24              
25             # math-image --values=SpiroFibonacci --output=numbers --size=78
26             #
27             # math-image --values=SpiroFibonacci,recurrence_type=absdiff --output=text --size=60x15
28              
29              
30             package Math::NumSeq::SpiroFibonacci;
31 1     1   1399 use 5.004;
  1         3  
32 1     1   4 use strict;
  1         2  
  1         25  
33              
34 1     1   3 use vars '$VERSION', '@ISA';
  1         1  
  1         74  
35             $VERSION = 72;
36 1     1   4 use Math::NumSeq;
  1         5  
  1         45  
37             @ISA = ('Math::NumSeq');
38             *_to_bigint = \&Math::NumSeq::_to_bigint;
39              
40             # uncomment this to run the ### lines
41             #use Smart::Comments;
42              
43              
44             # use constant name => Math::NumSeq::__('...');
45 1     1   4 use constant description => Math::NumSeq::__('Spiro-Fibonacci recurrence.');
  1         1  
  1         4  
46 1     1   3 use constant default_i_start => 0;
  1         5  
  1         89  
47              
48 1         7 use constant parameter_info_array =>
49             [
50             # { name => 'spiral_type',
51             # type => 'enum',
52             # default => 'square',
53             # choices => ['square','hex'],
54             # },
55             { name => 'recurrence_type',
56             type => 'enum',
57             choices => ['additive','absdiff'],
58             default => 'additive',
59             },
60             { name => 'initial_0',
61             display => Math::NumSeq::__('Initial value 0'),
62             type => 'integer',
63             default => 0,
64             width => 3,
65             description => Math::NumSeq::__('Initial value ...'),
66             },
67             { name => 'initial_1',
68             display => Math::NumSeq::__('Initial value 1'),
69             type => 'integer',
70             default => 1,
71             width => 3,
72             description => Math::NumSeq::__('Initial value ...'),
73             },
74 1     1   3 ];
  1         1  
75              
76             sub characteristic_integer {
77 0     0 0 0 my ($self) = @_;
78             return (_is_integer($self->{'initial_0'})
79 0   0     0 && _is_integer($self->{'initial_1'}));
80             }
81             sub characteristic_smaller {
82 0     0 0 0 my ($self) = @_;
83 0         0 return ($self->{'recurrence_type'} eq 'absdiff');
84             }
85             sub _is_integer {
86 0     0   0 my ($n) = @_;
87 0         0 return ($n == int($n));
88             }
89              
90             # FIXME: absdiff range related to least common multiple, maybe
91             sub values_min {
92 1     1 1 6 my ($self) = @_;
93 1 50 33     9 if ($self->{'initial_0'} >= 0 && $self->{'initial_1'} >= 0) {
94 1         3 return _min (0, $self->{'initial_0'}, $self->{'initial_1'});
95             }
96 0         0 return undef;
97             }
98             sub values_max {
99 0     0 1 0 my ($self) = @_;
100 0 0       0 if ($self->{'recurrence_type'} eq 'absdiff') {
101             return _max (abs($self->{'initial_0'}),
102 0         0 abs($self->{'initial_1'}));
103             } else {
104 0 0 0     0 if ($self->{'initial_0'} <= 0 && $self->{'initial_1'} <= 0) {
105             return _max ($self->{'initial_0'},
106 0         0 $self->{'initial_1'});
107             } else {
108 0         0 return undef;
109             }
110             }
111             }
112             sub _min {
113 1     1   2 my $ret = shift;
114 1         3 while (@_) {
115 2         3 my $next = shift;
116 2 50       6 if ($ret > $next) {
117 0         0 $ret = $next;
118             }
119             }
120 1         3 return $ret;
121             }
122             sub _max {
123 0     0   0 my $ret = shift;
124 0         0 while (@_) {
125 0         0 my $next = shift;
126 0 0       0 if ($next > $ret) {
127 0         0 $ret = $next;
128             }
129             }
130 0         0 return $ret;
131             }
132              
133              
134             #------------------------------------------------------------------------------
135              
136             # cf A079422 cumulative absdiff up to n^2
137             # A094925 hexagonal 1,1 three around a(n-1)
138             # A094926 hexagonal 0,1 three around a(n-1)
139              
140             my %oeis_anum = ('additive,0,1' => 'A078510',
141             # OEIS-Catalogue: A078510
142              
143             'absdiff,0,1' => 'A079421',
144             # OEIS-Catalogue: A079421 recurrence_type=absdiff
145              
146             # all zeros if initial_0 == initial_1 == 0
147             'additive,0,0' => 'A000004',
148             'absdiff,0,0' => 'A000004',
149             # OEIS-Other: A000004 initial_1=0
150             # OEIS-Other: A000004 initial_1=0 recurrence_type=absdiff
151             );
152              
153             sub oeis_anum {
154 1     1 1 4 my ($self) = @_;
155             return $oeis_anum{join(',',
156 1         3 @{$self}{ # hash slice
157 1         1 'recurrence_type',
158             'initial_0',
159             'initial_1'})};
160             }
161              
162              
163             #------------------------------------------------------------------------------
164              
165 1     1   4 use constant 1.02;
  1         12  
  1         30  
166 1     1   5 use constant _UV_LIMIT => (~0 >> 1);
  1         2  
  1         68  
167 1     1   5 use constant _IV_NEG_LIMIT => - (_UV_LIMIT >> 1);
  1         1  
  1         288  
168              
169             # my %spiral_type = (square => { num_sides => 2,
170             # side_longer => -1,
171             # },
172             # hex => { num_sides => 6,
173             # side_longer => 1,
174             # },
175             # );
176              
177             sub rewind {
178 3     3 1 397 my ($self) = @_;
179 3         11 $self->{'i'} = $self->i_start;
180 3         8 $self->{'queue'} = [$self->{'initial_0'}, $self->{'initial_1'}];
181 3         4 $self->{'num_sides'} = 2;
182 3         4 $self->{'side_len'} = 1;
183 3         5 $self->{'side'} = $self->{'num_sides'};
184 3         8 $self->{'count'} = 2;
185             }
186              
187             sub next {
188 24     24 1 389 my ($self) = @_;
189             ### next(): "i=$self->{'i'} side_len=$self->{'side_len'} side=$self->{'side'} count=$self->{'count'}"
190              
191 24         13 my $queue = $self->{'queue'};
192 24         18 my $i = $self->{'i'}++;
193 24 100       31 if ($i < 2) {
194             ### initial queue ...
195 4         8 return ($i, $queue->[$i]);
196             }
197              
198 20         10 my $value;
199 20 50       23 if ($self->{'recurrence_type'} eq 'absdiff') {
200 0         0 $value = abs($queue->[-1] - $queue->[0]);
201             } else {
202 20         16 $value = $queue->[-1] + $queue->[0];
203             }
204 20 50 33     67 if (! ref $value && ($value >= _UV_LIMIT || $value <= _IV_NEG_LIMIT)) {
      33        
205 0         0 $queue->[-1] = _to_bigint($queue->[-1]);
206             }
207              
208 20         18 push @$queue, $value;
209 20         18 my $count = --$self->{'count'};
210             ### count down to: $count
211              
212 20 100 100     41 if ($count > 0 && $self->{'side_len'} >= 2) {
    100          
213 4         5 shift @$queue;
214             } elsif ($count < 0) {
215             ### end of side, next side ...
216 6 100       11 if (--$self->{'side'} <= 0) {
217             ### end of sides, next loop ...
218 2         3 $self->{'side'} = $self->{'num_sides'};
219 2         2 $self->{'side_len'}++;
220             }
221 6         6 $self->{'count'} = $self->{'side_len'};
222             } else {
223             ### count==0 corner ...
224             }
225 20         21 return ($i, $value);
226             }
227              
228             # sub new {
229             # ### SpiroFibonacci new(): @_
230             # my $self = shift->SUPER::new(@_);
231             # require Math::PlanePath::SquareSpiral;
232             # $self->{'path'} = Math::PlanePath::SquareSpiral->new;
233             # $self->{'cache'} = [];
234             # $self->{'cache'}->[1] = $self->{'initial_0'};
235             # $self->{'cache'}->[2] = $self->{'initial_1'};
236             # return $self;
237             # }
238             #
239             # sub ith {
240             # my ($self, $i) = @_;
241             # ### SpiroFibonacci ith(): $i
242             #
243             # if (_is_infinite($i)) {
244             # return undef;
245             # }
246             #
247             # if ($i <= 0) {
248             # return undef;
249             # }
250             # my $orig_i = $i;
251             #
252             # my $cache = $self->{'cache'};
253             # my $path = $self->{'path'};
254             # my @pending = ($i);
255             # my $total = 0;
256             #
257             # while (@pending) {
258             # ### @pending
259             # $i = pop @pending;
260             # if (defined $cache->[$i]) {
261             # if ($self->{'recurrence_type'} eq 'absdiff') {
262             # $total ^= $cache->[$i];
263             # } else {
264             # $total += $cache->[$i];
265             # }
266             # } else {
267             # my ($x,$y) = $path->n_to_xy($i);
268             # my $pi = 0;
269             # foreach my $dxdy ([0,1],[0,-1],
270             # [1,0],[-1,0]) {
271             # my ($dx,$dy) = @$dxdy;
272             # my $n = $path->xy_to_n($x+$dx,$y+$dy);
273             # if ($n < $i-1 && $n > $pi) {
274             # ### straight at: "i=$i,x=$x,y=$y dx=$dx dy=$dy pi=$n"
275             # $pi = $n;
276             # }
277             # }
278             # if (! $pi) {
279             # foreach my $dxdy ([1,1],[1,-1],
280             # [-1,1],[-1,-1]) {
281             # my ($dx,$dy) = @$dxdy;
282             # my $n = $path->xy_to_n($x+$dx,$y+$dy);
283             # if ($n < $i-1 && $n > $pi) {
284             # ### diagonal at: "i=$i,x=$x,y=$y dx=$dx dy=$dy pi=$n"
285             # $pi = $n;
286             # }
287             # }
288             # }
289             # if (@pending > 100000) { die; }
290             # push @pending, $pi;
291             # push @pending, $i-1;
292             # }
293             # }
294             # $self->{'cache'}->[$orig_i] = $total;
295             #
296             # ### $total
297             # return $total;
298             # }
299              
300             1;
301             __END__