russell@unturf.com
2f342c3be2
Adds tagged bignum support alongside the existing 48-bit fixnum on the C tier. Tag 6 = bignum, heap struct sign-magnitude with u64 little-endian limbs. Reader emits bignums for any literal past the fixnum range; +, -, *, quotient, remainder, modulo, expt, =, <, >, abs, odd?, even?, integer?, exact?, number->string, string->number all promote fixnum → bignum on overflow & demote back when results fit. Boehm GC owns every allocation. Schoolbook O(n²) mul + shift-subtract divmod is sufficient at our 4-limb / 256-bit scale. Before: (expt 2 48) = 0, (expt 2 256) = 0, secp256k1-p = -4294968273. After: all three return their exact arbitrary-precision values, matching Python tier byte-for-byte. Validated: - c/test.c — 85/85 pass (+2 new bignum unit tests). - tests/functional.lsp — 205/205 pass on both C & Python tiers. - tests/bignum-cross-tier.lsp — 33/33 pass byte-identical on both tiers (diff produces no output). - ecdsa/runs/lumbda-sweep-003/c-tier-bignum-probe.lsp — all four assertions now match the Python oracle. - ecdsa Phase B byte-identity sweep inside QEMU guest: n+1=9 p=251 sha256 c668bbe3... — matches Python oracle. n+1=18 p=131071 sha256 8a031f96... — matches Python oracle. n+1=33 p=2³²-5 sha256 0bc56905... — matches Python oracle. Previously the n+1=33 C tier emitted sha256 b024d6d9... (26,078 fewer Toffolis due to silent fixnum wrap). Bignums close that gate. secp256k1 production-width emit (n+1=257) is now structurally unblocked on C tier; downstream agent (#55) drives that next-step on the ecdsa side. Asm tier inherits in a follow-up port.
146 lines
8 KiB
Text
146 lines
8 KiB
Text
;;; bignum-cross-tier.lsp — Cross-tier byte-identity for arbitrary-precision
|
|
;;; integers. Runs identically under Python tier & C tier. Python tier is
|
|
;;; our oracle (native int handles every magnitude); C tier joined the
|
|
;;; bignum club here & must agree byte-for-byte with Python.
|
|
;;;
|
|
;;; Python: python3 lumbda.py --fast tests/bignum-cross-tier.lsp
|
|
;;; C: ./c/lumbda tests/bignum-cross-tier.lsp
|
|
;;;
|
|
;;; Every assertion logs PASS or FAIL; a final summary lines tallies them.
|
|
;;; Identity discipline: every PASS line on both tiers must match
|
|
;;; byte-for-byte.
|
|
|
|
(define *pass* 0)
|
|
(define *fail* 0)
|
|
|
|
(define (assert-equal name got expected)
|
|
(if (equal? got expected)
|
|
(begin (set! *pass* (+ *pass* 1))
|
|
(display "PASS: ") (display name) (newline))
|
|
(begin (set! *fail* (+ *fail* 1))
|
|
(display "FAIL: ") (display name)
|
|
(display " got=") (write got)
|
|
(display " expected=") (write expected) (newline))))
|
|
|
|
;;; ═══════════════════════════════════════════════════════════════
|
|
;;; Literals & basic reader/printer round-trip
|
|
;;; ═══════════════════════════════════════════════════════════════
|
|
|
|
(assert-equal "fixnum-literal-1" 42 42)
|
|
(assert-equal "fixnum-literal-2" -7 -7)
|
|
(assert-equal "bignum-literal-pos"
|
|
281474976710656 ; 2^48
|
|
281474976710656)
|
|
(assert-equal "bignum-literal-neg"
|
|
-281474976710656
|
|
-281474976710656)
|
|
(assert-equal "bignum-literal-256"
|
|
115792089237316195423570985008687907853269984665640564039457584007913129639936
|
|
115792089237316195423570985008687907853269984665640564039457584007913129639936)
|
|
|
|
;;; ═══════════════════════════════════════════════════════════════
|
|
;;; expt — promotion through fixnum boundary
|
|
;;; ═══════════════════════════════════════════════════════════════
|
|
|
|
(assert-equal "expt-2-30" (expt 2 30) 1073741824)
|
|
(assert-equal "expt-2-47" (expt 2 47) 140737488355328)
|
|
(assert-equal "expt-2-48" (expt 2 48) 281474976710656)
|
|
(assert-equal "expt-2-64" (expt 2 64) 18446744073709551616)
|
|
(assert-equal "expt-2-128" (expt 2 128)
|
|
340282366920938463463374607431768211456)
|
|
(assert-equal "expt-2-256" (expt 2 256)
|
|
115792089237316195423570985008687907853269984665640564039457584007913129639936)
|
|
|
|
;;; ═══════════════════════════════════════════════════════════════
|
|
;;; secp256k1 prime — 78-digit triple-subtraction lands precisely
|
|
;;; ═══════════════════════════════════════════════════════════════
|
|
|
|
(define secp-p (- (expt 2 256) (expt 2 32) 977))
|
|
(assert-equal "secp256k1-prime"
|
|
secp-p
|
|
115792089237316195423570985008687907853269984665640564039457584007908834671663)
|
|
(assert-equal "secp-p length" (string-length (number->string secp-p)) 78)
|
|
|
|
;;; ═══════════════════════════════════════════════════════════════
|
|
;;; Arithmetic at bignum scale
|
|
;;; ═══════════════════════════════════════════════════════════════
|
|
|
|
(assert-equal "add-bignum"
|
|
(+ secp-p secp-p)
|
|
231584178474632390847141970017375815706539969331281128078915168015817669343326)
|
|
|
|
(assert-equal "sub-bignum"
|
|
(- (* secp-p 2) secp-p)
|
|
secp-p)
|
|
|
|
;;; (* secp-p secp-p) — magnitude check via number->string length; exact
|
|
;;; value differs across tier baselines only if their bignum products
|
|
;;; diverge — Python tier serves as oracle (literal computed there).
|
|
(assert-equal "mul-bignum"
|
|
(* secp-p secp-p)
|
|
13407807929942597099574024998205846127479365820592393377723561443720769383374469661147847687812952081302854773939601805382211292725060150247698793015185569)
|
|
|
|
;;; Multi-step modular: a * b mod p
|
|
(define a 12345678901234567890123456789012345678901234567890)
|
|
(define b 98765432109876543210987654321098765432109876543210)
|
|
(assert-equal "mod-bignum"
|
|
(modulo (* a b) secp-p)
|
|
(modulo (* a b) secp-p))
|
|
|
|
(assert-equal "quotient-bignum"
|
|
(quotient (* secp-p 7) secp-p) 7)
|
|
|
|
(assert-equal "remainder-bignum"
|
|
(remainder (+ (* secp-p 3) 42) secp-p) 42)
|
|
|
|
;;; modulo wraps negative dividend by divisor sign
|
|
(assert-equal "modulo-neg-bignum"
|
|
(modulo (- 0 1) secp-p)
|
|
(- secp-p 1))
|
|
|
|
;;; ═══════════════════════════════════════════════════════════════
|
|
;;; Comparisons across fixnum/bignum boundary
|
|
;;; ═══════════════════════════════════════════════════════════════
|
|
|
|
(assert-equal "lt-bignum-fixnum" (< 1 (expt 2 100)) #t)
|
|
(assert-equal "gt-bignum-fixnum" (> (expt 2 100) 999) #t)
|
|
(assert-equal "eq-bignum-bignum" (= (expt 2 64) 18446744073709551616) #t)
|
|
(assert-equal "neq-bignum-fixnum" (= (expt 2 50) 0) #f)
|
|
|
|
;;; ═══════════════════════════════════════════════════════════════
|
|
;;; Predicates
|
|
;;; ═══════════════════════════════════════════════════════════════
|
|
|
|
(assert-equal "integer?-bignum" (integer? (expt 2 100)) #t)
|
|
(assert-equal "exact?-bignum" (exact? (expt 2 100)) #t)
|
|
(assert-equal "odd?-bignum" (odd? (- (expt 2 100) 1)) #t)
|
|
(assert-equal "even?-bignum" (even? (expt 2 100)) #t)
|
|
(assert-equal "zero?-bignum" (zero? (- (expt 2 100) (expt 2 100))) #t)
|
|
|
|
;;; ═══════════════════════════════════════════════════════════════
|
|
;;; Promotion & demotion
|
|
;;; ═══════════════════════════════════════════════════════════════
|
|
|
|
;;; Result of (- bignum bignum) that fits a fixnum demotes back.
|
|
(assert-equal "demote" (- (expt 2 64) (expt 2 64)) 0)
|
|
(assert-equal "demote-small" (- (expt 2 50) (- (expt 2 50) 7)) 7)
|
|
|
|
;;; number->string round-trip
|
|
(assert-equal "n->s-bignum"
|
|
(number->string (expt 2 100))
|
|
"1267650600228229401496703205376")
|
|
|
|
;;; string->number round-trip
|
|
(assert-equal "s->n-bignum"
|
|
(string->number "1267650600228229401496703205376")
|
|
(expt 2 100))
|
|
|
|
;;; ═══════════════════════════════════════════════════════════════
|
|
;;; Summary
|
|
;;; ═══════════════════════════════════════════════════════════════
|
|
|
|
(display "════════════════════════════════════════") (newline)
|
|
(display "bignum cross-tier: ")
|
|
(display *pass*) (display " passed, ")
|
|
(display *fail*) (display " failed")
|
|
(newline)
|