# Local Dyadic Square Class Benchmarks

This folder contains a set of benchmark scripts for timing computations of local dyadic square classes using **Magma**, **SageMath**, and **Pari/GP**.

---

## Important

> Before running any scripts, ensure that the variable `PATH_TO_LSC` in the file `path.[m|sage]` correctly points to the package `local_square_classes.[m|sage]`.

---

## Tests

Benchmark scripts are named `benchmark_XYZ.[m|sage|gp]`, where `XYZ` is one of:

* `totally_ramified`
* `totally_ramified_big`
* `unramified`

### Test Descriptions

For **Magma** and **SageMath** (except `benchmark_totally_ramified_big.m`), the following operations are timed:

1. **Construction of a basis** for the group of local dyadic square classes, treated as a vector space over the binary field.
2. **Generation of random representatives** of uniformly distributed local dyadic square classes.
3. **Coordinate computation** of a random nonzero algebraic number with respect to the basis constructed in test 1.

**Pari/GP** scripts and the Magma script `benchmark_totally_ramified_big.m` perform only test 1.

To ensure reliable measurements:

* The number of random samples in tests 2 and 3, and the number of repetitions of test 1, are dynamically adjusted.
* Since results of test 1 are prone to caching effects (and Magma is very good at caching), an additional consistency check is performed: the computation is repeated 8 times and the results are compared.  We allow for a deviation of no more than 30%.

### Benchmark Categories

* `benchmark_unramified.[m|sage|gp]`:

  * Tests are run for the unique unramified extensions of \$\mathbb{Q}\_2\$ for degrees 2 through 50. The main limitation is the time required by Magma to construct the unique dyadic place in the base number field. (Which, by the way, must be the principal ideal generated by 2.) 

* `benchmark_totally_ramified.[m|sage|gp]`:

  * Tests use fields defined by generating polynomials of the form \$(x - 1)^d + 2\$, where \$d\$ ranges from 2 to 100. Such fields are known to have unique totally ramified dyadic places. 

* `benchmark_totally_ramified_big.[m|gp]`:

  * Uses the same family of polynomials with degrees \$d = 2^k\$, for \$k = 7\$ to \$11\$.

---

## Output

Scripts for **Magma** and **SageMath** (with `.m` and `.sage` extensions, respectively) write their output to files named `XYZ_[magma|sage]_YYYY-MM-DD.dat`. **Pari/GP** scripts print timings directly to the console.

### Output Format

The `.dat` files outputted by the Magma scripts `benchmark_totally_ramified.m` and `benchmark_unramified.m` consists of the following columns:

* `deg`: Degree of the field extension.
* `t1`: Average time for constructing the group using Magma’s built-in method `LocalMultiplicativeGroupModSquares`.
* `N1`: One-eighth of the number of repetitions used to compute `t1`.
* `u1`: Average time using our implementation (`LocalGroupOfSquaresClasses`).
* `M1`: One-eighth of the repetitions used to compute `u1`.
* `t2`, `u2`: Average times to construct a representative of a random local square class using Magma’s built-in method (`t2`) and our method (`u2`).
* `N2`: Number of random classes used to compute `t2` and `u2`.
* `t3`, `u3`: Average times to compute coordinates in the local dyadic square class group using Magma’s built-in method (`t3`) and our method (`u3`).
* `N3`: Number of random elements used to compute `t3` and `u3`.

The `.dat` file produced by `benchmark_totally_ramified_big.m` contains only the columns: 

* `deg`, `t1`, `N1`, `u1`, `M1`

SageMath does not offer a built-in function to construct groups of local square-classes, Hence, the `.dat` files produced by Sage scripts contains only the columns 

* `deg`, `u1`, `M1`, `u2`, `N2`, `u3`, `N3`


