in reply to Re^7: checking a set of numbers for consistency mod p (update: still buggy)
in thread checking a set of numbers for consistency mod p

If I read it correctly, you currently make a sieve of length 2 * range, centred around pmax. I think you need the length to be around 2 * (range + pmax - 1).

I don't understand the logic you're using with $max_pos to decide where in the sieve to match, and I'm not sure it's correct. But I'd be tempted to punt on that - make both sieve and input into strings as below, and use a regexp match.

  use List::Util qw{min};
  my @order = '0' .. '9', 'A' .. 'Z'; # range of 2^36 is probably enou
+gh

  sub to_string {
    my($max, $list) = @_;
    return join '', map {
      defined($_) ? $order[min($_, $max)] : '.'
    } @$list;
  }

[download]
  • Comment on Re^8: checking a set of numbers for consistency mod p (update: still buggy)
  • Download Code

Replies are listed 'Best First'.
Re^9: checking a set of numbers for consistency mod p
by LanX (Saint) on Apr 12, 2022 at 12:24 UTC
    first of all, the algorithm as it is now is only reliable if a hole doesn't hide a max. Otherwise you get false negatives like demonstrated here

    You will need to cover that!

    I have some efficient ideas, but no time right now.

    ( These kind of riddles cost me a lot of processing power I need elsewhere. :)

    > make a sieve of length 2 * range

    that's sufficient because range can always fit in that sliding window.

    I shift the window to the right by pmax_known+n if positioning the first max means a negative sieve index.

    It's important to realize that this can only happen with preceding holes covering a former max. Hence these holes will also ignore the position pmax+n in the sieve. °

    > make both sieve and input into strings as below, and use a regexp match.

    Not sure I understand, but the fastest way to compare two byte arrays is to xor the strings, a range of 256 or even 128 exponents should be sufficient

    Of course representation of holes, like \xFF or \x00 makes this more challenging, needing a second and

    But I consider this premature optimization, you should first test the validity of the algorithm with arrays.

    Cheers Rolf
    (addicted to the Perl Programming Language :)
    Wikisyntax for the Monastery

    °) Maybe it's even not necessary to try successive n and you can just shift by pmax - this equals swapping the sequence to the second half.

    update

    ... to come...

    ... OK ... It's important to understand that those shifts and other problems are only due to one or more holes covering an e >= max ...

    Without holes the algorithm works as is!

    Now one needs to list the possible cases, for e=max and e >max and shift accordingly by + pe for all "dubious" holes till one has a pass or all failed.

    There might be a simple solution like moving the first hole to pmax+1 and taking advantage of the fact that further collisions are not possible because of the constraints (first max) but I can't wrap my head around it.

[reply]
[d/l]
[select]

      > > make both sieve and input into strings as below, and use a regexp match.

      > Not sure I understand, but the fastest way to compare two byte arrays is to xor the strings, a range of 256 or even 128 exponents should be sufficient

      We don't have two byte arrays, we have one array with possible holes and one without. And as I mentioned just before the quote you show: I'm not yet convinced of the correctness of your approach to picking the point in the sieve to compare against. Using a regexp removes the need to know what the starting point should be, has '.' as a handy mechanism for matching the holes, and won't go wrong if a hole happens to match something maximal.

      So I'm suggesting that for the (3, [1, 0, 0, undef, 0, 0, 1]) example, a solution that ends with return +("010010020010010" =~ /100.001/) ? 1 : 0 would be a good efficient approach as long as the prep to make the string (once) and the pattern (each call) is fast enough. I'd need to sit down with pen and paper to work out exactly what length of string is required for a given (p, range): I'm not confident I know right now what it should actually be.

[reply]
[d/l]
[select]
        ah now I understand what you meant with regex ...

        ...well if it's fast enough for your needs, go for it. :)

        Cheers Rolf
        (addicted to the Perl Programming Language :)
        Wikisyntax for the Monastery

[reply]

In Section Seekers of Perl Wisdom