binius_circuits/arithmetic/
static_exp.rs

1// Copyright 2025 Irreducible Inc.
2
3use anyhow::Ok;
4use binius_core::oracle::OracleId;
5use binius_field::{BinaryField128b, BinaryField16b, BinaryField64b, PackedField, TowerField};
6use binius_maybe_rayon::{
7	iter::{IndexedParallelIterator, IntoParallelRefMutIterator, ParallelIterator},
8	slice::ParallelSliceMut,
9};
10
11use crate::{
12	builder::{types::F, ConstraintSystemBuilder},
13	plain_lookup,
14};
15
16pub fn build_exp_table(
17	g: BinaryField64b,
18	builder: &mut ConstraintSystemBuilder,
19	name: impl ToString,
20) -> Result<OracleId, anyhow::Error> {
21	let chunk_size = 1024;
22
23	let table = builder.add_committed(name, 16, BinaryField128b::TOWER_LEVEL);
24
25	if let Some(witness) = builder.witness() {
26		let mut table = witness.new_column::<BinaryField128b>(table);
27
28		let table = table.as_mut_slice::<u128>();
29
30		table
31			.par_chunks_mut(chunk_size)
32			.enumerate()
33			.for_each(|(i, chunk)| {
34				let offset = i * chunk_size;
35				let mut current_g = g.pow(offset as u64);
36				chunk.iter_mut().enumerate().for_each(|(i, el)| {
37					let current_g_u64: u64 = current_g.into();
38					*el = (((offset + i) as u128) << 64) | current_g_u64 as u128;
39					current_g *= g;
40				})
41			})
42	}
43
44	Ok(table)
45}
46
47pub fn u16_static_exp_lookups<const LOG_MAX_MULTIPLICITY: usize>(
48	builder: &mut ConstraintSystemBuilder,
49	name: impl ToString,
50	xin: OracleId,
51	g: BinaryField64b,
52	g_lookup_table: Option<OracleId>,
53) -> Result<(OracleId, OracleId), anyhow::Error> {
54	let log_rows = builder.log_rows([xin])?;
55
56	let name = name.to_string();
57
58	let exp_result =
59		builder.add_committed(format!("{name} exp_result"), log_rows, BinaryField64b::TOWER_LEVEL);
60
61	let g_lookup_table = if let Some(id) = g_lookup_table {
62		id
63	} else {
64		build_exp_table(g, builder, format!("{name} g_lookup_table"))?
65	};
66
67	let lookup_values = builder.add_linear_combination(
68		format!("{name} lookup_values"),
69		log_rows,
70		[
71			(xin, <F as TowerField>::basis(4, 4)?),
72			(exp_result, <F as TowerField>::basis(6, 0)?),
73		],
74	)?;
75
76	let multiplicities = if let Some(witness) = builder.witness() {
77		let xin = witness.get::<BinaryField16b>(xin)?.as_slice::<u16>();
78
79		let mut exp_result = witness.new_column::<BinaryField64b>(exp_result);
80
81		let exp_result = exp_result.as_mut_slice::<BinaryField64b>();
82
83		exp_result.par_iter_mut().enumerate().for_each(|(i, exp)| {
84			*exp = g.pow(xin[i] as u64);
85		});
86
87		let mut lookup_values = witness.new_column::<BinaryField128b>(lookup_values);
88
89		let lookup_values = lookup_values.as_mut_slice::<u128>();
90
91		lookup_values
92			.iter_mut()
93			.enumerate()
94			.for_each(|(i, look_val)| {
95				let exp_result_u64: u64 = exp_result[i].into();
96				*look_val = ((xin[i] as u128) << 64) | exp_result_u64 as u128;
97			});
98
99		let mut multiplicities = vec![0usize; 1 << 16];
100		for &i in xin {
101			multiplicities[i as usize] += 1;
102		}
103
104		Some(multiplicities)
105	} else {
106		None
107	};
108
109	plain_lookup::plain_lookup::<BinaryField128b, LOG_MAX_MULTIPLICITY>(
110		builder,
111		"u16_exp_lookup",
112		&[1 << log_rows],
113		&[[lookup_values]],
114		[g_lookup_table],
115		multiplicities,
116	)?;
117
118	Ok((exp_result, g_lookup_table))
119}
binius_circuits/arithmetic/static_exp.rs

binius_circuits/arithmetic/
static_exp.rs
