view release on metacpan or  search on metacpan

lib/Math/NumSeq/GolayRudinShapiroCumulative.pm  view on Meta::CPAN

For an inclusive sum GRS(0)+...+GRS(i) as per this module, the extra GRS(i)
can be worked into the calculation by its GRS definition +1 or -1 according
to the total number of adjacent 11 bits.  This can be thought of as an extra
value 1 below the least significant bit.  For example i=27 inclusive

           +1      below all bits
    1      -1      bit0 low bit
    1      -2      bit1
    0              bit2
    1      +4      bit3
    1      +4      bit4 high bit
          ----
            5      cumulative value GRS(0)+...+GRS(27)

For low to high calculation, this lowest +/-1 can be handled simply by
starting the total at 1.  It then becomes +1 or -1 by the negations as 11s
are encountered for the rest of the bit handling.

    total = 1   # initial value below all bits to be inclusive GRS(i)
    power = 1   # 2^ceil(bitpos/2)
    thisbit = take bit from low end of i

    loop
      nextbit = take bit from low end of i
      if thisbit&&nextbit
        then total = -total    # negate lower values added
      if thisbit
        then total += power
      thisbit = nextbit

      power *= 2
      exit loop if i==0

      nextbit = bit from low end of i
      if thisbit&&nextbit
        then total = -total    # negate lower values added
      if thisbit
        then total += power
      thisbit = nextbit
      exit loop if i==0
    endloop

    total += power     # final for highest 1-bit in i
    # total=GRS(0)+...+GRS(i)

This sort of calculation arises implicitly in the alternate paper folding
curve to calculate X,Y for a given N point on the curve.  Bits of the
cumulative GRS can be generated from base 4 digits of 2*N.  See the author's
alternate paperfolding curve write-up for some more ("GRScumul" in the
index)

=over

L<http://user42.tuxfamily.org/alternate/index.html>

=back

=cut

# ENHANCE-ME: Cross-ref to AlternatePaper formulas section when its X,Y
# calculation is described.

=pod

=head1 SEE ALSO

L<Math::NumSeq>,
L<Math::NumSeq::GolayRudinShapiro>

L<Math::PlanePath::AlternatePaper>

=head1 HOME PAGE

L<http://user42.tuxfamily.org/math-numseq/index.html>

=head1 LICENSE

Copyright 2012, 2013, 2014, 2016, 2019, 2020 Kevin Ryde

Math-NumSeq is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
version.

Math-NumSeq is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
more details.

You should have received a copy of the GNU General Public License along with
Math-NumSeq.  If not, see <http://www.gnu.org/licenses/>.

=cut