Algorithms
archec ships 21 algorithms that projects keep writing again: control loops,
filters, timing, checks and signal processing. They are in the library arche-algorithms, on the
store's algorithms shelf (archec shelf algorithms). Each one:
- is a component with its parameters (a
varwith a default, and a unit where it has one) and an interface other parts call it through; - does its work in the action language, so it runs in the simulator and is generated to C, C++, Rust, Go, Python and TypeScript;
- has its test plan (
lib/arche-algorithms/tests/), run on the simulator; - has a chart of how it responds (
response.svgbeside it, its data inresponse.json).
Using one#
Take the library, include the algorithm, add it as a part, and call it through a port that requires its interface:
project Oven {
uses arche-algorithms "^0.1"
}
include "arche-algorithms/pid/pid.arche"
component Heater {
out pid: requires PidApi
var temperature: float32 = 20
var power: float32 = 0
fn tick ```arche
power = pid.update(60.0, temperature)
```
}
system Oven {
part heater: Heater
part pid: Pid
heater.pid -> pid.api
}archec shelf add main.arche Pid writes the uses, the include and the part.
include "arche-algorithms/algorithms.arche" takes all of them.
To change a parameter, extend the algorithm and give it another default:
component OvenPid extends Pid {
var kp: float32 = 2.0
var ki: float32 = 0.5
var out_min: float32 = 0.0
}archec suggest main.arche finds hand-written code that one of them already does
(see the commands).
The algorithms#
Each entry gives the component, its interface and what is called.
PID controller — Pid, PidApi. Pushes a measurement towards a target. Its
output stays between out_min and out_max, and the integral stops growing at a
limit (anti-windup). Parameters kp, ki, kd, dt.
command = pid.update(target, measured), pid.reset().
On/off with hysteresis — Thermostat, ThermostatApi. On below
setpoint - hysteresis/2, off above setpoint + hysteresis/2; heating false
cools instead. heater_on = thermostat.update(temperature).
Ramp (slew-rate limit) — Ramp, RampApi. The output follows the target at
rate per second at most. speed = ramp.update(wanted), ramp.reset(0.0).
Moving average — MovingAverage, MovingAverageApi. The mean of the last
window samples (up to 32). smooth = average.update(raw).
Low-pass filter — LowPass, LowPassApi. First order: changes slower than
cutoff (Hz) pass. level = filter.update(raw).
Median filter — Median, MedianApi. The middle of the last window
samples (3 to 9): a single spike never comes out. range = median.update(echo).
Debounce — Debounce, DebounceApi. The output changes once the input has
stayed changed for settle (10 ms), called every period.
pressed = button.update(contact).
Complementary filter — ComplementaryFilter, ComplementaryFilterApi. A tilt
angle from a gyro (smooth, drifts) and an accelerometer (noisy, does not drift).
pitch = tilt.update(gyro_rate, accel_x, accel_z).
Kalman filter, one value — Kalman1D, Kalman1DApi. The best estimate of a
slowly changing value; q is how much it drifts, r how noisy a measurement is.
level = kalman.update(measured).
2-point calibration — Calibration, CalibrationApi. A straight line through
two known points. cal.set_low(410.0, 0.0), cal.set_high(3720.0, 100.0),
celsius = cal.apply(raw).
Lookup table — LookupTable, LookupTableApi. A curve of up to 16 points,
straight lines between them. curve.set_point(0, 0.5, 100.0),
celsius = curve.lookup(volts).
Differential-drive odometry — Odometry, OdometryApi. Where a robot on two
wheels is, from the angle each wheel turned since the last call.
odo.update(left_rad, right_rad), odo.get_x(), odo.get_y(),
odo.get_heading().
Waypoint follower — WaypointFollower, WaypointFollowerApi. Steers to each
point of a route in turn (up to 16), slower in turns, and stops at the last.
route.add(1.0, 0.0), done = route.update(x, y, heading), route.get_speed(),
route.get_turn().
Trapezoidal motion profile — MotionProfile, MotionProfileApi. Speeds up at
max_accel, cruises at max_speed, slows down to stop on the target.
setpoint = profile.update(goal).
Watchdog — Watchdog, WatchdogApi. Says when it was not fed for longer
than timeout. alive.feed(), lost = alive.expired(). (A part's own
watchdog member runs its on-timeout by itself; this one is asked.)
Retry with backoff — RetryBackoff, RetryBackoffApi. After each failure a
wait twice the last, from first_delay up to max_delay; it gives up after
max_tries. wait retry.failed(), retry.succeeded(), retry.gave_up().
2-out-of-3 vote — Vote2oo3, VoteApi. Keeps the middle of three readings,
so one failed sensor changes nothing; odd_one says which is off.
altitude = vote.vote(a, b, c), vote.agreed().
CRC-8, CRC-16, CRC-32 — Crc8 (SMBus), Crc16 (CCITT-FALSE), Crc32 (IEEE),
Crc8Api, Crc16Api, Crc32Api. crc.reset(), crc.add(b) for each byte,
crc.value(). "123456789" gives 0xF4, 0x29B1 and 0xCBF43926.
LFSR noise source — Lfsr, LfsrApi. A shift register of 32 bits with
feedback: numbers that look random and are the same at each run and on every
target. noise.seed(7), noise.next() (32 bits), noise.uniform() (-32768 to
32767), noise.gauss() (around 0, a spread of 147.8).
Radix-2 FFT — Fft, FftApi. 2 to 256 points, on integers. fft.size(64),
fft.set(n, re, im) for each point, fft.forward() (divided by the number of
points) or fft.inverse(), then fft.re(k) and fft.im(k).
Complex arithmetic — Complex, ComplexApi, and the type Cplx
(struct Cplx { re: int16; im: int16 }, 32768 for 1). cx.add(a, b),
cx.sub(a, b), cx.mul(a, b), cx.mul_conj(a, b), cx.scale(a, num, shift),
cx.rotate(a, angle), cx.power(a). A result too large is held at the largest
value.
examples/5g-cell-search uses these three: a 5G
synchronisation signal sent through a noisy channel and found again
(5g-cell-search.md).
Tests and charts#
archec test lib/arche-algorithms/tests/main.arche --sim web
node tools/algorithm-charts.js
The first runs every algorithm on a bench of its own (a heater for the PID, a
room for the thermostat, a rocking board for the complementary filter…) and
checks it: the PID settles and does not wind up, the debounce ignores a 5 ms
glitch, the median never lets a spike out, the CRCs give their published values.
The second runs the same benches and writes each response.svg and
response.json: a plot over time (an on/off value as a lane under it), or y
against x for a curve or a path. test/algorithms.test.js fails when they are out
of date. It also generates every algorithm to C, C++, Rust, Go, Python and
TypeScript, builds them where the compiler is installed, and runs the same calls
in C, Go, Python and TypeScript to check that they give the same results.
Limits#
- Nothing here has run on hardware.
- The arrays are fixed: 32 samples for the moving average, 9 for the median, 16 points for the lookup table and the route.
- The values are
float32. Python and TypeScript compute in 64 bits, so their results differ from C's in the last digits. - A
uint64bit operation is exact in C, C++, Rust, Go and Python, not in the simulator or TypeScript (JavaScript numbers have 53 bits).
TheAlgorithms#
TheAlgorithms/Python has about 1,600 modules of algorithms in Python (MIT). arche-lang takes them in two ways:
- The embedded ones are translated. A function that fits a microcontroller
(no heap, bounded loops, fixed-size arrays) is translated from Python into the
action language by
archec import x.py. It then runs inarchec simand is generated to C, C++, Rust, Embassy, Go, Python and TypeScript, and each translation is checked against the Python on its doctests. - The others run in simulation. A module that needs a dict, a list that
grows, an int past 64 bits, numpy or recursion keeps its Python, unchanged.
It is a
simulation-onlycomponent whose functions bind by name to the module's defs (code "maths/x.py").archec simruns it in Python (sim.md), and its doctests are its tests. No microcontroller runs it: the embedded generators refuse it there.
/// Greatest common divisor
component GreatestCommonDivisor "greatest_common_divisor.py" {
simulation-only
code "maths/greatest_common_divisor.py"
fn greatest_common_divisor(a: any, b: any) -> any
fn gcd_by_iterative(x: any, y: any) -> any
}The simulation packages#
The simulation side is one Store package per upstream folder:
thealgorithms-maths, thealgorithms-sorts, and so on. They are not in this
repository; a script builds them from an upstream checkout:
git clone https://github.com/TheAlgorithms/Python upstream
node tools/thealgorithms-sim/build.mjs upstream out
For each folder, out/packages/thealgorithms-<folder>/ holds:
- the folder's
.pyfiles and data files, unchanged; <folder>.arche: asimulation-onlycomponent per module, afnper public top-level def (its parametersany), andpip "…"for what the module imports beyond the standard library;library.arche(ownerthealgorithms, MIT),README.md, upstream'sLICENSE, and aNOTICEthat says the upstream URL and commit.
Then the script runs archec sim library.arche --doctest in each package,
writes out/report.md and out/report.json, and publishes the packages to a
local store, out/store (its signing key in out/home, not in ~/.arche).
--only maths,sorts builds some folders, --python names the Python,
--no-doctest and --no-publish skip a step. Nothing is fetched or installed.
At commit 30507bb, with Python 3.12 and numpy, scipy, matplotlib and pillow installed, 1,179 of the 1,354 modules run with their doctests passing, and 58 more load but have no doctest. The 117 others do not run:
| Why | Modules |
|---|---|
| The network (web_programming, a few in machine_learning) | 39 |
| A pip package that was not installed: opencv-python 20, pytest 13, scikit-learn 9, pandas 5, sympy 4, imageio 1, mpmath 1 | 53 |
They import another folder (from maths.… in ciphers, data_structures in strings): each package holds one folder |
9 |
Python 3.15 syntax ([*x for x in xs]) |
6 |
| A doctest fails: 3 fail upstream too, 3 pass only with Python 3.14 | 6 |
| Too slow for the 20 s timeout (fractals, a plot) | 3 |
They read input() |
1 |
The translated packages#
The embedded side is in this repository: lib/algorithms-<folder>, one package
per upstream folder that has a function it translates and checks
(algorithms-maths, algorithms-sorts, algorithms-physics…). They are on the
algorithms shelf, and archec store seed publishes them. A script writes them
again from an upstream checkout:
node tools/thealgorithms-embedded/build.mjs upstream --python python3.14
For each folder it runs archec import <folder> --checked-only --embedded-only
(importing), and the package gets:
- a component per module, its functions in the action language, each with its
source "file.py:line"; no upstream.py; tests/: a rig per module that runs its doctests (archec test lib/algorithms-maths/tests/main.arche --sim web);library.arche(MIT, as upstream, shelfalgorithms), upstream'sLICENSE, aNOTICEwith the upstream URL and commit;REPORT.md: each function of the folder, translated or not, and why.
Only what agrees with Python on every input in the simulator, C and Rust is kept. At commit 30507bb, with Python 3.14:
| Folder | Functions | Embedded | Bounded | Simulation | Calls compared | Downgraded |
|---|---|---|---|---|---|---|
| maths | 403 | 129 | 0 | 274 | 1097 | 3 |
| bit_manipulation | 51 | 26 | 0 | 25 | 260 | 0 |
| conversions | 80 | 16 | 0 | 64 | 158 | 9 |
| sorts | 97 | 15 | 0 | 82 | 170 | 2 |
| searches | 47 | 6 | 0 | 41 | 56 | 2 |
| ciphers | 129 | 0 | 0 | 129 | 0 | 0 |
| dynamic_programming | 66 | 1 | 2 | 63 | 18 | 0 |
| hashes | 30 | 2 | 0 | 28 | 23 | 0 |
| matrix | 73 | 3 | 0 | 70 | 23 | 0 |
| strings | 102 | 1 | 0 | 101 | 8 | 0 |
| electronics | 44 | 7 | 0 | 37 | 26 | 0 |
| physics | 86 | 36 | 0 | 50 | 189 | 1 |
| audio_filters | 13 | 0 | 0 | 13 | 0 | 0 |
| geodesy | 6 | 2 | 0 | 4 | 13 | 0 |
| boolean_algebra | 22 | 6 | 0 | 16 | 54 | 0 |
| financial | 22 | 11 | 0 | 11 | 50 | 0 |
| geometry | 13 | 1 | 0 | 12 | 3 | 0 |
| greedy_methods | 12 | 0 | 0 | 12 | 0 | 0 |
| linear_algebra | 28 | 0 | 0 | 28 | 0 | 0 |
| scheduling | 17 | 0 | 0 | 17 | 0 | 0 |
| knapsack | 3 | 0 | 0 | 3 | 0 | 0 |
| divide_and_conquer | 38 | 2 | 0 | 36 | 15 | 0 |
| backtracking | 57 | 1 | 0 | 56 | 7 | 0 |
| other | 49 | 2 | 0 | 47 | 14 | 0 |
| all | 1488 | 267 | 2 | 1219 | 2184 | 17 |
A function that disagrees is left out (downgraded). Most are inputs the Python
takes and the translation does not: a negative index (xs[-1]), an int past 64
bits, an int power with a negative exponent. Two modules of the same name get
their folder's name in front (SpecialNumbersPerfectNumber, MathsVolume).
Limits#
- A package holds one folder, so a module that imports another folder does not run. Its imports are not packages of their own yet.
archec simdoes not install packages.pip "…"says what to install.- The page's Pyodide is Python 3.13 with its own packages: what needs another package, or Python 3.15, runs only in the terminal.
- Simulation-only modules are not translated, so they have no C, Rust or Go.