dlog
solve(p, g, h): return an integer x with pow(g, x, p) == h, 0 <= x < p - 1. Any valid x counts; return None for no answer.
What it can prove: speedups from about 1.5 to 3 bits (2.8 to 8.0 times faster) than the baseline.
Usable, but read the compiler's notes below: they say how far to trust the test.
- The test: problem sizes [28, 29, 30], 24 questions per size, time limit 120 s per question; about 3.07 CPU-hours to score one solver.
- The baseline: the author has not said what it is or what is known to beat it, so a speedup over it may be easy.
- Compiler self-test: passed. It checks that the baseline against itself scores about 0, that a solver which never answers scores 0, and that a known 1-bit speedup is recovered.
How often a real speedup of each size would be proven
| Real speedup (bits) | Proven in all three rounds | % |
|---|---|---|
| 0 | 0% | |
| 0.5 | 0% | |
| 1 | 0% | |
| 1.5 | 97% | |
| 2 | 100% | |
| 3 | 100% | |
| 4 | 60% | |
| 5 | 0% | |
| 6 | 0% |
Assumes a solver's speed varies about 0.6 bit from question to question. The real figure is unknown until someone submits.
Notes from the compiler (4)
- narrow ladder: 3 size(s) spanning 2.59 octaves of cost (3+ is needed for the estimator's three difficulty bins to be well populated): widen SIZE_RANGE or let the reference's cost grow faster
- the first plan's cost predictions missed by more than an octave, so the ladder was re-planned from the confirming data: it is the best available but NOT independently confirmed
- the cost model was still off by more than one octave at size(s) [30] after 2 refinements
- the measured median at one size is 1.3 octaves from the smoothed trend (sampling noise at 16 instances per size): the power analysis uses the smoothed trend; raise --n-prof for a steadier profile
Version dlog-v1, fingerprint 4b6669a7acc6.
Check the compiler's arithmetic yourself (it recomputes the whole table from the saved record and says if anything differs):
python3 compile_domain.py recheck dlogpython3 submit_check.py my_solver.py --family dlog