SLEuclid.sleela
lib/advantage/trading-actions-on-verb/SLEuclid.sleela · 285 line(s) · sleela
<< lib/advantage/trading-actions-on-verb/SLEuclid.sleela
SLeeLa Standard Library Definition.
Definition: Careful integer Euclidean toolkit: greatest common divisor by Euclid loop, Bezout coefficients, exact fills by two round lots in logarithmic time, and squared Euclidean distance with an exact integer square root. >>
#sleela 3.0
material;
artifact;
pure;
gasoline;
< SLeeLa int is a 64-bit signed integer: + - * / and % are exact over the full >
< range. But the comparison operators (== != < <= > >=) were measured to be >
< exact only up to 2^53 - 1 = 9,007,199,254,740,991; above that, neighbours >
< such as n and n - 1 compare equal. So every value that is ever compared in >
< this class is kept at or below that limit (maxExact), by construction. >
< Every loop has a stated invariant and a termination argument, and every >
< input is range-checked before use. Out-of-range input is refused with a >
< sentinel (-1, or false with fillStatus 2); it is never wrapped or clamped. >
< >
< gcd: invariant gcd(x, y) = gcd(a, b); y is a non-negative integer that >
< strictly decreases each pass because x mod y < y, so the loop ends. >
< egcd: the pairs (oldR, r) carry Bezout rows, so that >
< a*oldS + b*oldT = oldR holds before and after every pass. >
< isqrt: invariant lo*lo <= n < (hi+1)*(hi+1); hi - lo strictly shrinks. >
< canFill: closed form through the modular inverse, O(log) time. >
< canFillScan: the plain scan, kept only as a reference to test against. >
class SLEuclid {
< ---- Descriptive metadata (version 1.11 nested-friendly accessors) ---- >
<< Eleven catalogued attributes with getter/setter pairs. A worker-class
lesson carries the baseline identity record. >>
String metaVersion = "1.0.0";
int metaId = 39201;
String metaAuthor = "Kiro Agent";
String metaDate = "2026-11-11";
String metaCopyright = "SLeeLa project";
String metaTrademark = "none";
String metaCorporation = "none";
< metaOrigin: National | <nation> | International | Galactic >
String metaOrigin = "International";
String metaBirthDate = "2026-11-11";
< metaScienceRating: maturity/robustness on a 1..10 scale >
int metaScienceRating = 5;
< metaNationalSchedule: a real, citable instrument or "none" >
String metaNationalSchedule = "none";
String getMetaVersion() { return metaVersion; }
void setMetaVersion(String v) { metaVersion = v; }
int getMetaId() { return metaId; }
void setMetaId(int v) { metaId = v; }
String getAuthor() { return metaAuthor; }
void setAuthor(String v) { metaAuthor = v; }
String getDate() { return metaDate; }
void setDate(String v) { metaDate = v; }
String getCopyright() { return metaCopyright; }
void setCopyright(String v) { metaCopyright = v; }
String getTrademark() { return metaTrademark; }
void setTrademark(String v) { metaTrademark = v; }
String getCorporation() { return metaCorporation; }
void setCorporation(String v) { metaCorporation = v; }
String getOrigin() { return metaOrigin; }
void setOrigin(String v) { metaOrigin = v; }
String getBirthDate() { return metaBirthDate; }
void setBirthDate(String v) { metaBirthDate = v; }
int getScienceRating() { return metaScienceRating; }
void setScienceRating(int v) { metaScienceRating = v; }
String getNationalSchedule() { return metaNationalSchedule; }
void setNationalSchedule(String v) { metaNationalSchedule = v; }
< Largest absolute coordinate difference accepted by distSq. >
int maxDiff = 10000000;
< Largest dimension accepted. maxDiff squared times maxDim = 6.4e15 <= maxExact. >
int maxDim = 64;
< The largest magnitude that every comparison handles exactly (2^53 - 1). >
int maxExact = 9007199254740991;
< Largest lot size accepted by the fill routines: maxLot squared <= maxExact. >
int maxLot = 90000000;
< Largest order accepted by the fill routines. >
int maxOrder = 1000000000000;
< Largest value lcm may return. >
int maxMag = 9007199254740991;
< Largest k with k*k <= maxExact; the search for a floor root never goes above. >
int sqrtCap = 94906265;
< Number of loop passes taken by the last gcd call. >
int steps = 0;
< The remainder trail of the last gcd call, for example 120,180 -> 180,120 >
String trail = "";
< Bezout coefficients from the last egcd call: a*bx + b*by = g. >
int bx = 0;
int by = 0;
< The fill found by canFill or canFillScan: fillA lots of a plus fillB of b. >
int fillA = 0;
int fillB = 0;
< 0 = a fill exists, 1 = no fill exists, 2 = input out of range. >
int fillStatus = 1;
int abs(int v) {
if (v < 0) { return 0 - v; }
return v;
}
< Greatest common divisor of |a| and |b|. gcd(0, 0) is 0. Returns -1 when >
< either magnitude passes maxExact. >
int gcd(int a, int b) {
if (abs(a) > maxExact || abs(b) > maxExact) { return 0 - 1; }
int x = abs(a);
int y = abs(b);
steps = 0;
trail = x + "," + y;
while (y != 0) {
int r = x % y;
x = y;
y = r;
steps = steps + 1;
trail = trail + " -> " + x + "," + y;
}
return x;
}
< GCD of the first n values of v. Returns 0 when n is 0 or all are 0. >
int gcdAll(int[] v, int n) {
int g = 0;
int i = 0;
while (i < n) {
g = gcd(g, v[i]);
i = i + 1;
}
return g;
}
< Least common multiple, or -1 when the result would pass maxMag. >
int lcm(int a, int b) {
int x = abs(a);
int y = abs(b);
if (x > maxExact || y > maxExact) { return 0 - 1; }
if (x == 0 || y == 0) { return 0; }
int g = gcd(x, y);
int q = x / g;
if (q > maxMag / y) { return 0 - 1; }
return q * y;
}
< Extended Euclid for 0 <= a, b <= maxExact. Returns g and sets bx, by so that >
< a*bx + b*by = g. Returns -1 for an input outside that range. >
int egcd(int a, int b) {
if (a < 0 || b < 0 || a > maxExact || b > maxExact) { return 0 - 1; }
int oldR = a;
int r = b;
int oldS = 1;
int s = 0;
int oldT = 0;
int t = 1;
while (r != 0) {
int q = oldR / r;
int nr = oldR - q * r;
oldR = r;
r = nr;
int ns = oldS - q * s;
oldS = s;
s = ns;
int nt = oldT - q * t;
oldT = t;
t = nt;
}
bx = oldS;
by = oldT;
return oldR;
}
boolean bezoutHolds(int a, int b, int g) {
return a * bx + b * by == g;
}
boolean fillInRange(int c, int a, int b) {
if (a <= 0 || b <= 0 || c < 0) { return false; }
if (a > maxLot || b > maxLot || c > maxOrder) { return false; }
return true;
}
< True when c shares can be filled exactly by whole lots of a and b. >
< Solves a*x + b*y = c with x, y >= 0 and the smallest x. With g = gcd(a,b), >
< a' = a/g, b' = b/g, c' = c/g: a solution needs g | c, then >
< x = (c' mod b') * inverse(a' mod b') mod b', y = (c - a*x) / b, and it >
< exists exactly when y >= 0. Every product is at most maxLot^2 = 8.1e15 <= maxExact. >
boolean canFill(int c, int a, int b) {
fillA = 0;
fillB = 0;
if (!fillInRange(c, a, b)) { fillStatus = 2; return false; }
int g = egcd(a, b);
if (c % g != 0) { fillStatus = 1; return false; }
int ap = a / g;
int bp = b / g;
int cp = c / g;
int x = 0;
if (bp > 1) {
egcd(ap, bp);
int inv = ((bx % bp) + bp) % bp;
x = ((cp % bp) * inv) % bp;
}
int rest = c - a * x;
if (rest < 0) { fillStatus = 1; return false; }
fillA = x;
fillB = rest / b;
fillStatus = 0;
return true;
}
< Reference implementation by scanning a-lot counts 0, 1, 2, ... Runs at most >
< c / a + 1 passes. Used to cross-check canFill, not for large orders. >
boolean canFillScan(int c, int a, int b) {
fillA = 0;
fillB = 0;
if (!fillInRange(c, a, b)) { fillStatus = 2; return false; }
int i = 0;
while (i * a <= c) {
int rest = c - i * a;
if (rest % b == 0) {
fillA = i;
fillB = rest / b;
fillStatus = 0;
return true;
}
i = i + 1;
}
fillStatus = 1;
return false;
}
< Floor of the square root of n for 0 <= n <= maxExact, else -1. sqrtCap^2 <= >
< maxExact < (sqrtCap + 1)^2, so mid*mid is always compared exactly. >
int isqrt(int n) {
if (n < 0 || n > maxExact) { return 0 - 1; }
int lo = 0;
int hi = n;
if (hi > sqrtCap) { hi = sqrtCap; }
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (mid * mid <= n) { lo = mid; }
else { hi = mid - 1; }
}
return lo;
}
< Squared Euclidean distance between the first dim entries of a and b >
< (a and b start at offsets oa and ob). Returns -1 when dim is out of range >
< or any difference passes maxDiff. >
int distSqAt(int[] a, int oa, int[] b, int ob, int dim) {
if (dim < 1 || dim > maxDim) { return 0 - 1; }
int sum = 0;
int i = 0;
while (i < dim) {
int diff = abs(a[oa + i] - b[ob + i]);
if (diff > maxDiff) { return 0 - 1; }
sum = sum + diff * diff;
i = i + 1;
}
return sum;
}
int distSq(int[] a, int[] b, int dim) {
return distSqAt(a, 0, b, 0, dim);
}
< Floor of the Euclidean distance, or -1 on a rejected input. >
int dist(int[] a, int[] b, int dim) {
int s = distSq(a, b, dim);
if (s < 0) { return 0 - 1; }
return isqrt(s);
}
< Index of the target nearest to cur. Targets are stored one after another >
< in a flat array, dim entries each. A tie goes to the earlier target (the >
< repo tie norm). Returns -1 when count < 1 or any distance is rejected. >
int nearestIndex(int[] cur, int[] targets, int dim, int count) {
if (count < 1) { return 0 - 1; }
int best = 0 - 1;
int bestD = 0;
int t = 0;
while (t < count) {
int dd = distSqAt(cur, 0, targets, t * dim, dim);
if (dd < 0) { return 0 - 1; }
if (best < 0 || dd < bestD) { best = t; bestD = dd; }
t = t + 1;
}
return best;
}
}