Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
PerlMonks  

Re^2: The 10**21 Problem (Part 4)

by eyepopslikeamosquito (Canon)
on May 19, 2014 at 22:04 UTC ( #1086720=note: print w/ replies, xml ) Need Help??


in reply to Re: The 10**21 Problem (Part 4)
in thread The 10**21 Problem (Part 4)

Luckily, it was accepted by both shinh's golf server, when I submitted it about a month ago, and the code golf server also (currently down). Shinh's server runs Python 2.7.2 on Linux, the code golf server Python 2.5 on Linux.

It would be interesting to see the actual hash value and Python version by running this version:

import sys print sys.version_info magic = chr(17)+chr(11)+chr(119)+chr(60)+chr(47)+chr(44)+chr(78)+chr(1 +03)+chr(125)+chr(48) for r in ["M", "D", "C", "L", "X", "V", "I"]: h = hash(r + magic) n = h % 1001 print r, n, "(" + str(h) + ")"
which produced for me on Windows just now:
sys.version_info(major=2, minor=7, micro=5, releaselevel='final', seri +al=0) M 1000 (2094745652) D 500 (1641493353) C 100 (277891714) L 50 (1566900385) X 10 (1666291637) V 5 (-1570643069) I 1 (1060402344)
Strange, that this is the same Python version 2.7.5 as reported by mr_mischief but on a different platform (Windows vs MacOS). I tested both 32-bit and 64-bit Python on Windows (multiple versions) and didn't see a failure.

On shinh's golf server it produced:

sys.version_info(major=2, minor=7, micro=2, releaselevel='final', seri +al=0)\n M 1000 (2094745652) D 500 (1641493353) C 100 (277891714) L 50 (1566900385) X 10 (1666291637) V 5 (-1570643069) I 1 (1060402344)
This is doubly strange because that is the same Python version 2.7.2 running on the same platform, Linux, which failed for RMGir!

I will check the Python C sources version history later when I get more time.


Comment on Re^2: The 10**21 Problem (Part 4)
Select or Download Code
Re^3: The 10**21 Problem (Part 4)
by RMGir (Prior) on May 19, 2014 at 23:19 UTC
    Very strange.

    I even checked to make sure bitness had no impact by running both the 32 and 64-bit versions of the python on my mac, but both give the same result.

    I was doing that wrong. Running a 32-bit version of python (by following these directions) on my mac, I get the answer you expect.

    So I suspect it's just that the python hash function works for your approach in 32-bit builds, but not in 64.


    Mike

      Yes, I believe you are correct.

      From stringobject.c:

      static long string_hash(PyStringObject *a) { register Py_ssize_t len; register unsigned char *p; register long x; if (a->ob_shash != -1) return a->ob_shash; len = Py_SIZE(a); p = (unsigned char *) a->ob_sval; x = *p << 7; while (--len >= 0) x = (1000003*x) ^ *p++; x ^= Py_SIZE(a); if (x == -1) x = -2; a->ob_shash = x; return x; }
      we can see that it is not whether the platform itself is 64-bit that matters, but whether the long type used by the C compiler that Python was built with is 64-bit. For Python built with a 32-bit long my solution should work, for a 64-bit long it will not.

      On 64-bit architectures, Windows C compilers tend to use the LLP64 programming model (32-bit long), while most others tend to use the LP64 model (64-bit long). From this stack overflow question:

      The true "war" was for sizeof(long), where Microsoft decided for sizeof(long) == 4 (LLP64) while nearly everyone else decided for sizeof(long) == 8 (LP64). Note that a programming model is a choice made on a per-compiler basis, and several can coexist on the same OS. However, the programming model chosen as the primary model for the OS API typically dominates.

      Hmmm, I see from this later stringobject.c that _Py_HashSecret_* has been added, presumably to protect against DoS attacks that exploit hash collisions in Python dictionaries.

      static long string_hash(PyStringObject *a) { register Py_ssize_t len; register unsigned char *p; register long x; #ifdef Py_DEBUG assert(_Py_HashSecret_Initialized); #endif if (a->ob_shash != -1) return a->ob_shash; len = Py_SIZE(a); /* We make the hash of the empty string be 0, rather than using (prefix ^ suffix), since this slightly obfuscates the hash secre +t */ if (len == 0) { a->ob_shash = 0; return 0; } p = (unsigned char *) a->ob_sval; x = _Py_HashSecret.prefix; x ^= *p << 7; while (--len >= 0) x = (1000003*x) ^ *p++; x ^= Py_SIZE(a); x ^= _Py_HashSecret.suffix; if (x == -1) x = -2; a->ob_shash = x; return x; }

      See also:

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1086720]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (5)
As of 2014-12-20 11:54 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (95 votes), past polls