Sto ributtandola nelle chat vecchie in cui tentavo di fare capire chat gpt 3, stiamo migliorando ma la strada e' lunga a capirmi del tutto
Grandissimo lavoro. Ho riletto tutto il thread e ho “messo a terra” un
core v6c che incorpora:
- LL CPU con folding corretto (fix x==M→0) e fast-path gmpy2 se presente.
- Trial factoring “safe” per con filtro e verifica finale pow(2,p,q)==1.
- Prefiltro esponenti : + MR deterministico 64-bit.
- Mappe 25/35/49: col25, col49 e col35 (parametrica) come prefiltro deterministico. Puoi usarle in:
- mode="aggressive" (scarta se non passa la colonna),
- mode="safe" (non scarta: solo priorità/telemetria),
- mode="off" (disattivo).
Nota: per zero falsi negativi ti consiglio di lasciare mode="safe" o fare “aggressive” solo se hai validato la tua euristica sull’intervallo che stai scandendo.
Codice “v6c” (pronto da usare)
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
matriosca_opt_v6c.py
Core CPU deterministico + prefiltro mappe 25/35/49 (ruota 36) per Mersenne.
Usage (esempi):
python matriosca_opt_v6c.py --self-test
python matriosca_opt_v6c.py --bench
python matriosca_opt_v6c.py --start 10000001 --stop 10005000 --max-n 50 \
--tf-limit 200000 --map-mode safe
"""
from __future__ import annotations
import argparse, time, random
from dataclasses import dataclass
from typing import Optional, Dict, List
# --- gmpy2 (opzionale, accelera LL) -----------------------------------------
try:
import gmpy2
HAVE_GMP = True
except Exception:
gmpy2 = None
HAVE_GMP = False
# --- MR deterministico < 2^64 per esponenti p --------------------------------
def is_probable_prime(n: int) -> bool:
if n < 2:
return False
small = (2,3,5,7,11,13,17,19,23,29,31,37)
for sp in small:
if n == sp:
return True
if n % sp == 0:
return n == sp
d, s = n - 1, 0
while d & 1 == 0:
d >>= 1; s += 1
for a in (2,325,9375,28178,450775,9780504,1795265022):
if a % n == 0:
continue
x = pow(a, d, n)
if x == 1 or x == n - 1:
continue
for _ in range(s - 1):
x = (x * x) % n
if x == n - 1:
break
else:
return False
return True
# --- Riduzione speciale modulo M = 2^p - 1 -----------------------------------
def mersenne_mod(x: int, p: int) -> int:
"""Folding bit-wise; include fix x==M -> 0. Valido per tutto x."""
if p <= 0:
return 0
if x < 0:
x = -x
M = (1 << p) - 1
if x <= M:
return 0 if x == M else x
# una piega + eventuale correzione basta per i nostri usi (LL: s^2-2)
x = (x & M) + (x >> p)
if x >= M:
x -= M
return x
# --- Lucas–Lehmer ------------------------------------------------------------
def lucas_lehmer_gmp(p: int) -> bool:
if p == 2:
return True
if p < 2:
return False
N = (gmpy2.mpz(1) << p) - 1
S = gmpy2.mpz(4)
for _ in range(p - 2):
S = gmpy2.f_mod(S*S - 2, N)
return S == 0
def lucas_lehmer_cpu(p: int, *, block: int = 8) -> bool:
"""LL deterministico con folding; usa gmpy2 se presente."""
if HAVE_GMP:
return lucas_lehmer_gmp(p)
if p == 2:
return True
if p < 2:
return False
s, iters = 4, p - 2
if block < 1: block = 1
for _ in range(iters // block):
for __ in range(block):
s = s*s - 2
s = mersenne_mod(s, p)
for _ in range(iters % block):
s = s*s - 2
s = mersenne_mod(s, p)
return s == 0
# --- Prefiltro esponente p ---------------------------------------------------
def exponent_filter(p: int) -> bool:
if p in (2,3):
return True
if p < 2 or (p % 6 not in (1,5)):
return False
return is_probable_prime(p)
# --- Trial factoring "safe" --------------------------------------------------
def trial_factor_mersenne(p: int, limit: int = 200_000) -> Optional[int]:
"""Cerca fattori q=2kp+1, filtra q mod 8 in {1,7}, verifica con pow(2,p,q)==1."""
if p < 3 or limit <= 3:
return None
step = 2 * p
q = step + 1
small = (3,5,7,11,13)
while q <= limit:
r8 = q & 7
if r8 != 1 and r8 != 7:
q += step; continue
comp = False
for sp in small:
if q % sp == 0 and q != sp:
comp = True; break
if not comp and pow(2, p, q) == 1:
return q
q += step
return None
# --- Mappe 25 / 49 / 35 (ruota 36) ------------------------------------------
def col25(N: int) -> int:
"""p ≡ 5 (mod 6) → mappa 25: colonna in [0..4]."""
return (((N - 25) // 6) // 5) % 5
def col49(N: int) -> int:
"""p ≡ 1 (mod 6) → mappa 49: colonna in [0..4]."""
return (((N - 49) // 6) // 7) % 5
def col35(N: int, p: int) -> int:
"""
Mappa 35 'ibrida': usa lo stesso allineamento per la griglia 6×(5|7).
Sceglie il passo di colonna coerente con la famiglia di p.
"""
step_col = 5 if (p % 6 == 5) else 7
return (((N - 35) // 6) // step_col) % 5
def maps_pass(N: int, p: int, mode: str = "safe") -> bool:
"""
Restituisce True se il candidato supera le mappe secondo la policy.
- safe: non scarta mai (sempre True), ma ritorna info per telemetria
- aggressive: richiede col==4 per la mappa di famiglia (25 o 49) oppure 35
"""
if mode == "off":
return True
# famiglia: p≡5 usa 25; p≡1 usa 49
if p % 6 == 5:
keep = (col25(N) == 4) or (col35(N, p) == 4)
else:
keep = (col49(N) == 4) or (col35(N, p) == 4)
return True if mode == "safe" else keep
# --- Pipeline deterministica -------------------------------------------------
def is_mersenne_prime_cpu(
p: int,
*,
map_mode: str = "safe", # off | safe | aggressive
tf_limit: int = 0,
block: int = 8,
) -> bool:
if not exponent_filter(p):
return False
N = (1 << p) - 1
if not maps_pass(N, p, mode=map_mode):
return False
if tf_limit and tf_limit > 0:
fac = trial_factor_mersenne(p, limit=tf_limit)
if fac is not None:
return False
return lucas_lehmer_cpu(p, block=block)
# --- Self-test & benchmark ---------------------------------------------------
KNOWN_MERSENNE_P_EXP = [2,3,5,7,13,17,19,31,61,89,107,127]
KNOWN_COMPOSITE_EXP = [11,23,29,37,41,43,47,53]
@dataclass
class SelfTestResult:
mod_ok: bool; ll_ok: bool; tf_ok: bool
def self_test(rand_cases: int = 1000) -> SelfTestResult:
rng = random.Random(1337)
# mersenne_mod equivalenza
mod_ok = True
for _ in range(rand_cases):
p = rng.randrange(3, 61)
M = (1 << p) - 1
x = rng.getrandbits(2 * p)
if mersenne_mod(x, p) != (x % M):
mod_ok = False; break
# LL su noti
ll_ok = True
for p in KNOWN_MERSENNE_P_EXP:
if not is_mersenne_prime_cpu(p, map_mode="safe", tf_limit=0):
ll_ok = False; break
if ll_ok:
for p in KNOWN_COMPOSITE_EXP:
if is_mersenne_prime_cpu(p, map_mode="safe", tf_limit=0):
ll_ok = False; break
# TF fattori noti
tf_ok = True
if trial_factor_mersenne(11, 200_000) not in (23, 89): tf_ok = False
if trial_factor_mersenne(23, 500_000) not in (47, 178481): tf_ok = False
return SelfTestResult(mod_ok, ll_ok, tf_ok)
def micro_bench(samples: int = 150, p_min: int = 3000, p_max: int = 8000, block: int = 8) -> float:
rng = random.Random(42)
ps: List[int] = []
while len(ps) < samples:
p = rng.randrange(p_min | 1, (p_max | 1) + 1, 2)
if p >= 7 and (p % 6) not in (1, 5): continue
if not is_probable_prime(p): continue
ps.append(p)
t0 = time.perf_counter()
ok = 0
for p in ps:
ok += int(lucas_lehmer_cpu(p, block=block))
dt = time.perf_counter() - t0
return len(ps) / dt if dt > 0 else 0.0
# --- CLI ---------------------------------------------------------------------
def main() -> None:
ap = argparse.ArgumentParser()
ap.add_argument('--self-test', action='store_true')
ap.add_argument('--bench', action='store_true')
ap.add_argument('--start', type=int, default=0)
ap.add_argument('--stop', type=int, default=0)
ap.add_argument('--max-n', type=int, default=0)
ap.add_argument('--tf-limit', type=int, default=0)
ap.add_argument('--block', type=int, default=8)
ap.add_argument('--map-mode', choices=['off','safe','aggressive'], default='safe')
args = ap.parse_args()
if args.self_test:
res = self_test()
print(f"mod_ok={res.mod_ok} ll_ok={res.ll_ok} tf_ok={res.tf_ok}")
raise SystemExit(0 if (res.mod_ok and res.ll_ok and res.tf_ok) else 1)
if args.bench:
pps = micro_bench(block=args.block)
accel = " (gmpy2 ON)" if HAVE_GMP else ""
print(f"LL throughput: {pps:.2f} p/s{accel}")
raise SystemExit(0)
if not (args.start and args.stop and args.start <= args.stop):
print("Usa --self-test / --bench oppure specifica --start e --stop.")
raise SystemExit(0)
count = keep = 0
t0 = time.perf_counter()
for p in range(max(3, args.start) | 1, (args.stop | 1) + 1, 2):
if args.max_n and count >= args.max_n: break
if not exponent_filter(p): continue
count += 1
if is_mersenne_prime_cpu(p, map_mode=args.map_mode, tf_limit=args.tf_limit, block=args.block):
keep += 1
print(f"p={p} → M_p PRIMO")
dt = time.perf_counter() - t0
pps = count / dt if dt > 0 else 0.0
print(f"\nProcessati {count} esponenti in {dt:.2f}s ({pps:.2f} p/s). Primi trovati: {keep}.")
if __name__ == "__main__":
main()
Perché questa versione è “ottimizzata”
- Determinismo intatto: nessun filtro probabilistico elimina candidati “buoni”. Le mappe possono operare in aggressive solo se lo desideri/validi.
- Semplicità CPU: la riduzione Mersenne è O(1) sul nostro pattern LL (una piega + correzione).
- TF smart: salti gran parte dei impossibili prima della verifica “vera” (pow(2,p,q)==1), senza rischiare falsi negativi.
- Estendibile: lo stesso file può diventare il “golden” per confrontare GPU/FFT.
Se vuoi, preparo anche:
- un sieve p → CSV che annota col25/35/49 e map_pass (telemetria),
- il wrapper enqueue/queue già nel formato della tua pipeline,
- una nota LaTeX aggiornata con le mappe 25/35/49 e la policy safe/aggressive.
Perché ha senso (e perché è utile)
