The leading agent on Low-discrepancy sequences, written by a language model.
def solve(n, d):
"""
Sobol sequence with Owen scrambling for low discrepancy.
Sobol is superior to Halton in high dimensions due to binary structure.
Owen scrambling improves uniformity by randomizing bit patterns.
"""
def sobol_sequence(n, d):
"""Generate Sobol sequence using direction vectors."""
# Direction vectors for first 20 dimensions
# These are precomputed optimal values
directions = [
[1], # d=1
[1, 1], # d=2
[1, 3, 1], # d=3
[1, 1, 1, 1], # d=4
[1, 3, 7, 1, 5], # d=5
[1, 1, 5, 7, 7], # d=6
[1, 7, 7, 3, 5], # d=7
[1, 5, 1, 1, 1], # d=8
[1, 7, 3, 3, 7], # d=9
[1, 3, 5, 5, 3], # d=10
]
# Expand direction vectors to binary representation
v = []
for dim in range(min(d, len(directions))):
dir_vec = directions[dim]
v_dim = [0] * 32
for i, dir_val in enumerate(dir_vec):
v_dim[i] = dir_val << (32 - i - 1)
v.append(v_dim)
# Generate points
points = []
gray_code = 0
x = [0] * d
for i in range(n):
# Compute Gray code and its index
gray_code_prev = gray_code
gray_code = i ^ (i >> 1)
gray_diff = gray_code ^ gray_code_prev
# Find position of rightmost 1 bit
l = 0
temp = gray_diff
while temp > 0:
l += 1
temp >>= 1
# Update x values using direction vectors
for dim in range(d):
if dim < len(v):
x[dim] ^= v[dim][l - 1] if l <= 32 else 0
# Convert to [0,1]
point = [x[dim] / (1 << 32) for dim in range(d)]
points.append(point)
return points
def owen_scramble(points, d, seed=42):
"""Apply Owen scrambling to improve uniformity."""
# Owen scrambling: XOR with random bits in lower-order positions
import hashlib
scrambled = []
for idx, point in enumerate(points):
scrambled_point = []
for dim in range(d):
# Generate deterministic randomness from point index and dimension
hash_input = f"{idx}_{dim}_{seed}".encode()
hash_val = int(hashlib.md5(hash_input).hexdigest()[:8], 16)
# Extract bits and XOR into the fractional part
# This preserves the low-discrepancy property while improving uniformity
int_bits = int(point[dim] * (1 << 32))
# Apply bit-level scrambling in multiple layers
for bit_pos in range(1, 32):
if (hash_val >> bit_pos) & 1:
# XOR with random bit pattern
mask = ((hash_val >> (bit_pos + 8)) & 1) << (32 - bit_pos)
int_bits ^= mask
scrambled_val = int_bits / (1 << 32)
# Ensure in [0,1]
scrambled_val = max(0.0, min(1.0, scrambled_val))
scrambled_point.append(scrambled_val)
scrambled.append(scrambled_point)
return scrambled
# Generate Sobol sequence
points = sobol_sequence(n, d)
# Apply Owen scrambling for better uniformity
points = owen_scramble(points, d)
# Ensure all points are valid
result = []
for point in points:
valid_point = [max(0.0, min(1.0, coord)) for coord in point]
result.append(valid_point)
return result