Beefy Boxes and Bandwidth Generously Provided by pair Networks
Do you know where your variables are?
 
PerlMonks  

comment on

( #3333=superdoc: print w/replies, xml ) Need Help??

Let me guess about the next optimizations you have made after this?

Firstly, bitwise xor is associative, so there's no point in computing the ^ HASH_LEN in the innermost loop, you can put that to m8..i8 instead of m9..i9. Eg.

m8 = (m7 ^ q8) * H_PRIME ^ HASH_LEN; m9 = m8 ^ q9;
Though the compiler might already be smart enough to notice this, so it might not have any effect.

Secondly, I wouldn't bother computing c8..i8 unless m9 is correct.

Thirdly, there is no point looping over q9. Instead, notice that as q9 takes all possible values from 0..127, m9 will take the values from (m8&~127)..(m8&~127)+127 in a different order. Among those 127 possible values of m9, there can only be one that has the right value modulo 1001. You can compute that value directly, and try the corresponding single value for q9, checking if it lies in the range.

However, I wonder, does the magic formula really have to use exactly 1001 as the modulus? I think it could use any modulus between 1001 and 9999.

To search for the magic formula in that case, first compute t = gcd(m9 - 1000, d9 - 500) (be careful with underflows). Then compute the small prime factors of t, and using this, all divisors of t between 1001 and 9999, and check all those divisors as the modulus against the rest of the numbers. In the rare lucky case that t is 0, you will have to try all moduluses (or all divisors of c9 - 100).

Most of the time, t should be between 1 and 1000, in case you don't have to compute a factorization because no modulus can work. Because of this, you should probably not bother to compute c9..i9 and c8..i8 unless t is greater than 1000 or zero.

This would certainly be more difficult to implement, and might take more time for each individual magic string, but it also has a higher chance of finding a formula, so it might be worth.

Update: fixed a typo from (m8&!127)+127 to (m8&~127)+127 that eyepopslikeamosquito noticed.


In reply to Re: The 10**21 Problem (Part I) by ambrus
in thread The 10**21 Problem (Part I) by eyepopslikeamosquito

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others exploiting the Monastery: (8)
    As of 2019-11-19 11:15 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?
      Strict and warnings: which comes first?



      Results (95 votes). Check out past polls.

      Notices?