CSE 111 — dc-bigint REPL (UCSC, Winter 2022)

This repo packages the dc-bigint assignment from CSE 111 (asg1): a Unix-style desk calculator (dc(1)) with arbitrary-precision integer arithmetic implemented from scratch in C++. The unsigned-bignum ubigint does carry-aware decimal arithmetic (+, −, ×, ÷, %, multiply/divide-by-2 primitives, binary long-division as the workhorse), and the signed bigint layers sign handling on top. The pow() function uses fast exponentiation (square-and-multiply) over the bigint type.

Live demo

https://codeseys.io/projects/cse-111-bigint

The browser-based REPL is the original course CLI's stack machine wired to a JavaScript text input: type 2 1000 ^ p and watch 302 digits of 2^1000 print back. The bigint/ubigint algorithms are unchanged from the course submission — only the I/O boundary is different.

Bugs fixed during the WASM port

The original course code had four arithmetic bugs that all needed fixing before the demo would produce correct answers:

1. ubigint(unsigned long) constructor: had : uvalue(that) in the member init list, which calls vector<uint8_t>(that) — i.e. constructs a vector of that zero-initialized elements — so ubigint(1) ended up as [0, 1] (a vector pre-populated with one zero, then '1' appended), which displays as "10" decimal. For any positive value the bug yielded value × 10^value. ubigint{1} and ubigint{2} and ubigint{0} all stopped meaning what they're named, breaking every literal-from-int construction in pow() and udivide(). Fix: empty the vector and only append digits, then trim.

2. ubigint::operator+: the final carry was never pushed onto the result. For 5 + 8 = 13, after the digit-pair loop sum = 3 with carry = 1, but neither tail loop runs (both indices past end), so 1 was lost and 5+8 printed as 3. Fix: push the residual carry after the three loops.

3. ubigint::divide_by_2: walked low-to-high and tried to read uvalue[i+1] before that digit had been halved — plus accessed past the end of the vector. The correct algorithm walks high-to-low, carrying the remainder from each digit into the next. Fix: rewrite to for (int i = size-1; i >= 0; --i) with a 0/1 carry from the previous iteration.

4. ubigint::operator<: in the same-size case, the per-digit scan returned false on this[i] > that[i] even when higher-order digits had already established this < that. For 12 < 50: high digits 1 vs 5 → 1 > 5 false (so don't return), continue to low digits 2 vs 0 → 2 > 0 → return false, declaring 12 < 50 to be false. Many divisions were wrong because of this. Fix: at the first differing digit (high to low), return whether this[i] < that[i].

5. ubigint::operator* (fixed earlier in the audit, before this attempt): temp[i+j] = temp[i+j] + this[i]*that[j] + carry without % 10 left digit slots holding values like 25 from 5*5, which printed as a literal "25" and made 5*5 display as "225".

After these fixes, the original pow() algorithm in libfns.cpp works correctly because it's algorithmically right — it was just being driven by broken primitives. Everything verified against Python: 2**1000, 30!, 2^31-1 all match byte-for-byte.

Layout

src/                       — original asg1 sources (with the bugs fixed inline)
  bigint.{cpp,h}           — signed bigint
  ubigint.{cpp,h}          — unsigned bigint (the actual arithmetic)
  iterstack.h              — std::deque-backed stack with iteration
  libfns.{cpp,h}           — pow() over bigint
  scanner.{cpp,h}          — input tokenizer
  util.{cpp,h}             — error type, env helpers (CLI-only; not in WASM)
  debug.{cpp,h}            — DEBUGF macro
  main.cpp                 — original CLI driver (kept for reference)
embeds-wasm/dc-bigint/     — Emscripten shim layer + REPL HTML harness
scripts/build-embeds.sh    — CI build script
web.codeseys.json          — Manifest for codeseys.io

Build pipeline

1. Push to master triggers .github/workflows/build-web-asset.yml, which calls the reusable workflow at baladithyab/web-embed-workflows@main.
2. Manifest declares build.tools: ["emsdk"] so the workflow installs Emscripten (cached after first run).
3. scripts/build-embeds.sh runs emcc over src/*.cpp (minus util.cpp and main.cpp) plus the wasm shim, producing embeds/dc-bigint.{js,wasm,html}.
4. The workflow uploads everything in embeds/ to Cloudflare R2 at cse-111-bigint/<git-sha>/, authenticated via OIDC (no static API keys).

Running the original CLI

After the bug fixes, the CLI also works correctly:

g++ -std=gnu++2a -O2 -o ydc src/*.cpp
echo '2 100 ^ p' | ./ydc
# → 1267650600228229401496703205376

echo '1 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * p' | ./ydc
# → 3628800

Running locally

# Install emsdk (one-time)
git clone https://github.com/emscripten-core/emsdk.git
cd emsdk && ./emsdk install latest && ./emsdk activate latest
source emsdk_env.sh

# Build
cd ../UCSC-CSE-111-BigInt
EMBED_SOURCE_DIR=embeds ./scripts/build-embeds.sh

# Serve
python3 -m http.server -d embeds 8080
# Open http://localhost:8080/dc-bigint.html