More › algorithms

More

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 var with 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.svg beside it, its data in response.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
}
Diagram: Oven
What archec draws from this code: Oven
Try it

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
}
Diagram: OvenPid
What archec draws from this code: OvenPid

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 uint64 bit 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 in archec sim and 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-only component whose functions bind by name to the module's defs (code "maths/x.py"). archec sim runs 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
}
Diagram: greatest_common_divisor.py
What archec draws from this code: greatest_common_divisor.py

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 .py files and data files, unchanged;
  • <folder>.arche: a simulation-only component per module, a fn per public top-level def (its parameters any), and pip "…" for what the module imports beyond the standard library;
  • library.arche (owner thealgorithms, MIT), README.md, upstream's LICENSE, and a NOTICE that 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, shelf algorithms), upstream's LICENSE, a NOTICE with 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 sim does 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.