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 = builder.add_committed(
59		format!("{} exp_result", name),
60		log_rows,
61		BinaryField64b::TOWER_LEVEL,
62	);
63
64	let g_lookup_table = if let Some(id) = g_lookup_table {
65		id
66	} else {
67		build_exp_table(g, builder, format!("{} g_lookup_table", name))?
68	};
69
70	let lookup_values = builder.add_linear_combination(
71		format!("{} lookup_values", name),
72		log_rows,
73		[
74			(xin, <F as TowerField>::basis(4, 4)?),
75			(exp_result, <F as TowerField>::basis(6, 0)?),
76		],
77	)?;
78
79	let multiplicities = if let Some(witness) = builder.witness() {
80		let xin = witness.get::<BinaryField16b>(xin)?.as_slice::<u16>();
81
82		let mut exp_result = witness.new_column::<BinaryField64b>(exp_result);
83
84		let exp_result = exp_result.as_mut_slice::<BinaryField64b>();
85
86		exp_result.par_iter_mut().enumerate().for_each(|(i, exp)| {
87			*exp = g.pow(xin[i] as u64);
88		});
89
90		let mut lookup_values = witness.new_column::<BinaryField128b>(lookup_values);
91
92		let lookup_values = lookup_values.as_mut_slice::<u128>();
93
94		lookup_values
95			.iter_mut()
96			.enumerate()
97			.for_each(|(i, look_val)| {
98				let exp_result_u64: u64 = exp_result[i].into();
99				*look_val = ((xin[i] as u128) << 64) | exp_result_u64 as u128;
100			});
101
102		let mut multiplicities = vec![0usize; 1 << 16];
103		for &i in xin {
104			multiplicities[i as usize] += 1;
105		}
106
107		Some(multiplicities)
108	} else {
109		None
110	};
111
112	plain_lookup::plain_lookup::<BinaryField128b, LOG_MAX_MULTIPLICITY>(
113		builder,
114		"u16_exp_lookup",
115		&[1 << log_rows],
116		&[[lookup_values]],
117		[g_lookup_table],
118		multiplicities,
119	)?;
120
121	Ok((exp_result, g_lookup_table))
122}
binius_circuits/arithmetic/static_exp.rs

binius_circuits/arithmetic/
static_exp.rs
