Hacker News Reader

Comment by pansa2 | Hacker News Reader

I did the same thing, recalling "There are Only Four Billion Floats–So Test Them All!" [0]. Except I used Python, so it took over 10 minutes:

    >>> import struct
    >>> count = 0
    >>> for i in range(0x1_0000_0000):
    ...     f = struct.unpack('<f', struct.pack('<I', i))[0]
    ...     if 0 <= f <= 1: count += 1
    ...
    >>> count
    1065353218

[0] https://randomascii.wordpress.com/2014/01/27/theres-only-fou...

View on HN

My very-slightly-different Python implementation runs in 9m56s minutes on Python 3.11, but in 2m54s using pypy3.9 (all on an M1 Max)

pypy never ceases to amaze me for low-effort performance gains on computational stuff.

A naive implementation in C compiled with Apple's clang (-O2) takes 0.62 seconds, of course.

This should be a bit faster, while still sticking to stock Python:

  import time, array

  n = 0
  start_time = time.time()
  values = bytearray(b"".join(i.to_bytes(4, "big") for i in range(2**24)))
  for prefix in range(256):
      values[::4] = prefix.to_bytes(1, "big") * (2**24)
      arr = array.array("f", values)
      n += sum(1 for x in arr if 0.0 <= x <= 1.0)

  print(f"Found: {n} Time: {time.time() - start_time:.1f} seconds")

It uses an array.array() to convert from a large number of concatenated 4 bytes to floats, rather than going through the struct module one-by-one.

Rather than build all 0x1_0000_0000 values in memory, I process 0x100_0000 at a time, and accumulate the partial sums.

On my laptop this reports "Found: 1065353218 Time: 228.5 seconds", so just under 4 minutes.

A slightly improved algorithm in NumPy takes 5.4 seconds.

    import time, numpy as np

    start_time = time.time()
    arr = np.arange(2**24, dtype=np.uint32)
    incr = np.full(2**24, 2**24, dtype=arr.dtype)

    values = np.frombuffer(arr, np.float32)
    n = ((0.0 < values) & (values <= 1.0)).sum()
    for i in range(1, 256):
        arr += incr
        n += ((0.0 < values) & (values <= 1.0)).sum()

    print(f"Found: {n} Time: {time.time() - start_time:.1f} seconds")

Reply on news.ycombinator.com